By ReplyChallenges, history, 7 weeks ago,

Hello Codeforces!

We're glad to invite you to the upcoming Reply Code Challenges 2021 edition, on 11th of March.

It's a free online team-based challenge and you can choose between:

### Standard Edition: designed for university students and professionals

Each member of the first-placed team wins a Mac Book Pro™ 16 (2.3GHz 6-core 9th-generation Intel Core i9 processor, AMD Radeon Pro 5500M with 4GB of GDDR6 memory, 16GB 2666MHz DDR4 memory and 1TB SSD storage). The second-placed team members each win a Mac Mini™ (Apple M1 chip with 8-core CPU, 8-core GPU and 16-core Neural Engine, 256GB SSD storage), the team members placed third in the ranking each win Apple Air-pods Pro™.

### Teen Edition: designed for students aged 14 to 19

The winning team will receive 5,000 euros. The second-ranked team will receive 2,000 euros, the third-ranked team will receive 1,000 euros.

Description and rules available online at challenges.reply.com on March 11th from 4.30pm to 8.30pm CET. To play you must form a team by March 10th.

• +219

 » 7 weeks ago, # |   0 tourist is coming xD
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +42 MAC BOOK PRO is coming for TOURIST
•  » » » 7 weeks ago, # ^ |   0 ikr !! xD
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Funny thing is tourist even doesn't need a team:,-)
•  » » 7 weeks ago, # ^ |   +44 Last year's winner was Errichto' team :D
 » 7 weeks ago, # | ← Rev. 2 →   0 Hi, I'm looking for people to team up with me (for the teen challenge). PM me on codeforces if you're interested (preferably be close to a CM or above). Thanks!Edit: Preferably someone from the US as well
•  » » 7 weeks ago, # ^ |   +25 If you are looking for someone, you can join our Find your team mate telegram group with other participants.
 » 7 weeks ago, # | ← Rev. 4 →   -51 MAC BOOK PRO is coming for tourist :)
 » 6 weeks ago, # | ← Rev. 2 →   -24 Tourist farm money again :)
 » 6 weeks ago, # |   +24 Last days available for the registrations, hurry up!
 » 5 weeks ago, # |   +15 last 16h to register! Tomorrow is the day — see you online from 4.30 pm to 8.30 pm cet
•  » » 5 weeks ago, # ^ |   0 I think we have few more hours to register, to be exact it's 12 hours, 11 minutes from now.
 » 5 weeks ago, # |   0 How to get the Reply U's T-shirt ?
•  » » 5 weeks ago, # ^ |   0 I dont think there are any t-shirts :(
 » 5 weeks ago, # |   0 The problem was very nice and we loved the contest. Can anyone please tell me that why my Dev-C++ compiler was not producing outputs for input data E,F as it was producing for A,B,C&D.I tried everything but couldn't submit E and F because Dev-C++ was not giving outputs for very large input files. Also tried to use Jdoodle but no success.
 » 5 weeks ago, # |   +49 Can someone share an implementation of half-plane intersection? We used MIT code but failed last input, idk why.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   +54 I used and I also wrote smth from scratch and they matched on the D5 input file I downloaded, so idk what happened. Does anyone have code that passes? :P(Also, what even was E ... We had at least two different interpretations and two of them matched on all but the last input. So we just redownloaded the input again so both interpretations gave the same answer ...)
•  » » » 5 weeks ago, # ^ |   +28 Can you share your code? We used http://cf.yanyanlongxia.cn/gym/101309/submission/52249734
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +38 Unable to view that link.V1:http://ideone.com/ZHxF6OV2:http://ideone.com/ZI1eGe(though these solutions are very similar, so I would be surprised if they gave different outputs)(C++17 required)
•  » » » » » 5 weeks ago, # ^ |   +48 Both solutions have the same output as mine in the large input we got. Maybe something is wrong with checker.Also, in this problem we submited twice input D to get AC.
•  » » » » » » 5 weeks ago, # ^ |   +53 Same ...
•  » » » » » » » 5 weeks ago, # ^ |   +48 Same
•  » » » » » » » » 5 weeks ago, # ^ |   +42 Same
•  » » » » » » » » » 5 weeks ago, # ^ |   +31 Same
•  » » 5 weeks ago, # ^ |   +18 Also, why limits of coordinates are hidden??????
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +26 solution Reply sent me — http://ideone.com/hGS3pIdiffers from my solution by relative error $\sim 10^{-7}$ on some casesmodified version of above solution (with different EPS and Decimal for more precision) — http://ideone.com/KUiPqMmatches my solution almost exactly
 » 5 weeks ago, # | ← Rev. 2 →   +44 I was coding alone and these are my results (6th place): It seems that even results of winners could be significantly improved since I know on F I have score bigger by ~340M than Rethinkers which were ~120M behind 1st place.
•  » » 5 weeks ago, # ^ |   +8 Could you please explain your ideas for problem D, E and F?
•  » » » 5 weeks ago, # ^ |   +54 A very important observation is that radii of antennas are more like 5 instead of 6000. In particular that gives us opportunity to compute result much faster than $O(buildings \cdot antennas)$ cause for a particular building we only need to inspect antennas in its proximity and not too many antennas of high radius (that is "sqrt-decompish" type of thinking :p, I chose 15 as a threshold).Second observation that I made was that this negative part with latency has negligible influence on the result. I still compute it, but I disregard it in all of my thinking on what and how to optimize things.Then I sort antennas by C values. Ideally I would like to do the following. For each following antenna choose a place which maximizes sum of C values of noncovered buildings that it would cover if placed here (it is good to match big C antenna values to big C building values). Such algorithm would in fact give better results than ones that I have, however a problem here is that I cannot really compute it efficiently. It would be not that hard to do in $O(antennas \cdot R \cdot C)$, but that seems too slow. For radius up to 5 I compute it optimally. I have a designated priority-queue-like structure implemented on many vectors for each such radius. For bigger radii I take many (~10 thousands) random places and take the best one. This should give >41.5B and to get my score I tried doing some more messy optimization.What I didn't really give a try was local search. However it is possible to do it since each building is covered by only a small number of antennas. By local search I mean "remove some antenna, place it elsewhere, quickly recompute the result and accept this change if it didn't make result worse". I will try to code this now.
•  » » » » 5 weeks ago, # ^ |   +16 I added local search and it raised my scores to:B: 2042796558D: 5106007900E: 7823657652F: 25081748708If I'm not mistaken my total score would currently be around 42.11B. Improvement was significant, however I was hoping for more :P. Especially in D and E were I still have significant losses to Rethinkers (surprisingly my biggest improvement was on F where I already got a big advantage over them).
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 The O(M * R *C) is not that slow if you skip some of the cells. Me and my wife are 7th (just behind you) and managed to run F in around 25 minutes.What we do is sort the antennas by speed * range (actually a slightly better sorting is speed * (range + 1), but I figured this out too late); then for each antenna traverse all points on the grid and find the best position for it. This is okay-ish for all tests except F (if you have a fairly fast finding of the covered buildings; we have an almost linear one, thus if the antenna covers K buildings we use O(K)). For the last test we needed to skip some of the points on the grid. We set step = antenna[i].range / 3 + 10 (random variables we tweaked during the contest).
 » 5 weeks ago, # |   +186
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Idk what's wrong with my code. I tried using this and it gave the same output so I concluded that I don't have precision issues.Looks like other people also had some issues.
•  » » » 5 weeks ago, # ^ |   0 can you share your implementation?Also, how did you check for the infinity case, we tried calculating the area of intersection twice with two different bounding boxes and checking if the answer is the same. I guess there is also some issues with the choice of EPS, we figured out with some trial and error that (EPS = 1e-8) works for the first four inputs.I used this implementation
•  » » » » 5 weeks ago, # ^ |   +3 I modified kactl line container. Idl if i want to share my xoee it got so ugly.
 » 5 weeks ago, # |   +13 Team Rethinkers — znirzej, tabasz shadowatyy, xman1024 Second Place
•  » » 5 weeks ago, # ^ |   +5 I would love to hear a bit of your approach!
•  » » » 5 weeks ago, # ^ |   +13 So the first phase of our solution was a greedy approach: We sort antennas descending by $radius * speed ^ {2.4}$ Then we iterate over antennas and try to place each antenna as good as we can To do it we iterate ~$10^5$ times (depending on the test) and do the following: Choose a random position on the grid and calculate the score of placing the antenna in this position Try to move the antenna to neighbor cells if a score of placing in this random place was at least 95% of the best one The second phase was Hill Climbing. We had a fast approach to change the position of an antenna and update the score. So we were trying to move antennas to increase the resultUnfortunately, we finished Hill Climbing ~30 minutes before the end of the contest and we didn't have as much time to run it as we wanted to, but it still gave us ~ $1.5 * 10^9$ pointsAlso, few minutes after the end of the contest a greedy solution on test F with a higher number of iterations finished and it gave us ~$0.5 * 10^9$ improvement.Good contest, congratulations to the winners!
•  » » 5 weeks ago, # ^ |   0 Sir, what IDE do you use, I was having problems with Dev-C++ as it generated output with freopen for Test Cases A,B,C,D but as E and F were very large input files, it generated blank output files.Should I use any other IDE, please help?
 » 5 weeks ago, # |   +138 The teen edition contest was completely ruined by the statement of E. Literally nobody could understand what the "winner of turn" means. The support staff refused to meaningfully reply and clarify. All they said was : "check the broadcast", which unfortunately didn't clarify anything. Most people passed first 3 groups of that task with random buggy shit without understanding the statement, because apparently the definition didn't matter. Can anyone clarify what it meant?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +69 After a bunch of trial and error, we concluded that "distance" referred to one of the following (not totally sure which): undirected distance minimum of directed distance to and directed distance from Leaning towards the former, might have made sense before the clarification ...
•  » » » 5 weeks ago, # ^ |   0 What was your score?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +25 Team ^_^ (4600)
•  » » » 5 weeks ago, # ^ |   +106 We got the problem accepted with the former (undirected). I'd like to thank my teammate for not following any clarifications.
 » 5 weeks ago, # | ← Rev. 3 →   +18 Team: parth20,Priyansh31dec, Gaurav_Dawra Global rank: 28 (India rank: 1) (if anyone cares XD)
 » 5 weeks ago, # | ← Rev. 3 →   +37 For the record, we mostly did something like the follows: do a bfs from each building to it's neighbourhood. Assign a "score" to each cell via this bfs from each building. Then greedily assign to the cells. With some small optimizations this gave 30.8b, and it's clear that we were missing some idea for 40b. Team — Beernary Search (TheOneYouWant, Ashishgup, IceKnight1093 aryanc403)
•  » » 5 weeks ago, # ^ |   +25 We also assigned the "score" in a similar way (in some neighborhood of constant size). But when we put an antenna somewhere, we remove all the buildings it can reach, i.e. subtract their contribution back from the score in reachable cells. The higher we choose the neighborhood size, the higher score we get, so we selected it as large as possible as long as we fit into memory/time. We also got some improvement by sorting antennas by $R^{\alpha}\cdot C$ instead of just $C$ before the greedy part. $\alpha$ that worked best was some small number in the range $0.1-0.3$. Our final results (9th place):
 » 5 weeks ago, # |   +35 Will the contest be opened for upsolving?
 » 5 weeks ago, # |   +22 Will there be an editorial for the contest ?
 » 5 weeks ago, # |   +25 Thanks to the contest. It reminds me of the old good days of OI while I'm in college, despite the strange experience caused by the statement of E.
 » 4 weeks ago, # |   +8 Can anyone explain solution of D.painting ? (teen edition)
 » 4 weeks ago, # |   +5 ReplyChallenges, would you share how the test were created? Here's what my team got during the contest:test B: Buildings' speed and latency uniformly distributed, xy also uniformly random.test D: Buildings' speed and latency were equal, not sure what the distribution was, looks kinda triangular. Their xy positions are distributed into smaller squares and speed/latency of a building was proportional to the distance from center of the square in belonged to.test E: Buildings' speed and latency were aligned into a shape resembling Great Britain. Latency distribution looks normal-ish, speed looks like nothing to me. Wasn't able to determine how the xy positions were assigned, but it must have depended on their speed and/or latency and looks like some kind of a contour.test F: 20 different (~ uniformly distributed) pairs (building speed, building latency), buildings with same (speed,latency) were aligned into regions.When it comes to antennas, it looks like for all of these tests you just picked a couple of rectangles, then picked how many points you want from each of them and then uniformly sampled. By rectangle I mean ((min speed, max speed), (min range, max range)). Am I wrong?
 » 4 weeks ago, # |   +8 Do anyone know other contests of the same kind ? (such a Google Hashcode)
•  » » 3 weeks ago, # ^ |   0