### Yury_Bandarchuk's blog

By Yury_Bandarchuk, 6 years ago, translation,

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)

• +120

 » 6 years ago, # |   +3 Auto comment: topic has been updated by Yury_Bandarchuk (previous revision, new revision, compare).
 » 6 years ago, # |   0 Auto comment: topic has been updated by Yury_Bandarchuk (previous revision, new revision, compare).
•  » » 6 years ago, # ^ |   0 sorry, in problem C when you say H_j is H_i right?
 » 6 years ago, # |   0 Thank you for your fast tutorial:)
 » 6 years ago, # |   0 Thanks for nice editorial and nice contest :)
 » 6 years ago, # |   0 Problem A: this line min(d1, d2) + min(d3, d1+d2) + min(d3+min(d1, d2), max(d1,d2)) solves it.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +29 what about ? :) min(a,b+c)+min(c,a+b)+min(b,a+c)
•  » » » 6 years ago, # ^ |   0 even easier :)
•  » » 6 years ago, # ^ |   +8 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 :)
 » 6 years ago, # |   0 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)?
•  » » 6 years ago, # ^ |   +3 We know that 6x=3n^2*m+3nm+n. If we know n and x we can calculate m.
•  » » » 6 years ago, # ^ |   0 Sure.Missed it (
•  » » 6 years ago, # ^ |   0 From what I was able to deduce ,m = 6X+ n*(n-1)*(n+1)/(3*n*(n+1))So with a simple loop and checking if the above division is possible/iteration, we can find all the m's we need.
 » 6 years ago, # |   +3 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-totmy code: 14383376
•  » » 6 years ago, # ^ |   0 Hey! I did it in the same fashion :)
•  » » » 6 years ago, # ^ |   0 I think we solved it the hard way :) there are simpler solutions.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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.
 » 6 years ago, # |   0 Fastest system testing ever! And super fast editorial. Great job. Ciao.
 » 6 years ago, # |   0 Problem D — Spongebob and Squares is a beautiful problem, kudos to the author
 » 6 years ago, # |   +56 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
•  » » 4 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 sorry, in problem C when you say H_j is H_i right?
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 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 ;)
 » 6 years ago, # |   +11 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
•  » » 6 years ago, # ^ |   0 I use the same equation as yours, and I'm confused by the equation in the editorial. Anyone who can explain that? Thanks. :)
•  » » 6 years ago, # ^ |   0 but how it is possible??can you please explain.....
•  » » » 6 years ago, # ^ |   +1 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.
•  » » » » 6 years ago, # ^ |   0 thanks adnaan1703
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 //Solved
 » 6 years ago, # | ← Rev. 3 →   0 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
•  » » 6 years ago, # ^ |   0 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>=nit means (3m+1-n)>=2*n+1hence 6x/(n*(n+1))>=(2*n+1)so just run a loop for all n with above conditionscode: 14383578time comp.-> O(cuberoot(x))
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
 » 6 years ago, # |   0 in problem B : why don't when i find count of some element b[i] more than 1 immediately print "Ambiguity", is it wrong ?
•  » » 6 years ago, # ^ |   0 3 31 1 21 1 3If 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.
•  » » » 6 years ago, # ^ |   0 Thanks bro :)
•  » » » 6 years ago, # ^ |   0 My code works correctly for this test case however it fails in the system test. Can you help me figure out whats wrong. Its a pretty huge testcase so i am not able to find out the bug.Here the link to code : http://codeforces.com/contest/599/submission/14373418
 » 6 years ago, # |   0 How is my logic wrong for A, I only got till pretest 4,I put these 4 values into integers d1+d2+d3 2(d1 + d3) 2(d2 + d3) 2(d1 + d2) and then I put these integers into an array and I wrote a for loop to find the minimum value
•  » » 6 years ago, # ^ |   0 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).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 …
 » 6 years ago, # |   0 Problem D. 6x = -n^3 + 3mn^2 + (3m+1)*n
•  » » 6 years ago, # ^ |   0 but how it is possible??can you please explain.....
 » 6 years ago, # |   0 What's wrong with my submission? I cant figure it out.. http://codeforces.com/contest/599/my#
•  » » 6 years ago, # ^ |   0 That link takes one to his personal submissions for that contest, not yours.
 » 6 years ago, # |   0 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://codeforces.com/contest/599/submission/14373418Would be great if anybody could help. Thank You.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 It is not ambiguous if there are identical elements in the array b.
•  » » » 6 years ago, # ^ |   0 Thanks Alot! Can't believe that i lost my rating because of a stupid line in the code. After removing it, It got accepted. Thanks again.
 » 6 years ago, # | ← Rev. 5 →   +6 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.
 » 6 years ago, # |   0 The problem D.X<=10^18？WA65....
 » 6 years ago, # |   0 well, i solved B with binary search and thought it was good, but this one's simplicity blew my mind...
 » 6 years ago, # |   0 problem B is failing on test 20 and i can't figure out the bug. can anyone help me ?here's my code 14400028
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 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
•  » » » 6 years ago, # ^ |   0 the problem says that sequence B is of length m and contains numbers from 1 to n B can't be {1,50} because n =4
•  » » 6 years ago, # ^ |   0 you should test that the solution "possible" before saying "Ambiguity" because you say that there is many solution but actually there is no solution
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 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 continue2-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
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 case3 31 1 21 1 3
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 system. here's the submission 14411133
»
6 years ago, # |
Rev. 2   0

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?????

•  » » 6 years ago, # ^ |   0 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 5I 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.
•  » » » 6 years ago, # ^ |   0 Thank you so much brother. :) I get the point now.
 » 6 years ago, # |   0 Could somebody explain how the solutions for problem D with this inner cycle work:  i += 1 x -= i * i if x < 0 : break t += i m = x // t if m * t != x : continue e.g. 14403136 Looks more elegant than calculating whole formula every time, but how does it work??
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   0 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
 » 6 years ago, # |   0 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
 » 6 years ago, # |   0 Can someone explain E in more detail ??
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 DELETED
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 deleted
•  » » » 6 years ago, # ^ |   +3 Дискриминация индусов.
•  » » » » 6 years ago, # ^ | ← Rev. 5 →   +1 deleted
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -9 DELETED
 » 6 years ago, # |   +3 Can someone please give the necessary resource links(blogs,tuts etc) for understanding problem E as could not understand it
 » 6 years ago, # |   0 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 :)
•  » » 6 years ago, # ^ |   +3 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.
 » 4 years ago, # |   0 This is just an explanation for problem A to help anyone who can't visualize the different cases that can happen in such a solution ..................................................................................................... the 6 different cases that can happen in order to solve the problem case(1)||home...>1st shop...>home...>2nd shop....>home and its formula is like this((d1+d2)*2) case(2)||home...>2nd shop..>home....>1st shop ....>home also has same formula ((d1+d2)*2) case(3)||home...>2nd shop...>1st shop...>home has the formula (d1+d2d+d3) case(4)||home..>1st shop...>2nd shop...>home also has the same formula of (d1+d2+d3) case(5)||home...>2nd shop..>1st shop..>2nd shop..>home and has the formula of ((d2+d3)*2) case(6)||home...>1st shop...>2nd shop...>1st shop...>home and has the formula of ((d1+d3)*2) ................................................................................................... note:cases (1&2) are equal in value , cases(3&4) are equal in value ................................................................................................... compare between cases(1 or 2) and cases (3 or 4) and find which value has the smallest distance to walk lets call it (1st number )for now and after that compare between case 5 and case 6 and also find which one has the smallest distance to walk and also for now call it (2nd number) and at the end compare between the (1st number )and (2nd number) and which one has the smaller value and this will be the answer ,that's it.
 » 21 month(s) ago, # |   0 I'm a beginner.I don't understand the problem B. Can anyone help me?
 » 14 months ago, # |   0