ch_egor's blog

By ch_egor, 4 weeks 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 V--gLaSsH0ldEr593--V, grphil, _kun_, VFeafanov, Sehnsucht, Sender, voidmax under my supervision.

Thanks to _kun_ 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_Red_Dates

  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_Red_Dates

  5. waynetuinfor

  6. dreamoon_love_AA

  7. danya090699

  8. KrK

  9. Farhod_Farmon

  10. PinkieRabbit

UPD3: Editorial

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

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

»
4 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

Why this unusual timing!

Have classes at the time of contest. :(

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

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

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Good luck & high rating!

»
4 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Once again with a hope to cross 1200

»
4 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

May I ask about the score distribution?

»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

What's the score for each problem?

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

all the best

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

Extended by 15 min?

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

why why wait more ..

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

15 minutes...

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

just the regular delay

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

delayed lol

»
4 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

Can't wait more!

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

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

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

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

What is the score distribution?

»
4 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

"6 problems"

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

6 == 7

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

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

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

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

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

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

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

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

      my code return 3

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

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

          my code return 3 this case too..

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

Good Job problem B setter!

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

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

    make the dsu tree and do a preorder traversal

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

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

How to solve C?

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

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

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

    Sort the array find out all the element whose indexes &1 and !&1. Seperate them all and put them with the following order: (!&1 indexes element (increase order)) (&1 indexes element (decrease order)). Thus, we have the following code in C++:

    include <bits/stdc++.h>

    using namespace std; typedef long long ll;

    define vi vector

    vi last; ll n; main(){ cin >> n; ll a[n+1]; for(ll i=0; i<n; i++) cin >> a[i]; sort(a,a+n); ll ans[n+1]; ll j = 0, z = n — 1; for(ll i=0; i<n; i++){ if(i&1) ans[z--] = a[i]; else ans[j++] = a[i]; } for(ll i = 0; i < n; i++) cout<<ans[i] << " "; } /* CODE BY MyNameIsHung */

  • »
    »
    3 weeks 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;
»
4 weeks ago, # |
  Vote: I like it -57 Vote: I do not like it

sooo booring A-F

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

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

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

»
4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    #define int long long int

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

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

      Signed overflow is technically undefined behavior.

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

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

What was the approach to solve problem B ?

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

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

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

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

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

    q1: YES

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

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

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

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

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

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

      test added to upsolving, thanks!

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

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

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

Easy problems, but I wa, wa, wa QAQ

»
4 weeks ago, # |
Rev. 2   Vote: I like it +39 Vote: I do not like it

The contest was a little bit unbalanced

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

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

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

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

»
4 weeks 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.com/contest/1131/submission/50389432

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

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

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

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

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

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

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

Will editoral be published?

»
4 weeks 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 :/

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

How to solve D?

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

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

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

»
4 weeks 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.com/contest/1131/submission/50382324

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

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

i have two id....97325 and mahedi_hasan...i have submitted the same code after being accepted...i didn't the rules properly....i have a messege from codeforces warning me....sorry for my submimisson the same code

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

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

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

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

        Because clear operation on vector doesn't free memory.

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

          Allright got it thanks :D

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Finally,i became an expert!!!

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem D is quite similar to this problem:Table Compression

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

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

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

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

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

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

»
3 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

很开心

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

happy