By awoo, history, 4 months 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

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

Me to chance pupil coder again,,,,,

  • »
    »
    4 months 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. :)

    • »
      »
      »
      4 months 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..../?

      • »
        »
        »
        »
        4 months 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?

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Good luck everyone !

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

Very sad that I can't participate

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

Good luck everyone!!!

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

Good luck everyone!!

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

Chance to get to pupil....

»
4 months 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?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope everyone to get higher rating in this round!

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

good luck guys

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone!

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

I like Educational round.Thanks to the organizers.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

contest is a kind of festival to me!

»
4 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Kindly note unusually usual time.

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Any Interactive problem?

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
4 months 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 ?

»
4 months 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

Spoiler
»
4 months 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

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

C was tough one

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

DistanceForces

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

SpeedForces :(

»
4 months 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

  • »
    »
    4 months 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
    • »
      »
      »
      4 months 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.

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

        No it is not necessary.

        Reason
        • »
          »
          »
          »
          »
          4 months 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)?

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

            No they wont be.

            Why?

            Hope it helps :)

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

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

    • »
      »
      »
      4 months 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

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

        did you figure it out?

        • »
          »
          »
          »
          »
          4 months 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

          • »
            »
            »
            »
            »
            »
            4 months 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

    • »
      »
      »
      4 months 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. :(

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

    welcome

»
4 months 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.

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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

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

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

»
4 months 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:))

»
4 months 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?

  • »
    »
    4 months 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.

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

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

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

hints for problem E pls

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

    Dlete

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

How to solve C and D?

  • »
    »
    4 months 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..

    • »
      »
      »
      4 months 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!

  • »
    »
    4 months 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>,...>

»
4 months 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 :(

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months 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

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

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

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

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

»
4 months 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

»
4 months 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 :(

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

    a topological sort to decide the distance of closest point

  • »
    »
    4 months 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].

»
4 months 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! :-(

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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 :(.

      • »
        »
        »
        »
        4 months 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.

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

          thanks for trying your code is sooo clean.

          • »
            »
            »
            »
            »
            »
            4 months 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).

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

    I used bfs and I got accepted

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

      why does bfs not time out

      • »
        »
        »
        »
        4 months 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?

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

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

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

    I have the same problem as you

»
4 months 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.

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

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

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

    Powers of 3 work

  • »
    »
    4 months 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.

  • »
    »
    4 months 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$$$.

»
4 months 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

»
4 months 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.

»
4 months 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

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

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

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
My approach for C

Still WA on test 2 :( 149166751

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

    [Updated] Failing testcase: Ticket 1699

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 months 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

»
4 months 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 (╥_╥)

  • »
    »
    4 months 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.

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

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

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

    Put

    ios::sync_with_stdio(false);
    

    before reading the inputs, not after.

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

      thanks a lot! what a silly mistake of mine!

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

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

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

    In these cases, try to use custom invocation for testing

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

I got WA in C because of a typo :)

»
4 months 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

»
4 months 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

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

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

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

How to solve D?

  • »
    »
    4 months 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.

»
4 months 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 :(

  • »
    »
    4 months 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)

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

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

      • »
        »
        »
        »
        4 months 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

    • »
      »
      »
      4 months 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".

  • »
    »
    4 months 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:

»
4 months 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.

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

    Thank you so much! This is amazing!

»
4 months 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.

»
4 months 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

»
4 months 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.

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

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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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)]

      • »
        »
        »
        »
        4 months 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

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

      Thanks. Fixed a silly bug. Updated the comment.

      • »
        »
        »
        »
        4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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

»
4 months 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

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

chance to get specialist...

»
4 months 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

  • »
    »
    4 months 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

»
4 months 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?

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

when editorial will come.

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

When will the rating be changed?

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
4 months 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).

»
4 months 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 ?

  • »
    »
    4 months 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.

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

      The contest shows up as unrated in my rating graph. Maybe this one would go unrated.

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

Good luck

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

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

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

MikeMirzayanov I received Plagiarism on Problem A of this round with some guy I don't know . Logic for problem A was one liner how can i get plagiarism on this problem . please check again . Its my request to you.

»
4 months 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!

  • »
    »
    4 months 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!

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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 :(

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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.

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

.Finally rating changes after waiting hours..

»
4 months 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.

  • »
    »
    4 months 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 :)

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

downvote me plsss

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

The worst C problem I have ever solved.

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

This contest Is Very good for thinking