Educational Codeforces Round 124 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On Mar/10/2022 17:35 (Moscow time) Educational Codeforces Round 124 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

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

Comments Comments (161)
| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Me to chance pupil coder again,,,,,

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Hope your rating can get over 1200 after this contest! By the way, your profile photo looks interesting, so I used it as my profile photo. :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks you for your wising,,,, By the way i need perform like your profile graph and reach 1600+ rating,,, how can i do..../?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe you can try to solve some problems that have a higher rating than you currently have in the ProblemSet？For example, try to solve problems with a rating about 1400？

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +38 Vote: I do not like it

          At first I thought you were talking to yourself . . .

          → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Good luck everyone !

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very sad that I can't participate

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone!!

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Chance to get to pupil....

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Sadly, overlaps with Reply Challenge.

Probably, if there's lot of participants wishing take part in both, could be moved one hour earlier?

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope everyone to get higher rating in this round!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

contest is a kind of festival to me!

→ Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Kindly note unusually usual time.

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

My first comment. plz I really hope to be the expert

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could some one create a group to collect all educational contests like Div. 3 ?

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Considering my downward trend of performance in the recent Educationals, I can't help but

Спойлер
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question how do we know the difference between final standings after system tests and when hacking phase is finished? from what I have seen they don't write anything to distinguish that

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

C was tough one

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

DistanceForces

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

$$$|$$$ codeforces $$$|$$$.

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Why such a huge difference between problem B and C, kinda unfair for pupil / specialists

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 7   Vote: I like it +4 Vote: I do not like it

    Actually it was not so unfair since you required just one observation for C.

    Hint
    Reason
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am sorry but ... shouldn't connecting any 2 pairs do it? I mean having 2 connections between 2 distinct pairs, this way if one fails the any other is reachable.

      I spent about 30 minutes asking myself why the hell does the first test case need to connect 4 pairs.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        No it is not necessary.

        Reason
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Shouldn't they be reachable from the other functioning corner? Or you're saying connections are directed (one way)?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            No they wont be.

            Why?

            Hope it helps :)

            → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      Actually I figured out all of this, but I don't know what I am missing, maybe I'll find out tomorrow, pretty stressed out from today's contest

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        did you figure it out?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah for the X, |X and X| type of cases, I was doing a loop from 1 to n — 1, but 0 to n — 1 works, I am not sure why, because I cant see the test cases. Maybe some corner cases were getting missed

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            The idea is that if both a0b0 and a0bn-1 have the same distance, you might choose the wrong one i.e. if you pick a0b0, there might exist a smaller cost that requires you to pick a0bn-1

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Ahhh, you are making sense, damnit

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I disagree with your opinion mira from aim

              → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I think most of the people got the approach but got messed up in corner cases, including me. :(

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    welcome

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

I think i know my mistake in C but not enough time damn I wasted so much time thinking about stupid possibilities that doesn't help in anything

we could do it in three wires right ? like this

1 0 0 2 0 3
1 0 0 3 0 2

i tried only 2 wires or 4 but not 3.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you just need 2 wires

    link 1 1 and 3 2

    make it a loop

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's not the values it's how it's possible to link it the ones with the same number are linked sorry it wasn't clear

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        oh,yes

        we need consider head-head,tail-tail,head-tail,and head-other,tail-other

        possibly appear headA-headB + tailA-otherB + tailB+otherA

        → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Experts and CMs after solving A-D:

Image

Btw Im writing this comment 23 minutes before the end of the contest. I have no idea what to do with all this time on my hand:))

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Isn't problem c only about first and last index of both arrays and finding optimum values in their counterpart arrays?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. But you need to take into account what happens, if you connect 2 of those 4 nodes to each other.

    → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

hints for problem E pls

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Dlete

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    hint
    → Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve C and D?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    For C : a[0],a[n-1],b[0],b[n-1] all must have connection with other row any element efficiently..

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lmao I can't believe I thought any 4 points work and now I see it's nowhere near correct. Thanks very much!

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did BFS from the borders for D. Saving information in a map<pair<int,int>,...>

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D can be solve by dfs.. right ?

and C statement was confusing for me :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My DFS failed, needed BFS. What do you do if your DFS has back edges?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used BFS (from neighboring points not in the given set) and still got TLE. Is this not the idea? Or is there a way to speed up my BFS? 149168850

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Phew, just looked at your code, it looks ok in principle, your times seem to be ~1.5-2x slower than mine. Guess you need constant optimisation here maybe? In your first loop, when looking for borders, it seems that you can push solitary points 4x into the queue. You can put a continue; there in your ifs. Also you can mark them as used then already.

        Yes, constant optimisation did the trick: 149174036

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, didn't think to optimize constants. That did the trick. Thanks!

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I passed the pretest with dp and a lot of sortings.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What was the 2nd testcase in C?? I tried all the cases can someone tell what I was missing?149157891

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the last for loop of your code, you have written: aml=min(abs(a[0]-b[i]),amf); That should be: amf=min(abs(a[0]-b[i]),amf);

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is DP the correct approach for D? I tried to check the answers of my neighbours and pick the best for me but got TLE on test case 9 :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    a topological sort to decide the distance of closest point

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use a DP-like idea. The intuition for me was, for a point, the closest point to [x, y] must either have the same x value (so it's on the same vertical line), or it must be on a path through [x — 1, y] or [x + 1, y].

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D? I used dfs to transmit the nearest point but got wrong answer! :-(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I solved using multi-source BFS from all untaken points neighbouring taken points

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I tried something similar, but because i am not pro like it took some time for me to code it well. basically what i did is pushed all the points that has an direct answer into queue. (more like pushed the outer layer of points in queue first). then i translated outer layer's answers to inner layers. but i got Wrong answer on Test 9. can you help if you find anything sussy here?

      Edit: no worries got accepted. it. was a minor issue :(.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        That's unlucky. I was trying to debug for you but couldn't understand the candidates things. In principle your idea is correct, and equivalent to what I described as multi-source BFS, except starting with the outermost points rather than untaken points. Should achieve the same result.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          thanks for trying your code is sooo clean.

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Thanks. Although actually your approach is quicker and less memory intensive as it doesn't require storing all of the neighbouring points (which can increase the size of the graph by a factor of 5).

            → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used bfs and I got accepted

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why does bfs not time out

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

        200k points, at most 800k unused neighbours. Graph has max size 10^6. Why would this time out?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah it won't , i didn't think in the neighbour direction

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same problem as you

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the technique for B? I wasted so much time on A due to a stupid typo.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    any pair of i, j must satisfy Ai * 3 <= Aj

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Powers of 3 work

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try writing the inequality that needs to be satisfied based on the pair you pick.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Suppose you'll do the operation on $$$x$$$ and $$$mx$$$ which are present in the array where $$$m \geq 1$$$. After the operation, $$$x$$$ and $$$mx$$$ will be replaced by $$$mx - x$$$, we want the change of the sum to be greater or equal to the previous sum, which implies $$$2(mx - x) \geq x + mx$$$ $$$\implies m \geq 3$$$

    So, you build the array like this: $$$[1, 3, 9, 27, ...]$$$ until the array size is $$$n$$$ or the value gets higher than $$$10^9$$$. For the later case the output is $$$NO$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? I tried with all 3 cases, but WA on tc2 149150730

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In C my idea was that computers at end must be connected to some other computer, so we must find a way to minimize this. But for whole 1 hour I was not able to implement due to edge cases of computer at ends being connected to each other. I knew edge cases(like first computer of array A can be connected to first computer of B or last computer of B or both first and last computer of B etc.) but was not able to implement and deal with those.

Any tips on how to improve this ability? Sometimes I break down a problem in different edge cases and get overwhelmed by that.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

it really was an intersting contest i have solved C with topology :" which i have studied in CS

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Same! Lmao maybe that's why they ask CS fundamentals in interviews

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
My approach for C

Still WA on test 2 :( 149166751

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I calculated all 7 cases.

        // Case 1: a1 to b1 and an to bn;
    ans = min(ans, a1_b1 + an_bn);
    // Case 2: a1 to b1, min bn, min an
    ans = min(ans, a1_b1 + a_n + b_n);
    // Case 3: a1min + b1min + bnmin + anmin
    ans = min(ans, a_1 + a_n + b_1 + b_n);
    // Case 4: a1min + b1an + bnmin
    ans = min(ans, a_1 + b1_an + b_n);
    // Case 5: a1 to min, b_1 to min, an bn
    ans = min(ans, a_1 + b_1 + an_bn);
    // Case 6: a1 to bn, an to b1
    ans = min(ans, a1_bn + b_1 + a_n);
    // Case 7: a1 to bn and b1 to an
    ans = min(ans, a1_bn + b1_an);
    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    [Updated] Failing testcase: Ticket 1699

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D ? I got TLE on test 9.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think it's BFS + Dijkstra. If a point in the input is next to any empty point, then the answer is either 1 or 2. The other points must border at least some point in the input. From there you just BFS + Dijkstra to get the point with the least distance to empty point and populate the neighboors

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me figure out what‘s wrong with my code149129168 in problem B？ it runs well on my computer but kept failing the preset when I submit, I was literally driven crazy during the contest (╥_╥)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    move "ios::sync_with_stdio(false);" to the very beginning of the main function.

    maybe you can try to use CUSTOM TEST on Codeforces platform when you meet questions like this.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Put

    ios::sync_with_stdio(false);

    before reading the inputs, not after.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      what happens if we put after, will it cause undefined behaviour

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

In problem D, I used a similar idea as This Atcoder Problem. For each point, i binary searched for the shortest distance and used merge-sort tree to check the number of points that has smaller distance than a certain number with that point. I noticed that the distance should be smaller than sqrt(n), so after finding the distance i brute forced through all possible points for the answer.

I think The final complexity is O(nlog^3 + n*sqrt(n)*log) but got TLE on test 9. This will be my 6th consecutive rating drop.(╥_╥)

upd: My contest submission

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

my submission for D giving MLE... If anyone have experienced similar problem, please help me

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used bfs，put the unused neighbours in the queue，and calc the answer when you meet a node which is not among the given $$$n$$$ points.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is $$$O(Nsqrt(NlgN))$$$ intended for problem F? I know that we can do pure $$$Nsqrt(N)$$$ if we solve for each block for each monster instead of for each monster for each block, but still, it sounds like a lot of work :(

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Model solution is $$$O(N \log N)$$$, but we decided to allow slower solutions with good implementation pass (although $$$O(N \sqrt{N \log N})$$$ sounds kinda scary)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Apparently even $$$O(N \sqrt{N} \log N)$$$ can pass :)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, the time limits were kinda generous in this problem (the model solution runs in something like 1s on 32-bit C++ compiler). Although 3931 ms out of 4000 sounds very scary

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Not at all mine runs in 1.5 seconds which is kind of okay also it's really easy to write and you can argue that if written with prefix sum the operations would be simple enough that you wouldn't be able to differentiate between $$$O(NlgN)$$$ and $$$O(NsqrtN)$$$ "unless you go full Chinese on the constraints/test data ig".

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I changed to unordered_map, so $$$O(N \sqrt N)$$$, and it passed, although 3899 ms. D:

    → Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much! This is amazing!

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

is cf_predictor gives correct predicted values ? i think that there must much increasing points in rating than i see in standings.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Screw C. Took more than an hr to solve it, and 40 minutes to finish D but not time to submit it

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My approach for D:

Rotate coordinate space by 45 degree by transforming (x,y) with (x+y, x-y). Now, for a point X, observe that all 4 points at distance 1 form a square, then next 8 points at distance 2 form another square and so on. Each square will have 4D points here D is distance from X.

Since N is 2*10^5, D can be at most 350. So for each point, I checked number of input points in squares of length 1, 2...350. As soon as I get a square of length d which has less than 4d points, we need to search in this square.

Then its simply searching all points at distance d and returning any one excluded point.

Complexity: O( N*Sqrt(N)*log(N) ) Solution: 149223014

But solution TLE'd on test case 30. Would appreciate if someone can take a look at my code and suggest scope for optimization.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you check the number of points in a square?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I got TLE on test 30 149175151. I doubt the time complexity but also can't imagine what does the worst case look like.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I think theoretically the number of operations in the worst case would be around 5.6*10^9 [(2*10^5)*(350)*(20)*(4)]

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I was trying to use openmp's parallel functionality, does cf supports it? i am not getting any error nor can i observe any significate difference in execution time.

        without pragma 149232334

        with pragma 149233499

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    changed your unordered set to set, because i guess performance of hash structure is complicated to guess.

    can you find why it is printing an already existing point?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Fixed a silly bug. Updated the comment.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        You can eliminate use of set, you already have list of sorted point with respect to both dimensions.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a solution which barely passes and it was possible thanks to IceKnight1093 optimizing my previous code by omitting pairs.

    It uses pragmas and shit so it's totally not safe for a contest submission.

    Perhaps someone else can bother to optimize it further.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved D considering/using that answer can never be greater than 700 . I made pair of interval for each coordinate of x from 0 to 2*10^5+1 which doesn't have a y coordinate . Then for point {x_i , y_i} it's just binary search the left nearest and right nearest value of y for each z s.t. ( z>=x-700 and z<=x+700)
    It's ACs in approx 1 sec
    Solution

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

My ideas for D (not AC on contest) :

  1. Pick a random unvisited point name it $$$p$$$ and mark this point as visited

  2. Do floodfill to another points adjacent from $$$p$$$ and mark them all as visited (adjacent : manhattan distance is equal to 1)

  3. So now from all the floodfilled points we form a connected component from $$$p$$$. Pick border points from this connected component (a point is called border if there's at least 1 adjacent point which doesn't exist in the input)

  4. From all border points, we can get their respective "source" (i.e. the neighboring point which is not in the input)

  5. Do multisource BFS from all border points and now you can get source for all non-border points by setting it to the source of their nearest border points

My implementation 149198396

I love the idea of the solution! Didn't quite like C (because caseworks), but this problem has a beautiful solution

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

chance to get specialist...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to know how people know this formula for problem B :

(b — a) * 2 >= b + a

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We need the next sum to be no less than the previous one. If we change a and b to |a — b| then their sum will be equal to |a — b| + |a — b|. We can expand the module and get (a — b) *2. And by condition, we want this sum to be at least a + b. => 2 * (a — b) >= a + b

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

when are the ratings going to update as it's past 12 hr already?

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

When will the rating be changed?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    same doubt its showing in unrated constest for now

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    You did not participate in the contest, why do you care about it? This kind of question has been asked a ton of times for every Educational round.

    → Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

The rating is still not updated......

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey does anyone know why I didn’t get rated yet is educational round ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No one got rated yet. The editorial has just been released so I would assume ratings will be updated soon too.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Me here reloading the website every 10 seconds for +2 delta :/

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In yesterday's competition, my code for question B was judged to be duplicate with others, but my code was submitted earlier, so there is no possibility of plagiarism at all. Plus, I want to score 2100 for this game, so there's no way I'm giving away my code to anyone else. Moreover, the solution shown in my code is a very general solution, and it is very easy to repeat it in a small amount of code. I don't think it's reasonable. Please check it carefully!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    MikeMirzayanov，I could have been a master, but now I'm an expert. Please check it! Thank you!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with me bro i got plagiarism on A. how can it be possible problem A was one liner

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I hope for a reasonable explanation. This accident reduced my rating by 300 :(

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I can understand bro but I don't think our issues will be responded

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for your comfort. I hope there will be no similar problems in the future. Good luck.

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I had a coincidence of my solution(149124483) matching with solution(149099666) of Performanceartist for the problem 1651B . clearly it is a coincidence as he is a candidate master and i a newbie with no prior communication between us. He submitted his solution much before me. please look into it. Your text to link here...

he(performanceartist) has commented for the same problem.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A sad coincidence, isn't it? Haha. We need to work hard in the coming contests bro :)

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The worst C problem I have ever solved.

→ Reply
»
11 months ago, # |
  Vote: I like it -10 Vote: I do not like it

I can't even see if there is any same place between my code 234454715 and 234466169, can officials check again, and it's no reason to copy such a easy problem with risks.

→ Reply