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 *b*_{i}

- If two or more elements exist from which it's possible to get
*b*_{i}, then use your special mark that answer is*Ambiguity* - If no elements exist from which it's possible to get
*b*_{i}, then print*Impossible* - If only one element exists from which it's possible to get
*b*_{i}just change*b*_{i}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 *H*_{i} be a sorted sequence of *h*_{i}. Let ** E** — set of indices of the last elements of each block. Then

*e*

**, first**

*E**e*sorted elements of sequence

*h*

_{i}are equal to the first

*e*elements of the sequence

*H*

_{j}.

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 *prefmax*_{i} — maximum between *a*_{1}, *a*_{2}, ..., *a*_{i}, and *suffmin*_{i} — minimum between *a*_{i}, *a*_{i + 1}, ..., *a*_{n}.

If you want to get the answer, just calculate the number of indices *i* that *prefmax*_{i} ≤ *suffmin*_{i + 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 6*x* = 6*n*^{2} * *m* - 3(*n*^{2} + *n*^{3} - *nm* - *n*^{2}) + 2*n*^{3} - 3*n*^{3} + *n* = 3 * *m* * *n*^{2} + 3 * *m* * *n* - *n*^{3} + *n*

As we solved this task for *n* ≤ *m* the 3*n*^{2} * *m* = ≈ *n*^{3}, it means that *n* is not greater than .

Time:

Problem E.

The solution for this problem is dynamic programming.

Let *f*_{root, 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 *f*_{0, 2n - 1}.

Trivial states are the states where a mask has only one single bit. In such cases *f*_{root, 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*(*N*^{2}) — 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*(3^{N}·*N*^{3}) or *O*(3^{N}·*N*·*Q*)

Auto comment: topic has been updated by K0T (previous revision, new revision, compare).Auto comment: topic has been updated by K0T (previous revision, new revision, compare).sorry, in problem C when you say H_j is H_i right?

Thank you for your fast tutorial:)

Thanks for nice editorial and nice contest :)

Problem A: this line

`min(d1, d2) + min(d3, d1+d2) + min(d3+min(d1, d2), max(d1,d2))`

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

even easier :)

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 :)

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

We know that 6x=3n^2*m+3nm+n. If we know n and x we can calculate m.

Sure.Missed it (

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.

Problem C:

I solved it in

`nlog(n)`

:I will illustrate on this example:

4 3 4 1 2

(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

Hey! I did it in the same fashion :)

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

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.

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

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

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

Say you have the array elements

a_{1},a_{2}, ...,a_{n}. Then, call them sorted beb_{1}≤b_{2}≤ ... ≤b_{n}. Then, for each 1 ≤i≤n, we check ifa_{1}+ ... +a_{i}=b_{1}+ ... +b_{i}, 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

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.

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

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 ;)

For problem D: won't the equation be: 6x = 3mn

^{2}+ 3mn — n^{3}+ n. I solved using this equation and got accepted. Here is the solution : 14387650I use the same equation as yours, and I'm confused by the equation in the editorial. Anyone who can explain that? Thanks. :)

but how it is possible??

can you please explain.....

I had got the similar general equation as :

but when I proceed to solve it I got:

6x = 6mn

^{2}— 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 = 3mn

^{2}+ 3mn — n^{3}+ n.thanks adnaan1703

//Solved

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 -n^{3}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 divisordwhetherd+ 1 is a divisor too. (Thus, whether it equals the next divisor in the list.) If bothdandd+ 1 are divisors, setn=dand solve form. Ifmis an integer, we have found a solution.The problem is that we can only factor numbers with at most one prime above 10

^{6}. (Or 10^{7}, but that doesn't really help.) The algorithm fails when 6xhas two consecutive divisors and two large factors. In particular, this might happen when 6x= 2·3·p·q, andp=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

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

Yes, you're right. Since , we only have to know the divisors (or factors) of

xup to 2·10^{6}. This excludes all my special cases. I clearly wasn't thinking straight yesterday.in problem B : why don't when i find count of some element b[i] more than 1 immediately print "Ambiguity", is it wrong ?

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.

Thanks bro :)

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

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

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

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

undefinedvalue. 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 isstrictlyless 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).…

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

but how it is possible??

can you please explain.....

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

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

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/14373418

Would be great if anybody could help. Thank You.

It is not ambiguous if there are identical elements in the array

b.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.

For problem D, I assumed that

m= (6x+n^{3}-n) / (3n^{2}+ 3n) is decreasing because data seemed like it. Son's upper bound is when . When 6xgets biggerngets bigger. Son's upper bound is when 2n^{3}+ 3n^{2}-n= 6 * 10^{18}thereforen≤ 1442249. Fortunately, this got accepted. But after the exam I looked at somem-ngraphs for variousxvalues and realized that this is not monotonically decreasing, instead it first goes down, and aftern=mit goes up again. I'm wondering if there's any integer (n, m) pairs wherenis 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

nis always bigger thanmafter intersection (even thoughmstarts to increase again, it increases more slowly compared ton) by looking at that graph.The problem D.X<=10^18？WA65....

well, i solved B with binary search and thought it was good, but this one's simplicity blew my mind...

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

here's my code 14400028

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

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

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

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

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

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.

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

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

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.

Thank you so much brother. :) I get the point now.

Could somebody explain how the solutions for problem D with this inner cycle work:

e.g. 14403136 Looks more elegant than calculating whole formula every time, but how does it work??

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

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

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

Can someone explain E in more detail ??

DELETED

deleted

deleted

Дискриминация индусов.

deleted

DELETED

Can someone please give the necessary resource links(blogs,tuts etc) for understanding problem E as could not understand 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(N^{3}) orO(N·Q) but I don't understand where does theO(3^{N}) come from.Could anyone give me an explanation or at least some hints about the 3

^{N}? ;)Thanks :)

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.

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.