HolkinPV's blog

Codeforces Round #224 (Div. 2) Editorial
By HolkinPV, 11 years ago, translation, In English

382A - Ksenia and Pan Scales

This problem is just a technic problem. So, you should take weights one by one and place the current one into the side of the scales that contains lower number of weights. At the end you should output answer in the correct format.

382B - Number Busters

In the problem you should understand, what is the structure of Artur's operation. You can see that this operation is near operation (b + x) % w (To see that just apply b = w - b - 1). There is nothing hard to get the formula of changing a during the operation. So, if you have k operations, you can see, that b = (b + k·x) % w, a = a - (b + k·x) / w, c = c - k. When you've got all the formulas, you can solve the problem using binary search.

382C - Arithmetic Progression

This problem is about considering cases:

1) If n = 1, the answer is -1. Because of any two numbers is arithmetical progression.
2) If array is constant, the answer if that constant.
3) If you have arithmetical progression initially, you can compute its difference d. In this case you should just to output minVal - d, and maxVal + d, where minVal is minimum value among a[i], and maxVal is maximum value among a[i]. But in case of n = 2, also you should check (a[0] + a[1]) / 2. If this number is integer, it is needed to be output.
4) Else, the answer has at most one integer. You find this integer you should sort the sequence, and find the place where the number is missed. If such a place exists you should add the corresponding number to the sequence, else, the answer is 0.
5) In all other cases the answer is 0.

382D - Ksenia and Pawns

In this problem from every cell except # there is one next cell. That's why this graph is almost functional graph. If this graph contains a cycle, then answer is -1 because the length of the cycle is at least two.

In the other case, there are no cycles in the graph. Let's find the longest path in it, denote is as len. Then is answer is at least 2·len - 1 because we can put the two pawns in the first two cells of this path.

But in some cases we could get the answer 2·len if there are two non-intersecting by vertices (not #) paths of length len. They are non-intersecting because if they intersect in some cell then they will be equal to the end (and the statement says that such moves are invalid).

So, we should check if the graph contains two non-intersecting by vertices (not #) paths of length len. It could be done in any way. For example, using dfs searches.

382E - Ksenia and Combinatorics

In this problem you should count trees with some properties. It can be done using dynamic programming. The main idea is that the maximum mathing in tree can be found using simple dynamic dp[v][used] (v -- vertex, used — was this vertex used in matching). So you should to count the trees tou should include in state of the dynamic values dp[v][0]$ and dp[v][1].

In other words, you should use dynamic programming z[n][dp0][dp1] — number of rooted trees with n vertices and values of dynamic in root dp[root][0] = dp0 and dp[root][1] = dp1. But in simple implementation this solution will get TL. There are two ways to get AC. The first is to opltimize code and make precalc. The second is to optimize asymptotics.

The author's solution uses the second way. To optimize solution you should mark that values dp0 and dp1 differs at most by one. That is dp0 = dp1, or dp0 = dp1 + 1. So the first dynamic becomes r[n][dp0][add]. Another optimization is there are not so many triples (n, dp0, add) with non-negative values (about 250), so you can you use lazy programming to calculate this dynamic.

Comments that describe other solutions:

http://codeforces.net/blog/entry/10423#comment-158177
http://codeforces.net/blog/entry/10423#comment-158182

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

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

when input 2 3 3 the answer is 1 3 why it's true? the answer 3 3 3 3 also correct i think

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

    The statement implies that all numbers should be distinct.

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

    No, you're asked to find the number you can put on one card, regardless their position, so 1 3 is correct since you can place it anywhere within the sequence.

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

Very fast tutorial, thanks!

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

    Very fast (incomplete) tutorial, thanks!

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

This was my first contest and I'm unrated. How long does it take for the ratings to show up ?

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

for problem C, i feel that the the case where (a[0] + a[1]) / 2 also had to be included in the answer could have been omitted from the pretests (or atleast from the examples), as a good number of participants may not have seen that.

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

5716844

I solved Problem B in a quite different way.

（I'm not sure if it's absolutely correct,and sorry for my poor English）

if b ≥ x, perform the assignment b = b - x

if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)

Let's define the b ≥ x one as operation A,and the other operation B

You may notice that a and c seems works as counters，and (c-a)gets smaller after operation A,(c-a) won't change after operation B

Define the times doing operation B as k

So the time Alexander gets ahead of Arthur is c-a+k

Also,you can easily find that the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)

So,now we have a formula

(b+kw)/x=(c-a)+k

we can get:

k=((c-a)*x-b)/(w-x)

and now we can get the answer by calculating ceil(c-a+k)

However,the (c-a)*x can be very large,bigger than INT_MAX.So,we should use long long.(That's why I made two Wrong Answer submissions)

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

    I can't get neither this nor author's solution for B :(

    "the time Alexander gets ahead of Arthur can be also described as ceil((b+kw)/x)"

    Why is it so?

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

      Well another approach is using dfs and finding cycles.

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

      Sorry for the trouble I caused.I forgot to explain that,and I may have made a mistake.

      operation B says，if b < x, then perform two consecutive assignments a = a - 1; b = w - (x - b)

      It's a little tricky

      b=w-(x-b)=b+w-x

      Which means,In operation B,we also did minus x.And we only add w for k times

      So no matter which operation we did, b always -x.

      If we don't -x during each operation B,b will be (b+kw) after k operation B.

      And (total times minus x)*x is supposed to be smaller or equal to (b+kw).

      (After a second thought, I think we don't need a ceil() here)

      So (total times minus x)<=(b+kw)/x

      So (c-a)+k<=(b+kw)/x

      So k>=((c-a)*x-b)/(w-x)

      Since We want to find the minimum time ,k=((c-a)*x-b)/(w-x)

      What should we do if k is't a integer?We can't do a half of operation B

      k=ceil(((c-a)*x-b)/(w-x))

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

        Wow,That was an awesome solution. I really liked your idea.

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

        Finally understood :D. Thanks so much!

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

      hi, look here http://codeforces.net/blog/entry/10423 for the explanation of clp012345 is a good one.

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

    i first use binary search , but WA twice . then in the last five minutes i try nearly the same algorithm with you then AC. lucky! k=((c-a)*x-b)/(w-x)

    for(int i=k-10000;;k++) { when i find a i,break. }

    i find that my bsearch is wrong just because the right need to be larger than 2000000000000LL a simple mistake takes me nearly all the time……

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

    我猜这个你能看懂

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

      What do you hope to achieve by posting something that the vast majority of people here can't read?

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

      Chullu bhar pani mein doob mar yeh samajh mein aa jae to batana

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

my solution for B is completely different from author`s

notice that 0 <= b < w <= 1000, this means that we had a cycle on b, so find it and compute its length and delta -- count of decreasing c (without a). now we can say how many times we should pass this cycle and then pass one more time for end. It works O(w)

5725480

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

Let me state another solution for problem B. The key observation is that both b=b-x and b=b-x+w are equivalent modulo w, and number b is always going to lie in [0, w-1]. So each operation means taking (b-x) instead of b (modulo w). So if we look at the reminders mod w, the sequence becomes b, b-x, b-2x, ..., b-kx, ... Now it's clear, that there is going to be a period P (we can find it via simulation in O(w) initially or notice that it's just the minimal p : b-px=b(mod w), or px=0(mod w), or p = w / gcd(w, p).). Also we should calculate the decrease of a variable "a" in this period — call it S.

Now, we can calculate the decrease of a variable a in X steps the following way: If X <= P, then it's just a simulation in O(P). Otherwise, it's just S*(X/P) + simulation of (X % P). Clearly, it works in O(P) which is also O(w).

All that left is a binary search: obviously, c always increases, while a increases just sometimes. So once c<=a is satisfied, it's gonna stay like that all the time afterwards.

Hopefully it's clear :)

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

    px = 0 (mod w), then p = w/gcd(w,x), not p = w/gcd(w,p). Anyway, thank for your clear explanation!

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

      That's right, sorry for the typo :)

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

may someone explain solution for D?, thx

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

    The problem can be formulated in terms of directed graphs: each cell is a vertex, it has outdegree 0 if it's '#' (let's call those vertices endpoints) and outdegree 1 otherwise, with the only outgoing edge pointing to the cell that a pawn moves to from it.

    If there's a cycle in this graph, the answer is -1.

    Otherwise, the path from every cell must end in an endpoint; notice that the graph is, in fact, a forest of trees rooted at endpoints. For every such tree, you can count (BFS, DFS, whatever you wish) its depth in its tree, which is equal to the number of moves, and the last vertex on the path from it before the root.

    Now, you can only put pawns in vertices which either have different depths or "last" vertices, or they'd meet on a non-end vertex; think why it works. For different depths, it's simple: just find the largest (a) and second largest (b) depth overall. If you want to choose 2 vertices with the same depths, both must be equal to a or it won't be better than a + b; that means you can choose a vertex v with depth a, iterate over all vertices with depth a and iff you find one with "last" different from last(v), then there's a better solution 2a. Just check all those possibilities.

    The time for this is O(NM).

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

Thanks for fast editorial.. But what about 382D and 382E?

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

Although I pass the problem b,I can't understand your explaination. I use the pigeonhole principle and have a way to solve it in o(2*x). Could you explain that how to get these formulas in details? Thank you very much.

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

    Could you please explain how have you used pigeonhole principle in problem B?? Thank you

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

      First,you should find the if the datas is enough big,the value of b will repeat.So it's easy to see that the value of b will repeat at most of x times. For example,if you use a array[x] to record the value of b when it appear,it must have one of the array[x] to equal 2 and that means b repeats. So we just need to use the value to devide the remain of a,and then caculate at most x times to get the answer.

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

Can someone please help me understand why this submission of mine for problem A gives WA at test 5.

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

Problem D i Got MLE in test 35

please help,though my array is arr[2000][2000] it shows MLE solution

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

For problem C: I have a test case for which my solution which got accepted will fail and I have no idea how many other solutions will fail

test case

my code : 88891597

expected 0 , output 1 => 5

HolkinPV I think this test case should be added. maybe only my solution fails.

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

Alternative approach for Problem C: Let, l=last term of A.P a= First term of A.P d=Common difference Then, n( Required number of terms) = (l-a)/d+1 and Sum of all terms = [n*(l+a)]/2

Using difference of sum of actual array and desired sum(computed using parameters l,a and d) gives us the left element(which must be included to make all elements of array follow the Arithmetic Sequence for given a,l and d. Ambiguous cases need not be worried out, all such cases can be judged as they don't follow the mathematical equations mentioned. https://codeforces.net/contest/382/submission/104538828

→ Reply