Yury_Bandarchuk's blog

Editorial Codeforces Round #332 (Div. 2)
By Yury_Bandarchuk, 9 years ago, translation, In English

Problem A.

Everything that you needed to do — solve some similar cases.

You need to check the following cases:

  • Home the first shop the second shop home

  • Home the first shop the second shop the first shop home

  • Home the second shop home the first shop home

  • Home the second shop the first shop the second shop home

Time: O(1)

Problem B.

First of all, you should read the statement carefully. Then, for every element 1 ... N create a list of integers from what we can get this number.

After that you have to check some cases, before that create a special mark for answer Ambiguity:

Let current element of the given array is bi

  • If two or more elements exist from which it's possible to get bi, then use your special mark that answer is Ambiguity
  • If no elements exist from which it's possible to get bi, then print Impossible
  • If only one element exists from which it's possible to get bi just change bi to the value of this element

Finally, if you marked your special mark then print Ambiguity, else print Possible and correct answer.

Time: O(N)

Problem C.

Let's take a minute to see how the best answer should look like.

Let Hi be a sorted sequence of hi. Let E — set of indices of the last elements of each block. Then e E, first e sorted elements of sequence hi are equal to the first e elements of the sequence Hj.

So, it is not difficult to notice that the size of E is the answer for the problem.

Firstly, we need to calculate two arrays: prefmax and suffmin, where prefmaxi — maximum between a1, a2, ..., ai, and suffmini — minimum between ai, ai + 1, ..., an.

If you want to get the answer, just calculate the number of indices i that prefmaxi  ≤  suffmini + 1.

Time: O(N)

Problem D.

First of all, let's solve this problem for n ≤ m, and then just swap n and m and print the answer. Important! Not to print squares twice!

We can use this formula for fixed n & m (n ≤ m) for calculating the value of x.

Then

Using the sum squares and the sum of the first k numbers we can easily solve this problem.

Getting 6x = 6n2 * m - 3(n2 + n3 - nm - n2) + 2n3 - 3n3 + n = 3 * m * n2 + 3 * m * n - n3 + n

As we solved this task for n ≤ m the 3n2 * m =  ≈ n3, it means that n is not greater than .

Time:

Problem E.

The solution for this problem is dynamic programming.

Let froot, mask is the number of ways to build a tree with root in vertex root using vertices from the mask mask and all restrictions were met. For convenience we shall number the vertices from zero.

The answer is f0, 2n - 1.

Trivial states are the states where a mask has only one single bit. In such cases froot, mask = 1.

Let's solve this task recursively with memorization. To make the transition, we need to choose some kind of mask newMask, which is necessarily is the submask of mask mask. Then we should try to find new root newRoot in mask newMask. Also, in order not to count the same tree repeatedly impose conditions on the mask newMask. Namely, we shall take only such masks newMask, in which the senior bit (not in charge of the root) coincides with a senior bit (not in charge of the root) of the mask mask. After that, you need to check the fulfillment of all conditions to the edges and to the lca. If everything is OK, update . Where means xor.

What about checking lca, it's possible to do it in time O(N2) — previously memorized lca for each pair or in the worst case in time O(Q) just iterating through all pairs of vertices, for which some vertex v is lca.

Time: O(3N·N3) or O(3N·N·Q)

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

Comments Comments (66)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by Yury_Bandarchuk (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Yury_Bandarchuk (previous revision, new revision, compare).

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

    sorry, in problem C when you say H_j is H_i right?

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

Thanks for nice editorial and nice contest :)

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

Problem A: this line min(d1, d2) + min(d3, d1+d2) + min(d3+min(d1, d2), max(d1,d2)) solves it.

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

    what about ? :) min(a,b+c)+min(c,a+b)+min(b,a+c)

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

    I've made a visual explanation for the problem A.
    If you guys have any suggestions for improvement, you can comment my explanation right here :)

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

In the problem D don't we search n in the range [1 X^1/3] and then for each n, m in the range [n,x^1/3]? Is overall complexity O(x^1/3) or O(x^2/3)?

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

Problem C:

I solved it in nlog(n):

I will illustrate on this example:

4 3 4 1 2

  • first, I sort the array keeping the index of each element with it as a pair. the resulting array will be like this:

(1,3) (2,4) (3,1) (4,2)

and then iterating through this array and know each element should go from where to where (so this segment must be sorted as one partition). For example:

element with value 1 must go from index 3 to 1, so segment(1,3) must be updated.

for Every such segment I either: 1- insert it into a set. 2- if it intercepts with other existing segment in my set, I update both of them into a new segment.

for example: first I insert segment (1,3), then it comes (2, 4). I merge both into one segment which it is (1,4).

lastly, I get the number of segments seg and the total elements they have in them tot, and answer is seg+n-tot

my code: 14383376

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

    Hey! I did it in the same fashion :)

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

      I think we solved it the hard way :) there are simpler solutions.

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

    Another nlogn solution 14416195. I think you will find this easier. The code is so short and simple that i don't need to explain what i've done (i guess).

    It was my contest time submission 14381758 too. but i resubmitted it to reduce unused codes.

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

Fastest system testing ever! And super fast editorial. Great job. Ciao.

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

Problem D — Spongebob and Squares is a beautiful problem, kudos to the author

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

I think there is much nicer/easier solution for problem C. I think it work?

Say you have the array elements a1, a2, ..., an. Then, call them sorted be b1 ≤ b2 ≤ ... ≤ bn. Then, for each 1 ≤ i ≤ n, we check if a1 + ... + ai = b1 + ... + bi, and if so, we increment ct++. (If sum are equal, then element must be equal because it is the minimum possible sum). Then ct will be the answer.

Implementation: 14386133

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

    Can you please tell me why the statement " If sum are equal, then elements must be equal" is always true ? Although I noticed this fact with few examples, but I couldn't prove it.

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

sorry, in problem C when you say H_j is H_i right?

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

    This isn't the only point that confuses me :) I'd actually appreciate if someone wrote a simpler and more detailed explanation for the problem C (at least, by filling in the gap in the logical steps before the sentence 'Firstly, we need to calculate two arrays').

    It would also be really great to start seeing the tutorials with pictures. For some reason the pictures are used to describe the problem statements, but they are avoided when they try to explain the solution for those who didn't solve the problem ;)

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

For problem D: won't the equation be: 6x = 3mn2 + 3mn — n3 + n. I solved using this equation and got accepted. Here is the solution : 14387650

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

    I use the same equation as yours, and I'm confused by the equation in the editorial. Anyone who can explain that? Thanks. :)

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

    but how it is possible??

    can you please explain.....

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

      I had got the similar general equation as :

      but when I proceed to solve it I got:

      6x = 6mn2 — 3(n+m)*(n)*(n-1) + (n)*(n-1)*(2n-1)

      I got the above equation after expanding the summations that is sum of k intgers and sum of k squares, here k = n-1.
      On further simplification we get the equation I mentioned above :

      6x = 3mn2 + 3mn — n3 + n.

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

My solution for D does not work for certain numbers, but still got AC. (Only sad thing is that I submitted the 'right' solution with an upperbound of instead of , which got hacked. Didn't know that would discard my accepted solution too.)

Let n < m. We can derive that 6x = n(n + 1)(3m + 1 - n). (By the way, you forgot the  - n3 in the final formula in the editorial.) What I did: first factorize 6x. Then, generate all divisors of 6x. Now, sort the divisors, and check for each divisor d whether d + 1 is a divisor too. (Thus, whether it equals the next divisor in the list.) If both d and d + 1 are divisors, set n = d and solve for m. If m is an integer, we have found a solution.

The problem is that we can only factor numbers with at most one prime above 106. (Or 107, but that doesn't really help.) The algorithm fails when 6x has two consecutive divisors and two large factors. In particular, this might happen when 6x = 2·3·p·q, and p = q ± 1, p = 2q ± 1, p = 3q ± 1, p = 6q ± 1 or 2p = 3q ± 1. (Although the first case can't happen.) I was to lazy to check each of theses cases separately, but it still passed when I resubmitted it after the contest. I think this solution should have been proven wrong by the system tests, but one can always miss some weird solutions. It was a nice contest anyway!

Solution

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

    I got AC with the same equation without handling any special case...

    6x = n(n + 1)(3m + 1 - n)

    since n and (n+1) can not have any common factor and 6x/(n*(n+1)) should be integer,

    it means 6x should be divisible by n & (n+1) individually...

    and as we assume m>=n

    it means (3m+1-n)>=2*n+1

    hence 6x/(n*(n+1))>=(2*n+1)

    so just run a loop for all n with above conditions

    code: 14383578

    time comp.-> O(cuberoot(x))

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

      Yes, you're right. Since , we only have to know the divisors (or factors) of x up to 2·106. This excludes all my special cases. I clearly wasn't thinking straight yesterday.

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

in problem B : why don't when i find count of some element b[i] more than 1 immediately print "Ambiguity", is it wrong ?

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

    3 3

    1 1 2

    1 1 3

    If you print "Ambiguity" then there should exist several sequences that satisfy the sequences F and B, but in this case, even though there is ambiguity with the 1's, it's impossible because a 3 never appeared in the sequence F.

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

How is my logic wrong for A, I only got till pretest 4,I put these 4 values into integers

  1. d1+d2+d3
  2. 2(d1 + d3)
  3. 2(d2 + d3)
  4. 2(d1 + d2)

and then I put these integers into an array and I wrote a for loop to find the minimum value

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

    Hi, I have read some of your submissions. Your logic is right, but your code have some implementation bugs. For example, you store the minimum in an unitialized int variable named 'o'. The default constructor initializes 'o' with some undefined value. That's why your code outputs a 0 in the first case ('o' is initialized with zero). In your last submission, if all the distances are equal, you are not printing anything. You are looking for a number in that array that is strictly less than all the others. Finally, make sure that you are inserting exactly the values (d1+d2+d3), 2*(d1+d3), 2*(d2+d3) and 2*(d1+d2) (I think you are inserting 2*(d1+d2)+d3 instead of d1+d2+d3).

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

Problem D. 6x = -n^3 + 3mn^2 + (3m+1)*n

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

What's wrong with my submission? I cant figure it out.. http://mirror.codeforces.com/contest/599/my#

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

    That link takes one to his personal submissions for that contest, not yours.

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

In Problem B , I did the same thing as mentioned here but its failing in the system tests , Test case #10. Its a pretty large test case so i am able to figure out the bug.

Can anybody tell me whats wrong ? Here's the link to code : http://mirror.codeforces.com/contest/599/submission/14373418

Would be great if anybody could help. Thank You.

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

For problem D, I assumed that m = (6x + n3 - n) / (3n2 + 3n) is decreasing because data seemed like it. So n's upper bound is when . When 6x gets bigger n gets bigger. So n's upper bound is when 2n3 + 3n2 - n = 6 * 1018 therefore n ≤ 1442249. Fortunately, this got accepted. But after the exam I looked at some m - n graphs for various x values and realized that this is not monotonically decreasing, instead it first goes down, and after n = m it goes up again. I'm wondering if there's any integer (n, m) pairs where n is bigger than the first intersection point (a.k.a my pseudo upper bound). If not, how to prove it?

Graph of the first test case of the problem:

UPD: Nevermind me :D I don't know how I couldn't see n is always bigger than m after intersection (even though m starts to increase again, it increases more slowly compared to n) by looking at that graph.

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

The problem D.X<=10^18？WA65....

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

problem B is failing on test 20 and i can't figure out the bug. can anyone help me ?

here's my code 14400028

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

    You can have situation when you say: "Ambiguity" and return 0, but after your answer you have f[i] that not exist... For example: n = 4, m = 2, f = {1, 1, 3, 4} b = {1, 50} Answer: Impossible

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

    you should test that the solution "possible" before saying "Ambiguity" because you say that there is many solution but actually there is no solution

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

      correct me if i'm wrong

      i'm checking like this

      1- if the number doesn't exists in (F) print impossible close the program, else continue

      2-if the number exists more than once in (F) print ambiguity close program ,else continue

      3- if the number passes all the above then it's possible to find a solution ,store number in an array

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

        2nd point is wrong.

        If you say there is ambiguity, then there should be several ways to create a sequence A that satisfies the sequences F and B.

        Check this case

        3 3

        1 1 2

        1 1 3

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

        In your 2nd point, you can't close the program if you get ambiguity, as it is possible you get "Impossible" later. An impossible solution also may have ambiguities.

        So keep a flag for ambiguity. If you find solution is not "impossible", then and only then print ambiguity, and else the answer.

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

About problem C:

I got wrong answer in test case 7 which is:

25

1 2 3 4 4 4 4 4 4 4 2 3 5 5 7 9 8 5 10 12 15 12 100500 800600 228228228

My output: 13 Jury's output: 12

The maximum number of blocks was asked to find out. In this test case my partition is: [1][2][3 4 4 4 4 4 4 4 2][3][5][5][7 9 8 5][10][12][15 12][100500][800600][228228228] -->> total 13 blocks.

Could anyone tell me where I am doing mistake?????

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

    In your answer [1][2][3 4 4 4 4 4 4 4 2][3][5][5][7 9 8 5][10][12][15 12][100500][800600][228228228]

    The 3rd and 4th block have to be merged as 3 is less than 4. So finally you will have 12 blocks, which is the answer.

    [1][2][3 4 4 4 4 4 4 4 2 3][5][5][7 9 8 5][10][12][15 12][100500][800600][228228228]

    I was making the same mistake you were. Let us see what that mistake is with an example.

    4 3 6 1 2 5

    I was finding for every element, the last index among all elements which are less than it. So for 4, I find that 2 is last element less than it, so I formed the blocks

    [4 3 6 1 2][5]. But this is incorrect.

    What I didn't consider is that in the newly formed block there maybe some element greater than the start of the block,, and that will introduce more inversions. So here, 6 is greater than 4, so 5 also has to be included in the block. Hence final block is [4 3 6 1 2 5]

    Hope you get the point.

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

in PROBLEM B

I adjusted my code and it's failing on test 28 .the weird thing is that test 28 gives me the correct answer when i run it on my PC but gives a completely different answer on the judge's system. here's the submission 14411133

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

    In your code, you need to set your "bool exists[]" array to zero. Since you are not doing that, your bool array is getting garbage values and hence your answer is wrong.

    So, either declare the array as global(which automatically sets it to zero), or do a memset, or go through the array in a loop and set all values to zero.

    Here is the AC submission: AC

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

D Getting 6x = 6n2 * m - 3(n2 + n3 - nm - n2) + 2n3 - 3n3 + n = 3 * m * n2 + 3 * m * n - n3 + n wrong? Is this? Getting 6x = 6n2 * m - 3(mn2 + n3 - nm - n2) + 2n3 - 3n3 + n = 3 * m * n2 + 3 * m * n - n3 + n

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

Can someone explain E in more detail ??

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

Can someone please give the necessary resource links(blogs,tuts etc) for understanding problem E as could not understand it

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

Hey, I was upsolving some problems and one of them was E of this contest.

I liked the problem and after reading the editorial and some silly mistakes in the implementation I got accepted and feel that I learned something, but there's something I don't understand in the editorial, the time complexity.

I understand how to check the fulfillment of the conditions before a transition in O(N3) or O(N·Q) but I don't understand where does the O(3N) come from.

Could anyone give me an explanation or at least some hints about the 3N? ;)

Thanks :)

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

    Although I'm a beginner , luckily I know why 3^N.( my English is poor, sorry ) All of the states is 2^N, that is no problem. For every state that has i of 1 in its bits( 11101 is 4, 11001 is 3, 10011 is 3) the number of submasks of it is 2^i(other bit is 0) so the equation is C(i,N)*2^i ( 0 < i <= N ) so it's 3^N This thing has also been used in the solution to Steiner Tree, maybe you can google it. Hope helpful to you.

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

tfw you solve problem C with sieve of eratosthenes

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

Can Anyone help me in understanding the testcases of problem B.

→ Reply