ch_egor's blog

Codeforces Round #541 (Div. 2)
By ch_egor, 6 years ago, translation, In English

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516).

Round will be held at 10:05 UTC on Saturday. You will be given 6 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by vintage_Vlad_Makeev, grphil, cdkrot, VFeafanov, Sehnsucht, Sender, voidmax under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Due to some last-minute changes, there will be 7 problems.

UPD2: Winners!

Div 2:

  1. Big_gold_date

  2. PinkieRabbit

  3. disposrestfuIIy

  4. Dobrobober

  5. szh0808

  6. prodakcin

  7. Argentina

  8. afedor

  9. bigelephant29

  10. Young25

Div.1 + Div.2:

  1. JustasK

  2. BigBag

  3. Egor.Lifar

  4. Big_gold_date

  5. waynetuinfor

  6. dreamoon_love_AA

  7. danya090699

  8. KrK

  9. Farhod

  10. PinkieRabbit

UPD3: Editorial

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

Comments Comments (123)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it -12 Vote: I do not like it

Happy Coding and high rating.

Hoped that everybody has good feeling

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

Why this unusual timing!

Have classes at the time of contest. :(

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

    We need intersection between official contest and round because we want to prevent cheating from onsite participants.

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

Perfect time for Chinese users! Finally we don't need to participate the contest at midnight! XD

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

Good luck & high rating!

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

Once again with a hope to cross 1200

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

May I ask about the score distribution?

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

What's the score for each problem?

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

all the best

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

Extended by 15 min?

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

why why wait more ..

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

15 minutes...

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

Why extended by 15 min?I can't Register it. :(

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

just the regular delay

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

15 min delay :((( why always me:?

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

delayed lol

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

Can't wait more!

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

I skipped school for this. hope i don't get disappointed. High rating for everyone :)

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

We want the 15 minutes delay in tomorrow's round to watch Liverpool Vs Man United match not in today's round :D

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

    C137 where is your Morty?

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

      Looking for Jessica

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

        Why don't you make a clone of her for his birthday like that robot that you bought him

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

    We want a 'Rick and Morty' special CF Round :D

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

Okay, I bunked my lecture only to find the round is delayed now. Rip my attendance.

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

What is the score distribution?

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

"6 problems"

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

6 == 7

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

Mmmmm... I love contestd like this. Yes, i LOVE contest with easy problem F.

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

    Silly me just looked at submission counts now, I spent most time on E thinking it might be not too hard :P

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

Solving C before B is the only good decision I have made in my life

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

Actual difficulty: A < B < C < F < E < D < G...
Btw, anyone knows about pretest 6 of D?

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

Its quite unusual to find an increase in the number of problems, due to last minute changes. Usually, problems are removed, but not added.

It can happen only on CF.

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

what is the testcase # 4 in B and # 7 in F..

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

    try this 4 0 0 1 1 1 1 2 2

    I fixed this case to pass test 4)

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

      my code return 3

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

        I got error at #8, then fixed for that but couldn't post in last 5 secs to see result: 3 2 0 3 2 3 4

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

          my code return 3 this case too..

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

Cool contest, but these difficulty estimates were all over the place. I think it would probably go ACFBDEG. None were too off except F. Was there some intended solution that didn't involve just stitching linked lists together?

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

    make the dsu tree and do a preorder traversal

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

    You can do it using only vectors. In order to unite 2 sets just append shortest vector to the longest one. Overall complexity will be O(nlogn).

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

How to solve C?

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

    i think sort -> element reallocation 0>0, 1>n-1, 2>1, 3>n-2, ...

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

    2, 4, ... , n — 3, n — 1, n, n — 2, n — 4, ... , 3, 1

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. sort the array in decreasing order(array a).
    2. take another array(array b).
    3. b[n/2] = a[0]; p1 = n/2, p2 = n/2;
    4. for(i = 1; i;){ p1++, p2--; if(p1 < n){ b[p1] = a[i]; i++; } if(p2 >= 0){ b[p2] = a[i]; i++; } }
    5. print b;
    → Reply
»
6 years ago, # |
  Vote: I like it -57 Vote: I do not like it

sooo booring A-F

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

Similar problem D.

https://open.kattis.com/problems/chesstournament

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

A bit mathforces...A stuck me 5 min and B stuck me 10 min...

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

    Would you prefer if two harder problems used math rather than two easier problems?

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

I have a weird solution for F.Could anyone help me to check it?

Build a tree similar to Kruskal rebuild tree.When dealing (xi, yi),add a new node,its two children are xi's highest father and yi's highest father.

After building,print the preorder traversal of the binary tree.Is that correct?

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

I had an issue with hacking some solutions for Problem A. The solutions used integers when defining all the variable of widths, heights, and the answer. However, I copied the solutions to my IDE, which they used the concept of areas that demands multiplication for sure, and tried hacking them on tests of 107 and 108 widths and heights, but the answers were all correct. How comes? why didn't the answers get overflowed?

Code example:

int w1, w2, h1, h2;
cin >> w1 >> h1 >> w2>>h2;
int s1 = (w1 + 2)*(h1 + 2) - w2 - (h1 * w1);
int s2 = (w2 + 2) * h2 - ((h2 - 1) * w2);
int s=s1+s2;
cout<<s;

Test example:

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

    #define int long long int

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

    They overflowed but then returned back. It's like you calculate answer modulo 231. Since it's always less than 231 it will be correct in the end.

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

      Signed overflow is technically undefined behavior.

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

    I am not sure, but in those particular cases the compiler could be doing some optimizations by removing the multiplication (it is possible).

    Even if that isn't the case, it still works. Consider that overflow is actually predictable. For example in this particular case:

    (10^7+2)*(10^7+2) - (10^7) * (10^7) = 316447236 - 276447232 = 4 * 10^7 + 4 as expected. The thing here is that when it overflows, you get "wrapped" around, i.e similar to taking modulo 2^32. For ex. 102 - 100 = 2 = 102 - 100 (mod 70), but 150 - 60 = 90 != 150 - 60 (mod 70) = 20. When the difference is small enough (smaller than the mod) you still get a valid result for the difference, no matter whether you take the mod (or overflow) or not.

    Of course you shouldn't rely on that because it is still UB per the C++ specification, but still.

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

What was the approach to solve problem B ?

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

    No. Of points such that x = y between coordinates (a,b) and (c,d) are max(0,min(c,d) — max(a,b) + 1). Just make sure to handle duplicates coordinates properly.

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

      can you explain, why this is correct ? Need a proof for the same.

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

        Consider a grid with topmost point (a,b) and bottom right point (c,d). There will be point whose coordinate x will lie in [a,c] and coordinate y will lie in [b,d].

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

Am I the only one who found D and F easier than C? :'(

Can someone provide a proof for optimality of the approach for C?

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

    q1: YES

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

    There exist a seq such that any gap will be at most 2 element, say a[7], a[5], a[3], a[1], a[2], a[4], a[6], call it (*).

    The largest difference in (*) is a[2] - a[1] or a[n] - a[n - 1] or a[i] - a[i - 2]. For the first two its clear that any sequence must be a difference larger of equal of that. For the last cases, if we don't want a[i] - a[i - 2] to appear, then we should insert something between them. Note it is a circle so we need consider transverse in clockwise and anticlockwise. Say if we insert a[i - 1] in one direction, then we must have a[j < i - 2] and a[k > i] meet somewhere in another direction. The difference a[j < i - 2] and a[k > i] is larger in that the largest difference in (*).So we cannot construct any better solution and (*) will be optimal.

    e.g. a[] = {1, 2, 3, 4, 100, 101, 102} we can write in 102, 100, 3, 1, 2, 4, 101. The largest difference is (100, 3). If we put 4 between them we get 102, 100, 4, 3, 1, 2, 101. Note the gap in another direction is bad and the largest difference is 101 - 2 = 99 > 100 - 3

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

Why is n in problem C so small?

It's very strange.

(Sorry to my poor English

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

    A funny solution: Binary search for the answer and use the Hungarian algorithm to check.

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

I hate A, B.

I solved 5 problems but lower than 4 solvers...

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

Is it actually possible to solve problem B in 2 hours?

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

F is gonna wreck my rating. But I solved D at least ...

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

At the last minute I decided to submit an extraordinarily crappy solution of problem F and it passed......

Can anyone explain why this passed?

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

    Probably cause there is no test like 

    150000 
2 1
3 4
4 1
5 6
5 1
...

    Which should result in TLE. Though you can easily make this solution O(nlogn) by merging smaller vector to larger instead of second one to first one

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

      Could you please tell me how merging smaller to larger vector gives O(nlogn)?

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

      test added to upsolving, thanks!

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

      My approach 50381829 which appends linked lists to each other (instead of copying a vector) while keeping track of the mostRight and mostLeft elements in each linked lists without keeping track which is smaller (But still doing path compression). Should it result in TLE too?

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

        No, your approach is same as DSU with path compression and according to this its O(NlogN)

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

Easy problems, but I wa, wa, wa QAQ

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

The contest was a little bit unbalanced

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

Problems A — C were around div 3 level, and problem D immediately jumped to div 1 level. Was this done on purpose?

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

    no cuz D is very standard.

    And there is a lot of problems similar to F

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

      I didn't get a chance to look at F during the contest, but it looks pretty easy to solve with DSU. I'm not sure about problem D though.

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

    D can be easily solved using DSU and Topology sorting.

    I think the difficulty of problem D is around D div 2 of usual Div-2 contests with 5 problems.

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

F can also be solved in O(n), for example we can maintain first element, last element, previous, next in each of the components and simulate accordingly in unite method.

http://codeforces.net/contest/1131/submission/50389432

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

    It's O(n*α(n)),btw I am the same solution

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

    Actually union find set with only path compression has the conplexity O(nlogn).

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

      right, but possibly a good alternative to storing list of elements in each components :)

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

Seemed the cf-predictor played a joke to me :/

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

The CF rating predictor is showing +86 while the actual rating change I got is +40 :/

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

How to solve D?

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

    D can be solved using DSU and Topology sorting.

    Firstly, if a(i, j) = '=' then join i and j + n to the same set. Thus, there can be at most n + m sets. Let's create a directed graph with n + m vertices, each vertex represents a set. Now if a(i, j) = '<' then connect an edge from head of set i to head of set j, a(i, j) = '>' otherwise. If we can't toposort this graph (i.e, this graph has cycles), then the answer is No. Also if two element i and j in the same set but a(i, j) != '=' then the answer is also No. Otherwise you can toposort the graph and find the answer easily.

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

    Also logN in overall complexity could be avoided by making a graph EQ with only '=' edges and finding CC's there instead of DSU.

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

Problem C is easier than B, but i did B first :(, and waste so much time to fix problem B. I just submit 1 time to ac the problem C

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

what is the problem with my code? (Problem F) https://codeforces.net/contest/1131/submission/50382324

It gets WA at testcase #7 which contains n=150000...

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

Can anyone please tell me why this solution(https://codeforces.net/contest/1131/submission/50393496) for F is giving me memory limit exceeded?

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

    You should merge to the cell with higher size.

    Also, vector::clear() doesn't free memory, if you want to to that, use

    vector<int> vec = {1,2,3};
vector<int>().swap(vec); //free memory from vec
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But why is it necessary to merge to the cell with higher size??? As after the merging operation the resultant vector in the both the cases will be of equal size.

      I could have agreed if the verdict was TLE but why is the verdict MLE.

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

        Because clear operation on vector doesn't free memory.

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

          Allright got it thanks :D

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

Finally,i became an expert!!!

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

Problem D is quite similar to this problem:Table Compression

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

Can someone explain the solution for F. I am not able to get it through editorial.

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

Can anybody please point out why my solution for F is exceeding time limit?

Thanks in advance!

50385034

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

In problem C, I pass the tests using an algorithm which I don't know why it is true, please help me. THX!

First, sort the array.

Second, binary search the minimum discomfort value.

Third, when I check whether a value is possible, let a[0] as a start point, a[n-1] as a end point, and I build one path from a[0] to a[n-1] using greedy method, then build another path using the remaining points. Thus I get a circle, finally I check whether this circle is legal.

Please see this submission for more details 50400061.

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

    By your check function, you decides that, sorting the array then destributing the elements with the way you mentioned, is the optimal way to reach the minimum discomfort value. So, firstly, you don't need to binary-search for the answer (mid value doesn't have effects on the work of the check function).

    The proof of the greedy method of the check function can be found in the editorial (or above in comments)

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

      I think the detail of the check function may differ from the method mentioned in the editorial.

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

        Sorry for that, if it's true, then I didn't understand what exactly is your greedy method.

        → Reply