Educational Codeforces Round 124 [Rated for Div. 2]

Hello Codeforces!

On Thursday, March 10, 2022 at 14:35UTC 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!

• 20 hours ago, # ^ |

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

  • 19 hours ago, # ^ |

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

    • 19 hours ago, # ^ |

      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？

      • 18 hours ago, # ^ |

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

• 39 hours ago, # ^ |

  Oh no that is so sad :( Give me your password, I shall participate in your stead.

  • 24 hours ago, # ^ |

    ← Rev. 3 →  

    0

    hahahaha, the cleverest

• 18 hours ago, # ^ |

  Chance to leave pupil

• 15 hours ago, # ^ |

  I should be practice more

• 18 hours ago, # ^ |

  Use this website here you can filter contest based on contest types and many more things you can do https://clashofcodes.herokuapp.com/codeforces

  • 18 hours ago, # ^ |

    Why ask to signup first? How is signing up going to benefit the user?

    • 18 hours ago, # ^ |

      I guess they made it mandatory recently as i made an account previously so i don't know about it but it is a good website can make accout there google auth.

• 16 hours ago, # ^ |

  "absolute"ly.

• 15 hours ago, # ^ |

  ← Rev. 7 →  

  +1

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

  Hint

  Reason

  • 15 hours ago, # ^ |

    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.

    • 15 hours ago, # ^ |

      ← Rev. 2 →  

      0

      No it is not necessary.

      Reason

      • 15 hours ago, # ^ |

        ← Rev. 2 →  

        0

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

        • 15 hours ago, # ^ |

          No they wont be.

          Why?

          Hope it helps :)

          • 14 hours ago, # ^ |

            Thank you so much for your detailed responses. I get it now, senpai XD.

  • 15 hours ago, # ^ |

    ← Rev. 2 →  

    +2

    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

  • 15 hours ago, # ^ |

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

    • 3 hours ago, # ^ |

      Yes, same for me :(

• 15 hours ago, # ^ |

  you just need 2 wires

  link 1 1 and 3 2

  make it a loop

  • 15 hours ago, # ^ |

    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

    • 15 hours ago, # ^ |

      oh,yes

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

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

  • 5 hours ago, # ^ |

    no he need 3 wires. 1_1 2_2 3_3 ans=0;

• 16 hours ago, # ^ |

  And some Ms, too

• 16 hours ago, # ^ |

  I don't know what you are talking about...

• 16 hours ago, # ^ |

  Help others! LOL

• 15 hours ago, # ^ |

  shake hands...

• 16 hours ago, # ^ |

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

  • 15 hours ago, # ^ |

    I considered it, seems i need to see the test case to understand :(

• 3 hours ago, # ^ |

  Hint 1

  Hint 2

  Hint 3

• 15 hours ago, # ^ |

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

  • 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

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

  • 15 hours ago, # ^ |

    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

    • 15 hours ago, # ^ |

      ← Rev. 2 →  

      0

      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

      • 15 hours ago, # ^ |

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

• 6 hours ago, # ^ |

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

• 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  a topological sort to decide the distance of closest point

• 15 hours ago, # ^ |

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

  • 11 hours ago, # ^ |

    I tried your idea. Is this way is correct to implement it? 149191779
    I got RE on testcase9.

    • 102 minutes ago, # ^ |

      Failing testcase: Ticket 1708

      What's so special about the testcase? It contains all points in the interval [1,5]×[1,5][1,5]×[1,5]

• 15 hours ago, # ^ |

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

  • 15 hours ago, # ^ |

    ← Rev. 3 →  

    0

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

    • 14 hours ago, # ^ |

      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.

      • 14 hours ago, # ^ |

        thanks for trying your code is sooo clean.

        • 14 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  I used bfs and I got accepted

  • 15 hours ago, # ^ |

    why does bfs not time out

    • 15 hours ago, # ^ |

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

      • 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  I have the same problem as you

• 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  Powers of 3 work

• 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  Suppose you'll do the operation on xx and mxmx which are present in the array where m≥1m≥1. After the operation, xx and mxmx will be replaced by mx−xmx−x, we want the change of the sum to be greater or equal to the previous sum, which implies 2(mx−x)≥x+mx2(mx−x)≥x+mx ⟹m≥3⟹m≥3

  So, you build the array like this: [1,3,9,27,...][1,3,9,27,...] until the array size is nn or the value gets higher than 109109. For the later case the output is NONO.

• 15 hours ago, # ^ |

  try link left and right end of A and B. either use optimal point in opposite array, or link two end points.

• 15 hours ago, # ^ |

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

• 15 hours ago, # ^ |

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

• 14 hours ago, # ^ |

  ← Rev. 2 →  

  +1

  [Updated] Failing testcase: Ticket 1699

• 13 hours ago, # ^ |

  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

• 15 hours ago, # ^ |

  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.

  • 15 hours ago, # ^ |

    oh got it! Thanks for your reply! I will try it next time!

• 15 hours ago, # ^ |

  ios::sync_with_stdio(false);

  before reading the inputs, not after.

  • 15 hours ago, # ^ |

    thanks a lot! what a silly mistake of mine！

  • 3 hours ago, # ^ |

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

• 15 hours ago, # ^ |

  In these cases, try to use custom invocation for testing

• 15 hours ago, # ^ |

  I got MLE because of stack overflow. Forgot to maintain a visited hash table when recursing.

• 4 hours ago, # ^ |

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

• 14 hours ago, # ^ |

  Model solution is O(NlogN)O(Nlog⁡N), but we decided to allow slower solutions with good implementation pass (although O(NNlogN−−−−−−−√)O(NNlog⁡N) sounds kinda scary)

  • 13 hours ago, # ^ |

    Apparently even O(NN−−√logN)O(NNlog⁡N) can pass :)

    • 13 hours ago, # ^ |

      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

  • 11 hours ago, # ^ |

    ← Rev. 2 →  

    0

    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)O(NlgN) and O(NsqrtN)O(NsqrtN) "unless you go full Chinese on the constraints/test data ig".

• 14 hours ago, # ^ |

  Thank you so much! This is amazing!

• 13 hours ago, # ^ |

  Yes, I have found the carrot chrome extension to be more accurate.

• 8 hours ago, # ^ |

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

• 4 hours ago, # ^ |

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

  • 15 minutes ago, # ^ |

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

• • 21 minute(s) ago, # ^ |

    Thanks. Fixed a silly bug. Updated the comment.

    • 15 minutes ago, # ^ |

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

• 57 minutes ago, # ^ |

  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