### 490A - Team Olympiad

The teams could be formed using greedy algorithm. We can choose any three children with different skills who are not participants of any team yet and form a new team using them. After some time we could not form any team, so the answer to the problem is minimum of the number of ones, twos and threes in given array. We can get *O*(*N*) solution if we add children with different skills into three different arrays. Also the problem could be solved in *O*(*N*^{2}) — every iteration find new three children for new team.

### 490B - Queue

This problem can be solved constructively. Find the first student — it is a student with such number which can be found among *a*_{i} and could not be found among *b*_{i} (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number *a*_{i} of the first student equals 0, so his number is a number in pair [0, *b*_{i}].

After that we will find numbers of all other students beginning from the third. It can be easily done using penultimate found number. The number of the next student is a number *b*_{i} in such pair where *a*_{i} equals to number of penultimate found student number (that is a number in pair [*ans*_{}[*i* - 2], *b*_{i}]). Look at the sample to understand the solution better.

### 490C - Hacking Cypher

At first, let’s check all prefixes of specified number — do they have remainder 0 when divided by the *a*? It can be done with asymptotic behavior *O*(*N*), where *N* -length of specified number *C*. If we have remainder of division by *a* of prefix, which ends in position *pos*, we can count remainder in position *pos* + 1: *rema*[*pos* + 1] = (*rema*[*pos*] * 10 + *C*[*pos* + 1]) % *a*.

Then we need to check suffixes.If we have remainder of division by *b* of suffix, which begin in position *pos*, we can count remainder of position *pos* - 1: *remb*[*pos* - 1] = (*C*[*pos* - 1] * *P* + *remb*[*pos*]) % *b*, where *P* — it is 10^(*L* - 1) module *b*, *L* — length of suffix (*P* we can count parallel).

Now let’s check all positions *pos* — can we cut specified number *C* in this position. We can do it if next four conditions performed: prefix of number *C*, which ends in *pos* is divisible by *a*; suffix of number *C*, which begin in *pos* + 1 is divisible by *b*; length of prefix and suffix more than 0; first digit of suffix is different from 0. If all four conditions performed we found answer. If we did not find any such positions, than print *NO*.

### 490D - Chocolate

We can change the numbers by dividing their by two or by dividing their by three and multiply two. Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not. If their squares are not equals answer doesn’t exists. Otherwise calculate of difference between number of three in factorization, we should remove this amount of threes from the some chocolate, it depends from the sign, and recalculate difference between number of two in factorization and do the same.

### 490E - Restoring Increasing Sequence

Let’s iterate on specified numbers and try to make from current number minimal possible, which value more than value of previous number. Let’s current number is *cur*, previous number is *prev*.

If length of number *cur* less than length of number *prev* — let’s print *NO*, this problem has not solution.

If length of number *cur* more than length of number *prev* — replace all signs ? in number *cur* to digit 0, except case, when sign ? in first position — replace him on digit 1, because numbers in answer must be without leading zeroes.

Another case when lengths of numbers *a* and *b* are equal. Let’s iterate on positions *pos*, in which prefix number *cur* more than prefix of number *prev*. Now we need to try for this position make minimal possible number, which more than *prev*. In all positions *pos*_{i}, which less than *pos*, replace all ? on *prev*[*pos*_{i}]. In all positions *pos*_{i}, which more than *pos*, replace all ? on digit 0. If *cur*[*pos*] = = ? than make *cur*[*pos*] = *max*(*prev*[*pos*] + 1, 9).

If received number less or equal to *prev* — this position is bad. From all good positions choose minimal number, received with operations above and assign him number *cur* and will continue iteration. If count of such positions is 0 we need to print *NO*.

### 490F - Treeland Tour

The problem is generalization of finding maximal increasing subsequence in array, so it probably can be solved using dynamic programming. We will calс dynamic *d*[(*u*, *v*)], the state is directed edge (*u*, *v*) in tree. Value *d*[(*u*, *v*)] means the maximum number of vertices where the band will have concerts on some simple path ended in vertex *v* going through vertex *u*. Also the concert in vertex *v* must be certainly.

To calc *d*(*u*, *v*) we should consider all such edges (*x*, *y*) that there is simple path started in *x*, going through *y*, *u* and ended in *v*. These edges can be found using dfs from vertex *u* which is not going through vertex *v*. All edges used by dfs should be reoriented. So if *r*[*y*] < *r*[*v*] then *d*[(*u*, *v*)] = *max*(*d*[(*u*, *v*)], *d*[(*x*, *y*)] + 1). The solution needs *O*(*N*^{2}) time and *O*(*N*^{2}) memory. The memory could be *O*(*N*) if you get indexes of directed edges without two-dimensional array.

comments soon

How to find a student which in first place in problem B?

You should use map to find this

You might use map-container. Every non-first and non-last student appears in the input twice. Just keep the map <Student ID, appearances> and traverse it at the end.

Thanks)

In problem E, case: lengths of number a and b are equal, if (cur[pos]=='?') then cur[pos] = max(prev[pos] + 1, 9) or cur[pos] = min(prev[pos] + 1, 9) ?

it can't be max(prev[pos] + 1, 9)

it should be min(prev[pos] + 1, 9)

i think it is a typing mistake

Will someone please explain approach to problem D : Cholocate ?

I am not able to get the explanation described...

Thanks

+1, the comment says: " Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not.". This sentence makes no sense....

You can factorize the dimensions of the chocolate. Taking the second sample case, you have 36 × 5 and 10 × 16; the factorizations are 36 = 2

^{2}·3^{2}, 5 = 5, 10 = 2·5, and 16 = 2^{4}.Now you remove all factors of 2 and 3. Thus, 36 turns to 1, having all factors removed. 10 turns to 5, having the 2 removed but not the 5. 5 remains a 5.

After doing this, we are left with 1 × 5 and 5 × 1. The areas are equal (both are 5), so we can solve this (at least by cutting all chocolates by thirds, then by halves; we will always end up with 1 × 5 and 5 × 1 if we keep doing the cutting, although there might be a better solution). If the sizes aren't equal (such as in third sample case, where you have 1 × 5 = 5 and 1 × 1 = 1), you can't solve it.

I got wrong answer for test 12, but when I checked the results from jury's and my outputs, they are both correct, I mean number of minutes in both outputs are the same and aXb equals cXd where a,b,c,d are the sides of those chocolates. here is my code 11133391 and judge result http://postimg.org/image/4qmj8m90b/

Is there any faster solution for F than

O(N?^{2})I can't follow all the logic, but this looks like

O(N*logN) to me: 8816064I'm not sure but I think it's O(N*(logN)^2). In each "MergeQuery" operation, it takes O(logN) for every node in tree2 to query and insert. By controling the size of t2 smaller than t1, it can be guaranteed that every node will be involved in a MergeQuery option for at most logN times. I think this upper bound can be reached in a full binary tree.

You are right, It's O(N*(log N)^2).

Hey MLGuy, I implemented the

`O(N^2 * logN)`

solution in Java similar to your submission but it gives me TLE. I'd appreciate it if you could take a look and point out if I'm doing something wrong: Treeland Java submissionHey! could you further explain D.chocolate more clearly? What do you mean by saying: "Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not". Whose square equals who? Really appreciate it......

Well, I think it means you should check whether the products of the width and height after removing all 2 and 3 are the same. The "square" in the sentence seems weird to me though.

Thanks!!!I also guess so...lol

It simply means that if we factorize a1*b1 and a2*b2 and remove all 2 and 3 factors from both and if they are not equal, the solution does'nt exists.

Look here: http://codeforces.com/contest/490/submission/8843267

Is there any sample code of problem F using the idea in the tutorial? I can't understand how to implement this......

My submission (http://codeforces.com/contest/490/submission/8886626) is pretty much like that.

Things to be aware of: You have to add a dummy edge coming from (but not to) any leaf to a dummy node.

I also do not use DP, but rather memoization, that way I do not have to worry about the order in which I process the edges.

I got it, thank you very much!

My program on pretest 8 in question A, gives the wrong answer, but why? Please somebody help me. My program:(in Python 3)

Well, you use index I twice inside the try block... I'm pretty sure that changing the index to a unique name (for example, use "for J in range(N)" the first time and then "for K in range(N)") will lead to a correct answer in that test. Also, I think the algorithm will be too slow to pass all the tests. The condition in the while loop takes O(N) to evaluate, and then you make an O(N^2) loop inside.

No,Python it does. If two "for" at the same time to counter the "I" the two "I", by mistake do not move . My problem is that when all the students in the teams my program one fewer runs Anyway, thank you that you are trying to debug my program but my problem still remains ...

Oh, sorry for my ignorance :( Yesterday I made a submission based on your code, would you mind taking a look at it? 8849662 If I understood correctly, this solution passes the test you mentioned. If not, I apologize for my mistakes.

Thank you very much. I have no problem with my program & I think Time Limit Only in python codes(for this question)

No, you have TLE everywhere.

O(N^{3}) algorithm will not pass forN= 5000 even with C/C++ (two of the fastest languages on Codeforces). You need to rethink your algorithm.No, it doesn't. True, the

`I`

in the outer`for`

(the one directly inside`try`

) will not be affected as it iterates along`range(N)`

, but the`I`

outside (the global variable) will be affected; when it exits the`for/for`

loop,`I`

will be equal to`N-1`

(being the last value in the inner list).Here is a modified version of your code, where I removed the output code and added a print statement for what value of

`I`

and in which loop the program is currently reading. As you can see, after breaking out from the innermost loop,`I`

retains its value, leading to`global 5`

instead of the expected`global 1`

. (This also means`1 1 2 2 3 3`

fails your program, as you only got the first`1 2 3`

, not finding the second.)Oh, Yes! Your edit is best edit with my code. I'm a Python newbie programmer. Thank you for helping me.

Could anyone tell me what's wrong with my code for

F?8840730 I get TLE on test #53 and I'm not sure why :/Thanks !

Your algorithm seems to be

O(N^{3}), when it should actually beO(N^{2}) or a low constant factorO(N^{2}*logN).Thanks! :) I think I get it, it's because I do the

LISsearch at the end of every path, so there are a lot of repetitive search.I don't see why it is

O(N^{3}) though, I would think my solution isO(N^{2}logN) which is why it doesn't pass as it is supposed to beO(N^{2}). Am i wrong ?O(N2logN) can pass easily, I think. My solution is O(N2logN) because of some unnecessary binary search, but it still pass in 124ms. I think your solution is O(N3logN) because you have to enumerate all the vertex in the tree as the root. Maybe there's a more accurate analysis though... Edit: My example is wrong, but I still think it's not O(N2logN).

I think you are right ! I believe my solution is

O(N^{2}+PNlogN) where theO(N^{2}) is for the dfs and theO(PNlogN) wherePis the number of paths to searchLIScan be up toN^{2}(let's say each node is match to all the other nodes) so effectively the total complexity isO(N^{3}logN) which is too slow!Thanks for the help !

I am unable to understand

`D-Chocolate`

.All I can understand is iff you have`a1*b1`

and`a2*b2`

first remove all 2's and 3's from them and after removing if`a1*b1!=a2*b2`

then answer is`NO`

else we have to do something. Can anybody tell me what next we are supposed to do?^{i}* 3^{j}, then it will become 2^{i - 1}* 3^{j}.^{i}* 3^{j}, then it will become 2^{i + 1}* 3^{j - 1}.The idea is to make the exponents in a1*b1 and a2*b2 equal.

Got that.Thnx :)

could anyone please tell me why WA ? http://ideone.com/0AzRks

Is it possible to get full test-cases of Problem-E ? I am getting WA in test-case 9, but the test-case is truncated after some values. There are dots (...) which means continue, but the full test-cases are not there.

Is there anyway to get this I am missing?

Thanks.

Mistake is in lines 55-66 of your code. Your programm doesn't react if two numbers are equal

Test:

2

1

1

Thanks Kefaa!

My code had another major problem. After submitting 17 times I got Accepted!!! Yaaayyyy...!!! :D :D :D

After reading the tutorial, I realized how unnecessary this solution by me is: http://codeforces.com/contest/490/submission/8829276

In D-Chocolate could any one explain that why does a solution exist after removing all 2's and 3's as factors ??

You can see the no. of segments in each chocolate bar, as factorized by 2 and 3: . the actions only change

`x`

and`y`

, not`K`

. So if two K do not equal, answer doesn't exist.Thnx, got it!!

Could anybody help me with my solution 8871640

well, i am a beginner....here in PRBLM A told to print any of the solution....for the first pre test why it is ans 3 5 2 and 7 6 4 why not 1 5 2 and 3 6 4....

Both of them are right answer for test 1 so you can output one of them.

Well,I'm not familiar to this website,I want to know where can I get the whole test data◔ ‸◔？ I don't know why I'm wrong on test 7,and the test data on the website is not complete(..•˘_˘•..)

Here: http://codeforces.com/contest/490/submission/8895986

hello PROB : B http://codeforces.com/contest/490/my#

got TLE on test case 46 what can I do?

O(N * logN)

could anyone help me on how to solve Div2 Problem B using disjoint set data structure, as I found dsu tag attached with this problem.

Anyone have any idea why WA on problem E at 12124985?

I have written several version but I cannot seem to get past test case 6. I am sure I am missing something, any help is appreciated!

Has anyone consistently got WA on test number 42 in problem C? I am unable to figure out my mistake. Thanks 14803288

I didn't understood the explanation for 490F so I went for browsing other's code instead, and here is a much more easier solution related to LIS with O(n^2 * log(n)) time complexity.

If you happen to be familiar with the LIS algorithm, you would understand that each time we visit a new node we just find the place where the new node could just fit into the optimal LIS, the only problem left is how do we choose the first position of the sequence and how do we handle a node leaving the LIS. (i.e. it has reached it's end in the euler tour)

So far I haven't come up with a brilliant answer with the first question, so it would be left as brute force from each node instead.

For the second question, keep a 2D-vector(or stack to be precise) to store the values, when a node leaves, just pop it from it's corresponding position and update the value from the updated top of the stack. This resets the LIS back to the state before visiting the subtree.

My implementation after viewing others ideas: http://codeforces.com/contest/490/submission/19867543

Hi haleyk100198 do you know why works when only calls the dfs from leaves?

If you are talking about my approach, it only works when it is called from the starting point of the journey.

haleyk100198 what's the complexity of your solution?

thanks!

"here is a much more easier solution related to LIS with

O(n^2 * log(n)) time complexity."Here, you are required to run O(n) dfs which takes O(n) time each, and the LIS algorithm inserts each node with a O(logn) time complexity.

In problem A, I solved using O(N^2) and O(N) and O(N^2) took lesser time and memory to run. So how do I decide which is the best solution

in problem C why %b is done after multiplying with 10

i think that we need a proof :/

I think to remove the overflow. The digits can be 10^6. So if u multiply 10 for each digit it weill be 10^(10^6) which will obviously overflow. So we can % b and then it wont overflow

as we know number's length can be bigger than 10^6 so we have to make it smaller . ( to check %b) , so we go from rightmost number . keep in mind that in modular arithmetic we have properties :

(a+b)%c = (a%c + b%c) % c

(a*b)%c = ((a%c) * (b%c)) % c

suppose we have ...262 and b is 13 .

let's start from 62 we are interested in what is

(62)%13 . 62 = 6*10 + 2 ,

62 % 13 = (6*10 + 2) % 13 -> (6*10 % 13 + 2 % 13) % 13

then take 262

262 = (2*100 + 6*10 + 2),

262 % 13 = (2*100 %13 + 6*10 % 13 + 2 % 13) % 13 ,

we already know ( 6*10 % 13 + 2 % 13 ) % 13 so we take it from previous step , and we have to make 1 more thing , because our number 100 can get 10 ^ 6 , we have to make it smaller too , so we take (100%13) , then ((100%13)*10)%13 and so on ... i hope it helps :d

MY SOLUTION to the A problem Team Olympiad

Can anyone explain how does this relation cam

`rema[pos + 1] = (rema[pos] * 10 + C[pos + 1]) % a`

for Problem C?Can somebody help me with problem B? I stored the values in a map, found the last two elements and found rest of the elements using those values, but getting TLE. Any ideas on how to optimize this, particularly second-last loop?

88036986

Can anyone please provide the proof of solution of div2 C? How we are calculating the modulus of such a large number? I tried to google it but wasn't able to find it anywhere.