cdkrot's blog

Editorial of Codeforces Round #567 (based on All-Russian olympiad in the name of Keldysh)
By cdkrot, history, 6 years ago, translation, In English

Thanks for the participation!

1181A - Chunga-Changa was authored by vintage_Vlad_Makeev and prepared by achulkov2

1181B - Split a Number was authored by Endagorion and prepared by manoprenko

1181C - Flag was authored and prepared by budalnik

1181D - Irrigation was authored by Helen Andreeva and prepared by ch_egor

1181E2 - A Story of One Country (Hard) was authored by voidmax and prepared by voidmax and alexey_kuldoshin.

And now the editorial:

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +84
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
»
6 years ago, # |
  Vote: I like it +91 Vote: I do not like it

No doubt E is very cool, thank you for this round!

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

It is very convenient to use Python to solve B but I'm not good at it. Learning several different languages seems important.

Anyway, thank you for your amazing problems!

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

    I used python to solve the problem But I'm stuck in the case when the leading zeroes come. Can someone help me with that ?.

    My submission is 55661488

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

      Hey, there are two things you can do over here.

      1) Slice at the middle, then slice at the nonzero number to the right of middle & similarly to the left. (As explained in the editorial)

      2) Since you use python you can partition at every possible place and check the right half doesn't start with zero. And finally, return the minimum sum of both halves.

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

Does there exist a stack based solution to 1181C, similar to how SPOJ — HISTOGRA is done? Both questions look very similar, hence my question. I tried but couldn't figure out anything.

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

    the problem is that you have here various color so you have to go through a series of corner cases and handle a lot of if-else to do stack implementation. I don't know but it should be really complex if it exists.

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

It seems that there's another solution for problem D, without tree data structure. https://mirror.codeforces.com/contest/1181/submission/55650482 Could someone explain how it works?

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

    I'll try — imagine a rectangle with width M and infinite height. Every year you color one cell of this rectangle, going bottom to top and left to right. The column you color corresponds to the city in which the olympiad happens — so in year T you will color city (T mod M) by this process.

    The problem is that some N cells are already colored. The coloring proceeds normally, except you skip colored cells. So for a given T, all you want to find is the number of cells you skip. This can be done by sorting these cells in the order in which they would be filled normally, and then binary search.

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

      1.Can you please provide the code?

      2.Will the time complexity be O(q*log(n)*log(m))?

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

        1. If you want you can check my code, using same idea — 55705590

        2. Complexity is O((n + q)*log(n)).

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

      in regards to (above mentioned solution) this , can you please explain these two lines

      1. for(i=1;i<=n;++i) lst[i]+=n-i;

      what is the purpose of adding "n-i" to every lst , and what values will "lst" will hold after this.

      1. ans=lower_bound(lst+1,lst+n+1,t)-lst; ans=t-(n-ans+1);

      how is this calculating answer

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

    did u get how is this code working ?

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

Can Anybody explain this statement for Problem D :- "If we subtract from k (the query parameter) the number S of cells painted in previous rows, then we simply need to return the (k−s)-th element in this set." Thanks in advance.

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

    Think in terms of time. S time at which last merging occurred and query time is current time.

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

Could anybody explain what the solution for Problem E(hard version) works? What's the meaning of Let's sort rectangles using all 4 possible sortings. And let's iterate over all this sortings simultaneously. and the sentences after it? Thanks a lot.

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

    core idea is to find valid cut in O(x) (seems that there's a typo in editorial?) by sorting in 4 directions (left to right, right to left, top to bottom and bottom to top) and go through these arrays simultaneously until you find a valid cut or you have gone through all those arrays.

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

      So x is a constant number that doesn't depend on n? And we go through these arrays at the same time to find the valid cut? (Then we can turn the problem to a small but similar one and go into recursion)

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

        "x is a size of one part of the cut" if i get it right. besides, for what we are going to do when we find a cut, it's described in the second last paragraph

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

          Thanks. I understand the solution better after asking you.

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

getting runtime error on test case 10 in problem D. https://mirror.codeforces.com/contest/1181/submission/55675351

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

    Years can be upto 10**18. Try changing int to long long.

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

    i dont think your code would promise count<=1e6 so that "result[x-n]" might overflow. you could try your code with the following test case:

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

      Yes I think you are right thanks. Can you suggest something to avoid that.

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

Very interesting contest and hard at the same time! Congrats to the organizers. Can you please put solutions for every problem? The problems are well explained without a doubt, but it will be very helpful.

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

can some one explain how to solve problem C in details

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

    First, find the number of same coloured cells to the right and bottom of each cell(plain dp). Now for each cell, check the row number of next colour and row number of next next colour along the same column. Find the maximum width of the rectangle by performing range query(segment tree).

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

      i understand the segment tree part but how to code it using dp (recursive is the only dp type i know and the iterative summation) did you solve it like that can you share the code

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

    take a dp matrix to know the number of same coloured cells from top to bottom. then, try to find a series of cases to do counting. here I am giving the code(try to understand the cases from line 39). here is the code. https://mirror.codeforces.com/contest/1181/submission/55669150

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

Who know how to solve D by using segment tree? Why not use priority_queue?

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

    We understood, that the next olympiad will take place in the k-th city(we will assume, that cities which can organize the olympiad sorted by their number). now we will talk about segment tree. Vertex in this segment tree will responsible for how many cities form l to r can organize the olympiad.Consider you are in the vertex v, and the olympiad will take place in either of cities from 2 * v, or 2 * v + 1.If the value of the vertex 2 * v larger than k, it means that there is no point in looking for k-th city in vertex 2 * v + 1.In other case we will check vertex 2 * v + 1, instead of vertex 2 * v.

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

      Please explain how to get k-th city. I could not understand anything from the D editorial. I am struggling with the problem for so long. :/

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

        Me too. I don't get anything from the D editorial :<

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

hardes part was implementation, please more constructive and greedy problmes rather than implementation. in B

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

Can anybody explain me the editorial of Problem C ? I am getting a hard time to understand it.

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

    I have an idea that you can consider the effect of each cell as the lower right corner on the answer.my submission

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

What is the idea behind this implementation of D(without using tree data structures). https://mirror.codeforces.com/problemset/submission/1181/55665170

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

for problem B what would be output for the following input

6

100001

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

I did problem B with C++. I think it works perfectly. But I'm getting wrong output format for test case 9. Here is my submission 55812911. Can anyone help me out, please?

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

    the same problem. Did u find a solution?

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

      I don't know why but using the string.substr() function solved my problem.

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

enjoyed this contest thank you !

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

Could explain in more details the solution to problem D ?

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

    After several long long hours of reading code of hundred of people, I finally have figured it out. You can read the easiest-to-understand-code-for-me I have found here .

    I think you should try as hard as possible to understand it (draw the segment tree, run that code with some test and try to understand it) as you will learn a lot when you yourself can figure it our on your own.

    But if you still struggle with it, just message me I will explain it for you.

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

Some confusion about Test case 3 of problem E

First I calculate the total area of all rectangles the result is area = 999999208300485319 Then I found the target boundry which is Left = 0,Right = 999999997,Down = 3,Up = 999999998 However the target area is not the same as total area But the answer is YES. Why? Am I wrong?

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

Hello, For problem E

I have submit my solutions several times and cannot get accepted, I doubted there is something wrong with the standard program.

Here is one case.

2

1 1 2 2

3 1 4 2

The answer for this case should be NO. However the accepted solution returns YES.

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

In problem E2, can anyone come up with a case where you can only cut off $$$O(1)$$$ rectangles each recursive step, causing the $$$O(n^2)$$$ solution for E1 to fail? I couldn't find such a counter case so I submitted my solution to E1, and got TLE as expected.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, the sentence "if we replace set of rectangles with its subset, it only can make better." is intuitive but very much far from obvoius. The editorial didn't give any alternative characterisation of being a nice subsets that make this clear.

A good cut is a cut that does not cross any given rectangular area.

Here is a proof: Use strong induction. Suppose we have a working plan that makes A as the first cut. We have another a cut B. We want to obtain a working plan that starts with the cut B instead. If A and B are in the same direction, then we B must still be a valid cut in one of the parts after A, so we can apply induction. Otherwise, if the cut A produce two parts X,Y, then observe that B is still a good cut with respect to X and Y, so we can use strong induction, and obtain plans for X and Y that starts with B. We can now merge these two plans into one plan that start with B.

→ Reply