.o.'s blog

Codeforces Round #233 Editorial
By .o., 11 years ago, In English

Please write here if you had written some comments about any suggestions or questions on the announcement. There are a bunch of notification emails but I couldn't read most of them :(

Here are the final top 100 : Div1, Div2. Congrats to the winners!

(These links are all from google search cache, so it may be disappear)

First of all, we are sorry to make this round unrated. This is an unexpected incident, and I believe that everyone in Codeforces would understand that. And second, we're sorry for estimating the difficulties of the problems wrong.

  • Actually, I thought that somebody would get Accepted on 398A - Cards within 5 minutes. But there wasn't any submissions during the first 4 minutes, and many people got wrong answer on pretests! I think almost everybody who solved this got at least one wrong answer.. I'm really sorry for measuring A easy. I think what cgy4ever said is right — it would be better not asking to print the sequence.

  • At first, I purposed 398C - Tree and Array as B(!!) because ainta solved it very easily than I expected. (I could hardly solve this, and thought it must be at least D, before I heard ainta's solution.) We're sorry for giving this problem the same score with 398B - Painting The Wall, which was much easier than 398C - Tree and Array. Next time I'll remember that ainta is really a genius :)

  • Congrats to four people who solved 398C - Tree and Array during the contest! : cgy4ever, Shef, SillyHook06, and Qwaz.

  • We are surprised that Petr solved 398E - Sorting Permutations during the contest! Even though he implemented by Java, his solution is faster than ours :p Congratulations to him!

  • Actually, we purposed an another problem for Div1-E, but the same problem popped out at OpenCup last Sunday, so we couldn't use that. Thanks to Gerald, who helped us preparing a new problem in such a short time. By the way, can you guess what problem was that? :D

  • ...

399A - Pages — Author : .o.

You can solve this problem by just following the statement. First, print << if p - k > 1. Next, iterate all the integers from p - k to p + k, and print if the integer is in [1..n]. Finally, print >> if p + k < n.

  • Time complexity: O(n).
  • Code : 5926588

399B - Red and Blue Balls — Author : xtalclr

Change the blue balls to bit 1, and blue balls to bit 0. Interpret the stack as an integer represented in binary digits. Now, one may see that a single operation decreases the integer by 1, and will be unavailable iff the integer becomes zero. So the answer will be 2a1 + 2a2 + ... + 2ak where the (ai + 1)-th (1 ≤ i ≤ k) ball is blue in the beginning.

  • Time complexity: O(n)
  • Code : 5926598

398A - Cards — Author : .o.

Let the number of o blocks p, and the number of x blocks q. It is obvious that |p - q| ≤ 1 and p, q ≤ n. So we can just iterate all p and q, and solve these two problems independently, and merge the answer.

1. Maximize the value of x12 + x22 + ... + xp2 where x1 + x2 + ... + xp = a and xi ≥ 1.

  • Assign a - p + 1 to x1, and assign 1 to x2, x3, ..., xp.
  • The value is (a - p + 1)2 + (p - 1).

2. Minimize the value of y12 + y22 + ... + yq2 where y1 + y2 + ... + yq = b and yi ≥ 1.

  • For all , assign to yi.
  • For all , assign to yj.
  • The value is .

The proof is easy, so I won't do it. With this, we can solve the problem. We can print y1 xs, and then x1 os, ...

  • Time complexity: O(n).
  • Code : 5926607
  • Bonus: Is there any solution faster than O(n)? We tried to use ternary search, but we couldn't prove that was correct.

398B - Painting The Wall — Author : ainta

This can be solved by dynamic programming. Let T[i, j] the expected time when i rows and j columns doesn't have any painted cells inside.

Let's see all the cases. If we carefully rearrange the order of rows and columns, we can divide the wall into 4 pieces.

  1. Choose a cell in rectangle 1. The size of this rectangle is i × j. The expectation value is T[i - 1, j - 1].
  2. Choose a cell in rectangle 2. The size of this rectangle is i × (n - j). The expectation value is T[i - 1, j].
  3. Choose a cell in rectangle 3. The size of this rectangle is (n - i) × j. The expectation value is T[i, j - 1].
  4. Choose a cell in rectangle 4. The size of this rectangle is (n - i) × (n - j). The expectation value is T[i, j].

Merging these four cases, we can get:

T[i, j] = 1 + {T[i - 1, j - 1] × i × j + T[i - 1, j] × i × (n - j) + T[i, j - 1] × (n - i) × j + T[i, j] × (n - i) × (n - j)} / n2

Moving the T[i, j] on the right to the left, we can get the formula which can be used to calculate the value T[i, j]. There are some corner cases, like i = 0 or j = 0, but it can be simply handled.

  • Time complexity: O(n2)
  • Code : 5926617

398C - Tree and Array — Author : .o.

There are two intended solutions. One is easy, and the other is quite tricky.

Easy Solution

Make a tree by the following method.

  • For all , make an edge between vertex i and with weight 1.
  • For all , make an edge between vertex i and i + 1 with weight .

You can see that are all good pairs. In addition, (1, 3) is also a good pair. So we can print the answer.

But, if n = 5, this method doesn't work because (1, 3) is not a good pair. In this case, one may solve by hand or using random algorithm.

  • Time complexity: O(n)
  • Code: 5926624
  • Bonus I: Is there any method to make more than good pairs?
  • Bonus II: Is there any method that the maximum weight is relatively small and make at least good pairs?

Tricky Solution

If you got stuck with the problem, one can run any random algorithm that solves small cases, and merge these cases. With this approach, we can even limit the weight to a very small constant!

But I think this is not a good solution, so I won't mention about unless anybody wants to know the details. I came up with this solution, and tried to purpose this as D. It seems all the 6 people who passed pretests during the contest didn't use this solution :)

  • Time complexity: ???
  • Code : 5926632

398D - Instant Messanger — Author : .o.

Let xi an integer representing the state of the i-th user. If user i is online, xi  =  1, otherwise, xi  =  0. Also, let Si the set consisting of i-th friends.

One can see that the queries become like this:

  • Online/Offline: change the value of xi to 1  -  xi.
  • Add: add u to set Sv, and v to set Su.
  • Delete: delete u from set Sv, v from set Su.
  • Count: calculate .

Let's use sqrt-decomposition to perform these queries. Let user u heavy if |Su| ≥ C, or light otherwise. Also, we will define some arrays and sets:

  • Hu is a set that stores friends with user u who are heavy users.
  • O[u] stores the sum of .

If the Online/Offline(u) query is given,

  • If u is a light user: for all , change the value of O[v]. It takes O(|Su|) time.
  • Otherwise: just update the state of itself.

If the Add(u, v) query is given,

  • If vertex u becomes heavy if we add this edge, for all , add v into Hw and update the value of O[w]. This can be done in O(C).
  • If vertex u is still light even if we add the edge, update O[v]. This can be done in constant time.
  • If vertex u is heavy (after the operations above), update Hv.
  • Add u to set Sv, and v to set Su.

If the Delete(u, v) query is given,

  • Delete u from set Sv, and v from set Su.
  • Update the value of O[*], Hu and Hv. Because for all |Hw| ≤  E| /  C, this can be done in O(|E| / C).

If the counting query is given, will be the answer. Because |Hu| ≤ |E| / C, it will take O(|E| / C) time.

So for each query, O(|E| / C) or O(C) time is required. To minimize the time, .

We can also solve this by dividing the queries into parts. For each block, use O(n + m + q) time to build the online & offline state and the answer table for each vertices. For each query, you can use time to get the answer. If you want more details, please ask in the comments.

398E - Sorting Permutations — Author : xtalclr, eyTns, and great help of Gerald

Here is the draft solution.

Feel free to ask of or discuss about the solutions! Unfortunately, I don't know how to read or write Russian, so if you ask me in Russian, I can't response to it. (also, I think the Russian editorial won't be available..) Sorry for that.

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

Comments Comments (44)
| Write comment?
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this editorial.... I hope the lost problems will add to the problem set as soon as possible~ I can't wait to test my code... because I solve none of problem in div1 during the contest.... Good luck ~ codeforces ~~

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

    It's up now,go and test your code!:)

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

pastebin is blocked by our government :(

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

    I generally think that the example solutions should be made available on Codeforces itself as submissions

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

      I used pastebin because Codeforces didn't set up the problems then. I changed the pastebin link to corresponding submission on Codeforces, so please check that. Thanks for your suggestion.

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

        I assumed as much :) Thanks for fixing that! B and C were very nice problems, by the way, thanks for that.

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

    paste.ubuntu.com is a nice choice....

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

    Excuse me,you've got a mail from Shunfeng Express.Please open the door:)

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

In problem D Div1, in the part about deleting operations: "Update the value of O[ * ], Hu and Hv. Because for all |Hw|  ≤  C, this can be done in O(|E|  /  C)." shouldn't it be |Hw| <  = |E| / C?

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

In problem D, I've got TLE in test case 48 using a similar approach with sqrt-decomposition. Am I doing something wrong or could I do something better? Or is the time limit too tight? :/ Here is my submission: 5926156. Many thanks!

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

    Same here, TLE on Test 35, with a algorithm, where |E| is the number of total edges that were ever added. I think the time limit is just a bit too strict, since I could only do constant optimizations from that point.

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

      Sorry for the strict time limit. We had several codes implemented by three authors, and the slowest accepted solution took only 450ms. That's why we have set the time limit to 2 seconds. We didn't test unordered_set solution because we didn't know how to compile C++0x code on Polygon :p

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

    Actually, your solution is not , but . Let's assume that currently the counting query is given, and the vertex is light. There will be at most neighbors of the vertex. You stores them in a set, and iterates all of them. To avoid TLE, you should reduce the factor from the time complexity.

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

398A — Cards, second paragraph: For all 1<= i <=(x mod q)... — what is x here?

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

    It's b, I'm sorry. I modified that part.

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

In "If vertex u becomes heavy if we add this edge, for all , add v into Hw and update the value of O[w]. This can be done in O(C). " shouldn't be "add u into Hw " ?

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

When will the tutorial for E be available? Really looking forward to it!!

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

    Sorry, the author of E had forgotten to write the editorial, and said that it will be available within 2-3 days.

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

      Really appreciate the efforts from you guys.

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

    Thanks for your patient and kindness. I just uploaded a draft version of the editorial for 1E here. It contains the solution when there is no hole inside the permutation. I'll finish it up tomorrow.

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

hi, i am upset with this editorial, it should be more specific and easier to understand, because there are people like me that are really new to contests and are not very familiar with math notation/problems (in my country math is poorly teached), so i got confused by the solution of for example problem C (i solved problem B but this explanation is really weird) which just trhow a lot of things and say: "its obvious that, its easy, its so easy to prove that i will not bother" then do not bother on making an editorial "explaning" the solutions, you guys need to understand that there are people that wish to learn and are really new to the competitive programming, i mean i have learned a lot from this site, but it just bothers me when the editorial is so torwards people that already know their thing.

Well thats all, sorry if i am being rude, but its getting harder and harder to learn nowadays when everything seems to be so obvious that it doesn't need an explanation.

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

    Sorry for the inconvenience I have caused. I thought the editorial was a short guideline to refer when I couldn't solve the task, and writing many details is not appropriate. If you want, I will write a new post with some mathematical proofs and details of this editorial.

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

      In Problem 398A-Cards. Please help me understand why "It is obvious that |p - q| ≤ 1" ?

      And in the solution here http://codeforces.net/contest/398/submission/5926607 why are we taking n as min(a, b) ?

      Thanks.

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

        Sorry I got why |p-q| <= 1. But I still didn't get why are we taking n as min(a,b) ?

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

          First, we should notice that p ≤ q holds for all cases except b = 0. If p > q, the deck will look like "oooxxxxoooxxx..ooo". We can increase the value by moving any "x" block to the front or to the back.

          So we can conclude that p ≤ min(a, b) because p ≤ a, q ≤ b, and p ≤ q.

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

didnt participate this round in real. i finally took part in it as virtual contest yesterday. problems and tutorial are both very attractive and heart-devoted. thanks a lot,tncks0121

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

Maybe there is a small mistake in Div.1 A. I think that value is (b/q + 1)^2 * (b % q) + (b/q)^2 * (q — b % q) rather than (b/q + 1) * (b % q)^2 + (b/q) * (q — b % q)^2.

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

    Sorry for checking the comment too late. You're right, and I modified that part of the editorial. Thanks for your help!

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

May anyone elaborate the solution of — painting the walls.

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

    Can someone please explain in problem-Painting the walls, why rearranging the rows/columns is necessary and why rearranging does not affect the final answer?

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

Nice Editorial ! thanks .o.

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

Thanks for this editorial. :)

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

In problem D. Instant Messanger, in the submissions detail, it seems to be another solution which is shorter and faster. The link of the submission is here. Can someone give me the time complexity analysis of this code ? Thanks in advanced <3 <3.

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

    I also wonder about the time complexity :<. Could anyone clarify this?

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

    Anybody... :<

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

    Sorry for spamming :< But if anyone is gonna help me ... :<

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

What a pity... Because of the memory limit, Problem D can't be easily solved by using bitset(which needs at least 300MB)

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

    Upd: I successfully solved problem D by using bitset! Here are my solutions:

    Firstly, we set M = 50000, and you just need to maintain bitset<M> B[M] and bitset<M> s:
initialization: for each x, set s[x] = 1; for each a b, set B[a][b] = B[b][a] = 1;
query:
O u: s[u] = 1;
F u: s[u] = 0;
A u v: B[u][v] = B[v][u] = 1;
D u v: B[u][v] = B[v][u] = 0;
C u: print (B[u] & s).count();

    However, this solution need memory out of the limit 256MB. Thanks to emofunc, she told me to solve this problem offline: you can just maintain bitset<M / 2> instead, and you just need to repeat the algorithm 2 times, like this:

    initialization: if (x < M / 2) s[x] = 1, if (b < M / 2) B[a][b] = 1, if (a < M / 2) B[b][a] = 1;
query:
O u: if (u < M / 2) s[u] = 1;
F u: if (u < M / 2) s[u] = 0;
A u v: if (u < M / 2) B[v][u] = 1, if (v < M / 2) B[u][v] = 1;
D u v: if (u < M / 2) B[v][u] = 0, if (v < M / 2) B[u][v] = 0;
C u: the answer for this query += (B[u] & s).count();
Then clear all B and clear s;
initialization: if (x >= M / 2) s[x - M/2] = 1, if (b >= M / 2) B[a][b - M/2] = 1, if (a >= M / 2) B[b][a - M/2] = 1;
query:
O u: if (u >= M / 2) s[u - M/2] = 1;
F u: if (u >= M / 2) s[u - M/2] = 0;
A u v: if (u >= M / 2) B[v][u - M/2] = 1, if (v >= M / 2) B[u][v - M/2] = 1;
D u v: if (u >= M / 2) B[v][u - M/2] = 0, if (v >= M / 2) B[u][v - M/2] = 0;
C u: the answer for this query += (B[u] & s).count();
Finally, print answers for each query C u.

    By doing this, the memory cost divided by 2. So it can suit the memory limit.

    Here are my code: 149867906

    → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me in problem D, why |h[w]| <= |E| / C ? Because as I understand, it can show that |h[w]| > |E| / C exists. For example, with 502 nodes, each node is connected to each other, so that each node is heavy. That means when we have a query about C x, we need to (for) all the nodes which connect to x, which means not O(|E| / C) anymore. Why:(

→ Reply