HolkinPV's blog

By HolkinPV, 5 years ago, translation, , 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(N2) — 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 ai and could not be found among bi (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number ai of the first student equals 0, so his number is a number in pair [0, bi].

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 bi in such pair where ai equals to number of penultimate found student number (that is a number in pair [ans[i - 2], bi]). 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 posi, which less than pos, replace all ? on prev[posi]. In all positions posi, 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(N2) time and O(N2) memory. The memory could be O(N) if you get indexes of directed edges without two-dimensional array. Tutorial of Codeforces Round #279 (Div. 2) Tutorial of Codeforces Round #279 (Div. 2) 279, Comments (68)
 » Why 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 and traverse it at the end.
•  » » » Thanks)
 » 5 years ago, # | ← Rev. 2 →   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) ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   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....
•  » » » 5 years ago, # ^ | ← Rev. 2 →   You can factorize the dimensions of the chocolate. Taking the second sample case, you have 36 × 5 and 10 × 16; the factorizations are 36 = 22·32, 5 = 5, 10 = 2·5, and 16 = 24.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.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   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(N2) ?
•  » » I can't follow all the logic, but this looks like O(N * logN) to me: 8816064
•  » » » I'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).
•  » » » 5 years ago, # ^ | ← Rev. 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 submission
 » Hey! 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.
 » 5 years ago, # | ← Rev. 2 →   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) N=int(input()) T=list(map(int,input().split())) Output=[] I=0 while 1 in T and 2 in T and 3 in T: try: if T[I]==1: Output.append([I+1]) T[I]=0 for I in range(N): if T[I]==2: Output[len(Output)-1].append(I+1) T[I]=0 for I in range(N): if T[I]==3: Output[len(Output)-1].append(I+1) T[I]=0 break break except IndexError:break I+=1 print(len(Output)) for I in range(len(Output)): for I2 in range(3): if I2==2:print(Output[I][I2]) else:print(Output[I][I2],end=' ')
•  » » 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(N3) algorithm will not pass for N = 5000 even with C/C++ (two of the fastest languages on Codeforces). You need to rethink your algorithm.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   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(N3), when it should actually be O(N2) or a low constant factor O(N2 * logN).
•  » » » Thanks! :) I think I get it, it's because I do the LIS search at the end of every path, so there are a lot of repetitive search.I don't see why it is O(N3) though, I would think my solution is O(N2logN) which is why it doesn't pass as it is supposed to be O(N2). Am i wrong ?
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   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(N2 + PNlogN) where the O(N2) is for the dfs and the O(PNlogN) where P is the number of paths to search LIS can be up to N2 (let's say each node is match to all the other nodes) so effectively the total complexity is O(N3logN) 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?
•  » » 5 years ago, # ^ | ← Rev. 3 →   Each time you do a type 1 operation, if the area of the rectangle is 2i * 3j, then it will become 2i - 1 * 3j. Each time you do a type 2 operation, if the area of the rectangle is 2i * 3j, then it will become 2i + 1 * 3j - 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.
•  » » 5 years ago, # ^ | ← Rev. 8 →   Mistake is in lines 55-66 of your code. Your programm doesn't react if two numbers are equalTest:211
•  » » » 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(..•˘_˘•..)
 » 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
 » 6 months ago, # | ← Rev. 2 → » MY SOLUTION to the A problem Team Olympiad