ReplyChallenges's blog

By ReplyChallenges, history, 2 months ago, In English

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™.

Registration opened on https://replychallenges.com/StandardEdition2021

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.

Registration opened on https://replychallenges.com/TeenEdition2021

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.

Follow us on our Telegram Channel: https://t.me/replychallenges

 
 
 
 
  • Vote: I like it
  • +219
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tourist is coming xD

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 4   Vote: I like it -51 Vote: I do not like it

MAC BOOK PRO is coming for tourist :)

»
2 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

Tourist farm money again :)

»
2 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Last days available for the registrations, hurry up!

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

last 16h to register! Tomorrow is the day — see you online from 4.30 pm to 8.30 pm cet

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think we have few more hours to register, to be exact it's 12 hours, 11 minutes from now.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get the Reply U's T-shirt ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Can someone share an implementation of half-plane intersection? We used MIT code but failed last input, idk why.

»
2 months ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Could you please explain your ideas for problem D, E and F?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        I added local search and it raised my scores to:

        B: 2042796558

        D: 5106007900

        E: 7823657652

        F: 25081748708

        If 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).

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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).

»
2 months ago, # |
  Vote: I like it +186 Vote: I do not like it

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I modified kactl line container. Idl if i want to share my xoee it got so ugly.

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Team Rethinkersznirzej, tabasz shadowatyy, xman1024

Second Place

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I would love to hear a bit of your approach!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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 result

      Unfortunately, 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$$$ points

      Also, 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!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
2 months ago, # |
  Vote: I like it +138 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +69 Vote: I do not like it

    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 ...

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What was your score?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +106 Vote: I do not like it

      We got the problem accepted with the former (undirected). I'd like to thank my teammate for not following any clarifications.

»
2 months ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

Team: parth20,Priyansh31dec, Gaurav_Dawra
Global rank: 28 (India rank: 1) (if anyone cares XD)

»
2 months ago, # |
Rev. 3   Vote: I like it +37 Vote: I do not like it

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)

Screenshot-from-2021-03-12-02-12-49

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it
    • 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):

»
2 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Will the contest be opened for upsolving?

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Will there be an editorial for the contest ?

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone explain solution of D.painting ? (teen edition)

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Do anyone know other contests of the same kind ? (such a Google Hashcode)