Блог пользователя ch_egor

Автор ch_egor, 6 лет назад, По-русски

Всем привет!

В эту субботу пройдет московская олимпиада школьников по программированию для 6-9 классов. Над туром работала Московская методическая комиссия, известная вам также по Открытой олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516).

Раунд состоится в 13:05 23 февраля. Вам будет предложено 6 задач и 2 часа на их решение. Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут написать контест вне конкурса.

Задачи соревнования подготовлены vintage_Vlad_Makeev, grphil, cdkrot, VFeafanov, Sehnsucht, Sender, voidmax под моим руководством.

За координацию раунда и перевод условий спасибо cdkrot, а так же MikeMirzayanov за системы Codeforces и Polygon, который использовался при подготовке задач этой олимпиады.

Всем удачи!

UPD1: Из-за решений, принятых в последний момент, в раунде будет 7 задач.

UPD2: Победители!

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: Разбор

  • Проголосовать: нравится
  • +203
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится -12 Проголосовать: не нравится

Happy Coding and high rating.

Hoped that everybody has good feeling

»
6 лет назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

Why this unusual timing!

Have classes at the time of contest. :(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +91 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +119 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Good luck & high rating!

»
6 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Once again with a hope to cross 1200

»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

May I ask about the score distribution?

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

What's the score for each problem?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

all the best

»
6 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Extended by 15 min?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am new at this site. Does I participants this?

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    If you are registered onto the contest you are participating.

    But until you did any submissions the rating wouldn't count for you

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Опять задержка(((

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

why why wait more ..

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

15 minutes...

»
6 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

just the regular delay

»
6 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

delayed lol

»
6 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Can't wait more!

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the score distribution?

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Узнаю олимпиады, которые проводятся в Москве. 15 минут это только начало...

»
6 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

"6 problems"

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

6 == 7

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    make the dsu tree and do a preorder traversal

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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;
»
6 лет назад, # |
  Проголосовать: нравится -57 Проголосовать: не нравится

sooo booring A-F

»
6 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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?

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

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
  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    #define int long long int

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the approach to solve problem B ?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    q1: YES

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

    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

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

Why is n in problem C so small?

It's very strange.

(Sorry to my poor English

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I hate A, B.

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

Can anyone explain why this passed?

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    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

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Easy problems, but I wa, wa, wa QAQ

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

The contest was a little bit unbalanced

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    no cuz D is very standard.

    And there is a lot of problems similar to F

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.me/contest/1131/submission/50389432

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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
    
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Finally,i became an expert!!!

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Problem D is quite similar to this problem:Table Compression

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Thanks in advance!

50385034

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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