Antoniuk's blog

By Antoniuk, 5 years ago, translation, ,

466A - Cheap Travel

Solution of this problem is based on two claims:
— If m·a ≤ b then there is no point to buy a ride ticket.
— Sometimes it is better to buy summary more ride tickets for amount of rides than we need.
If we receive profits bying ride tickets then number of such ones will be . For the remain n - m·x rides we must choose the best variant: to buy separate ticket for each ride, or to buy ride ticket and use it not fully.

Complexity: O(1)
Solution: 7784793

466B - Wonder Room

Let’s assume that a ≤ b.

First of all, let’s consider the situation when we can already accommodate all the students. If n ≤ a·b then answer is a·b a b.

Otherwise, we have to increase one of the walls(maybe, both). Let’s do it in the following way: iterate the size of the smallest wall newa ( ), after that we can calculate the size of another wall as .
For all this newa and newb if b ≤ newb we choose such a pair that has the smallest area of a room.

Obviously to undestrand, that there is no point to consider because we can decrease it and receive room of smaller area when we know that .

Complexity:
Solution: 7784788

466C - Number of Ways

First of all, notice that if sum of all elements is equal S then sum of each of three parts is equal .
Therefore, if S is not divided by 3 — then answer is 0.
Otherwise, let’s iterate the end of first part i (1 ≤ i ≤ n - 2) and if sum of 1..i elements is equal then it means that we have to add to the answer the amount of such j (i + 1 < j) that the sum of elements from j-th to n-tn also equals .

Let’s create an array cnt[], where cnt[i] equals 1, if the sum of elements from i-th to n-th equals and 0 — otherwise. Now, to calculate the answer we have to find the sum cnt[j] + cnt[j+1] + ... + cnt[n] faster then O(n). There are a lot of required ways to do this, but the easiest one is to create a new additional array sums[] where in j-th element will be cnt[j] + cnt[j+1] + ... + cnt[n]. It is easy to calculate in such way: sums[n] = cnt[n], sums[i] = sums[i+1] + cnt[i] (i < n).

Thus, we receive very simple solution: for each prefix of initial array 1..i with the sum that equals we need to add to the answer sums[i+2].

Complexity: O(n)
Solution: 7784781

466D - Increase Sequence

Lets use dynamic programming to solve this problem. dp[i][opened] — the number of ways to cover prefix of array 1..i by segments and make it equal to h and remain after i-th element opened segments that are not closed.

Consider all possible variants opening/closing segments in each position:
- ] closing one segment
- [ opening one new segment
- [] adding one segment with length 1
- ][ closing one opened segment and opening a new one
- - do nothing

Lets understand how to build dynamic. It is obviously to understand that a[i] + opened can be equal h or h - 1. Otherwise, number of such ways equals 0.

Consider this two cases separately:

1) a[i] + opened = h
It means that number of opened segments after i-th as max as possible and we can’t open one more segment in this place. So there are two variants:
- [ Opening a new segment. If only opened > 0. dp[i][opened] += dp[i-1][opened + 1]
- - Do nothing. dp[i][opened] += dp[i-1][opened]

Other variants are impossible because of summary value of a[i] will be greater than h(when segment is finishing in current position — it increase value, but do not influence on opened, by the dynamic definition.

2) a[i] + opened + 1 = h
Here we consider ways where i-th element has been increased by opened + 1 segments, but after i-th remain only opened not closed segments. Therefore, there are next variants:
- ] — closing one of the opened segments(we can do it opened + 1 ways). dp[i][opened] += dp[i-1][opened + 1] * (opened + 1)
- [] — creating 1-length segment. dp[i][opened] += dp[i-1][opened]
- ][ — If only opened > 0. Amount of ways to choose segment which we will close equals opened. dp[i][opened] += dp[i-1][opened] * opened

Start values — dp[1][0] = (a[1] == h || a[1] + 1 == h?1:0); dp[1][1] = (a[1] + 1 == h?1:0)

Answer — dp[n][0].

Complexity: O(n)
Solution: 7784697

466E - Information Graph

Let’s introduce all structure of the company as a graph(if у is the head of х then we add edge y -> x). It is obviously to understand that after each operation our graph will be the set of trees. Actually, the third query — to check is our vertex belong to the subtree of the vertex which has received data package. Graph that we will receive after doing all operations we call final. Also, we will say that two vertexes belong to the same connectivity component if they belong to the same component in graph that we can have from final by changing directed edge to undirected.

Consider the following statement: vertex у is the parent of vertex х in current graph(after doing first i queries) if у and х belongs to the same conectitive component and in final graph у is the parent of х.

We will solve this problem offline. After each query of adding data package we will immediately answer all the questions about this package. Besides that, use disjoint set union to define is this vertex belong to the same component or not. To answer the question we need to check that y is the parent of x in final graph and that x and y is currently belong to the same connectivity component. Final graph we will build before doing this algorithm because we know all queries. Check that y is the parent of x in final tree we can simply in O(1) by arrays of entry-time and output-time which we can calculate use dfs(v —parent u <=> (in[v] ≤ in[u] and out[u] ≤ out[v]).

Complexity: O(n * u(n)), where u — inverse Ackerman function.
Solution: 7784662

• +35

 » 5 years ago, # | ← Rev. 2 →   0 I solved C a bit another way with DP: http://codeforces.ru/contest/466/submission/7770043 First consider the case when Σ a = 0, where a is input. Then count the number dp of all indexes i from 0 to n - 2, for which Σ0ia = 0. The answer is .Now consider the case when s = Σ a ≠ 0. Take two lists dp0 and dp1. dp0 will contain all indexes i, for which , and dp1 will contain all indexes j, which satisfy . Now remains a bit tricky part, which can get TLE, if not correctly implemented: count all ordered pairs from dp0 and dp1. This can be done in linear time by looping through dp1 and saving current dp0 index: f=0 for sec in dp1: ans += f for fir in dp0[f:]: if fir < sec: ans+=1 f+=1 print ans 
•  » » 5 years ago, # ^ |   0 The loop is O(n2); consider if the input is 1 0 0 0 ... 0 1 0 0 0 ... 0 1, so that dp0 holds every index in the first half of the array, and dp1 holds every index in the second half of the array. Now you're looping through pairs.
•  » » » 3 years ago, # ^ |   0 The above method seems O(n) , since each index in dp0 is traversed only once.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I solved C the pretty much same way as yours. Although I save the sum from a[0] to a[i] (with i looped from 0 to n) to a variable and compare them to s/3 and 2s/3, if one of the conditions hold we add one to counter f (similar to your dp0) or add f to counter ct (as there would be f way to split 0->i to 2 equal parts), respectively. That way we have an O(n) solution. My solution: 7766244
•  » » » 3 weeks ago, # ^ |   0 Thanks
•  » » 4 years ago, # ^ |   0 Same idea. TLE in JAVA using HashMap> where the first entry stores the prefix sum and the second one stores all the indices in the prefix array where this occurs. Any ideas on how I can optimize this?Here it is: 14709146
 » 5 years ago, # |   +11 Hope so that D & E really comes soon !
 » 5 years ago, # |   0 I didn't quite understand Problem B's solution in the end. Why no need to consider newa > ceiling(sqrt(6n)) ? can someone give more details?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 The editorial says that newa is the smaller side; if , you can prove that this makes and hence newa is not the smaller side.
•  » » » 5 years ago, # ^ |   0 But how do we know that new a is smaller side? Can't it be new b?
 » 5 years ago, # | ← Rev. 2 →   +10 I don't quite understand the editorial for C. However, here's my solution. This is probably DP, although the fact that it might be DP doesn't come to my mind.The first part is the same as the editorial's; find the sum s and if it's not divisible by 3, return 0.On the second part, we keep three variables: t for the sum of all elements up to this point, ct to count the number of prefixes whose sum is , and res to count the actual number of pairs.We loop over each element except the last one; suppose the current element is p. We add p to t. If this causes , we add the value of ct to res. If this causes , we increment the value of ct. We do this in that order; switching won't work (try input 0 0 0; expected answer is 1 but switching the order of the above gives 3). This gives O(n) time with O(1) memory besides storing the array, better than the proposed O(n). Now why does that work? First, observe that ct holds the number of ways we can cut the array into two such that the left part sums to and the right part sums to , where the cut is done before p.Whenever , it means the last part sums to . Now, ct holds the number of ways we can cut the array so that the left part sums to before p. So we now have ct possible divisions: the first cut is any cut that ct has counted, giving a left part of , and the second cut is right after p, giving a right part of (since the sum of the left and middle parts is ). And the middle part is of course by elimination. Thus we increase res by ct.Now we update ct. If , dividing right after p gives a left part summing to , so this should now be counted by ct for future iterations. Note that we don't do this before the above so that our program won't mistakenly divide the array in the same place; if we update ct first, cutting right after p is now counted in ct, and if we also increase t, we will count dividing right after p among the possible ways, and thus both cuts happen right after p; this doesn't work for obvious reasons.Thus, after every iteration, ct holds the number of ways to split the array somewhere before the next element into two such that the first part sums to , and res holds the current total number of ways sought, where the splits are done before the next element. Since the loop finishes at the penultimate element, res now holds the number of ways to split the array as stated where the splits are done before the last element, which is the number we seek. (If we advance one more, it's possible that res counts where the second cut is at the end of the array, giving an empty third part, not accepted.)I hope the above is clear. The algorithm itself fits in three paragraphs (paragraphs 2-4 above); the proof is what makes everything bloaty.
•  » » 3 years ago, # ^ |   0 smart, i never thought of that :(
•  » » 4 weeks ago, # ^ |   0 Why are we not considering Last element
 » 5 years ago, # |   0 Another way to solve C is to take the indexes strictly smaller than n where the sum from the beginning is exactly sum/3 and the indexes strictly smaller than n where the sum from the beginning is exactly 2*sum/3. Lets call these sets idx1 and idx2. Obviously they will be sorted because we iterate from 1 to n-1. For every index from idx1 we count the indexes from idx2 which are strictly greater than our current. This could easily be done in O(logn) using binary search. Total complexity: O(nlogn). My solution.
•  » » 5 years ago, # ^ |   0 We can use two pointers method for that instead. If we have idx1 and idx2 as you described, begin with two pointers a = 0, b = 0. We compare idx1[a] and idx2[b]; if idx1[a] < idx2[b], we increment a, otherwise we increment b. Whenever we increment b, add a into the result. This works in O(n), and is essentially my solution just above (although mine works online, without storing idx1 and idx2 in memory).
•  » » » 3 years ago, # ^ |   0 Indeed what I done. http://codeforces.com/contest/466/submission/18943449
•  » » » 3 years ago, # ^ |   0 chaotic_iak Shouldn't it be: if idx1[a] < idx2[b] add b-idx2.size() to result otherwise increment b 
•  » » 3 months ago, # ^ |   0 Exactly what i did to solve this problem. The complexity of this approach is $O(n\ log (n))$ and that is enough to pass tests.
 » 5 years ago, # |   +4 how to solve E??
 » 5 years ago, # |   0 Has anybody come up with an algorithm to solve D?
 » 5 years ago, # |   0 I am unable to understand the solution for problem D and please clear me the meaning of dp[i][opened].
•  » » 5 years ago, # ^ |   0 Maybe it is easier to understand.
•  » » » 5 years ago, # ^ |   0 Thanks, that did the work. Maybe translation from Russian to English is not perfect and some meaning is lost in between.
 » 5 years ago, # |   0 In D,while a[i] + opened = h,why can we open a segment？Then,a[i]will bigger than h.Is it a mistake?
•  » » 5 years ago, # ^ |   0 Maybe I am wrong
•  » » » 5 years ago, # ^ |   0 dp[i][opened] means you solved for position i(meaning converted a[i] to h) and after that from (i+1)th position you are left with opened number of open segments.Now you have 2 valid cases From i-1 you have opened number of segments.Since a[i] is already increased by opened number we do nothing here - dp[i][opened] += dp[i-1][opened] From i-1 you have opened-1 number of segments. Since there is a need of increasing a[i] by one we are bound to open a segment here. [ dp[i][opened] += dp[i-1][opened - 1] //Typo in tutorial, see his solutionWe don't close here in any case as we will have opened -1 open segments after it.So ] and [] cases are ruled out. Also ][ will make a[i] = h+1 so its also ruled out.
•  » » » » 5 years ago, # ^ |   0 I have known it,thank you anyway
 » 5 years ago, # |   +3 I am unable to understand the solution of problem E ,would anyone like to explain the problem E ??
•  » » 5 years ago, # ^ |   0 if u dfs the final graph and traverse it preorder and write their discovery times, then u can understand whether a node is parent of another. and with dsu you can keep track of the nodes which are in the same group. using both of these you can understand whether someone signs a document or not
 » 5 years ago, # |   0 Hi, I submitted solution for problem E. My submission is http://codeforces.com/contest/466/submission/7796617 . I am getting runtime-error as verdict but when i run the same test case on my machine it worked just fine. Please someone tell me what might be the problem?
 » 5 years ago, # | ← Rev. 2 →   0 Err..I've made a mistake.... Just ignore me, please..
 » 5 years ago, # |   0 i got my problem B code accepted by O(n).
•  » » 5 years ago, # ^ |   0 How did you do it?
•  » » 2 years ago, # ^ |   0 Test cases are pretty weak. My O(n*sqrt(n)) code got accepted too.
 » 5 years ago, # |   0 There is typo in D (1) first case: it should be dp[i][opened] += dp[i-1][opened — 1]
•  » » 4 years ago, # ^ |   0 I wasted a lot of time bcoz of this typo in the editorial.Thank you.
 » 5 years ago, # |   0 In Problem D . We can close more than one segments as in the case a[i]+opened+2=h we can close 2 segments here, but in the Editorial it's considering the case of closing only one segment. Can anyone tell how it will produce right answer. Thanku...
•  » » 5 years ago, # ^ |   0 Don't know if you are still looking for answer, but in case you do: there is a restriction in the problem that you can't close more than one segment on each position. It's stated in the last sentence of the first paragraph.
 » 5 years ago, # |   0 sorry, i can not understand the solution of e, can anyone clear it, thank very much
 » 5 years ago, # |   0 Can anyone please explain the solution of 466D — Increase Sequence. I am unabel to understand the solution given in editorial.
 » 4 years ago, # |   0 Can anyone explain me solution D..??
 » 4 years ago, # |   0 Antoniuk nice fall :) For two contest you will beat Dreamoon.
 » 4 years ago, # | ← Rev. 3 →   +13 Problem-C 466C - Количество способов is exactly the same problem as 21C - Полоска 2 ...Nothing to say !!
•  » » 7 weeks ago, # ^ |   0 Thank you, I don't even get this editorial tbh very poorly written
 » 4 years ago, # |   0 Speaking of overkills, I solved C using a segment tree for range updates and queries. Basically, if i find an element in the prefix sum array to be sum/3 (sum=total sum in array) then i add it to a vector. If i find it to be 2*(sum/3), then I update that index in a segment tree with 1. That means that I can use this position as a marker.Now, iterate through all indices stored in the vector and for every index, query the segment tree from the index+1 to the end. This means that for the current index, we can use all the indices after that as the second marker (marker means demarcating the 3 segments from each other. We have 3 segments so it will be 2 markers). Answer is simply the sum of all this. Here is the AC solution. And yes, a Fenwick tree would've been better: 14711582
 » 3 years ago, # | ← Rev. 2 →   0 i am having problem understanding the solution of C.let’s iterate the end of first part i (1 ≤ i ≤ n - 2) and if sum of 1..i elements is equal S/3 then it means that we have to add to the answer the amount of such j (i + 1 < j) that the sum of elements from j-th to n-tn also equals S/3 .why not such j(i
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 If j = i + 1, there would be no 2'nd part.
 » 3 years ago, # |   0 In problem C why do we do cnt[i]+=cnt[i+1] and at the end ans+=cnt[i+2] ?
•  » » 3 years ago, # ^ |   0 Because if on some prefix sum is [S/3] we should add all the methods of getting exactly this sum on our suffix. Why [i + 2]? Because we should have 3 parts with exactly the same sum.
 » 2 years ago, # |   0 can someone plz explain the solution for c
 » 14 months ago, # |   0 In 466C, can anyone please explain why in cnt[] we add every i element with i+1?. And then why do we look for i+2 in sum?Why** i+2**?
 » 12 months ago, # | ← Rev. 5 →   0 I had serious difficulty in understanding the editorial of problem D. Took me a good amount of time to reach the solution. This comment helped a lot.Here's the approach: Firstly, if there exists an element in the array >= h, there is no way, so the answer is 0. Now, let dp[i][j] denote the no. of ways to make the first i points be equal to h s.t. there still remain j open segments after the point j. Now, there are 5 possibilities at a particular element: Don't open or close any segment here: In this case, we require j + a[i] == h and the no. of open segments after (i-1)st element must also be j. So, here we consider the no. of ways to make first (i-1) elements to be equal to h s.t. there exist j open segments after it. So, we add dp[i-1][j] to dp[i][j]. Open a segment here and don't close any: We require a[i] + j == h and no. of open segments after (i-1) must be (j-1). So, we add dp[i-1][j-1] to dp[i][j]. Close a segment here and don't open any: We require a[i] + (j + 1) == h since total contribution to ith element is by (j+1) segments (j which still remain open and 1 which is closed) and no. of open segments after (i-1) must be (j+1). Note here that there are also (j+1) ways to choose the segment we close at i. So, we add (j+1) * dp[i-1][j+1] to dp[i][j+1]. Open and close a segment here (length 1 segment): We require a[i] + (j + 1) == h and no. of open segments after (i-1) elements must be j. So, we add dp[i-1][j] to dp[i][j]. Close a previously opened segment and open a new segment: We require a[i] + (j + 1) == h and no. of open segments after (i-1) elements be j. Also, there are j ways to choose the segment to close. So, we add j * dp[i-1][j] to dp[i][j]. The answer to the problem is simply dp[n][0].Here's my submission: 45472102
 » 11 months ago, # |   0 The last line of the explanation of problem E is a little ambiguous. Here's the actual interpretation:...which we can calculate using dfs(). If v is an ancestor of u, then it must hold that in[v] ≤ in[u] and out[u] ≤ out[u].One more point: the above condition holds iff we ensure that in the final set of trees, every dfs performed on a tree starts at the root node. For this in the main loop of dfs(), for all the vertices processed in sequence, we can check if that vertex has not been visited and it is the root node of a tree (its indegree is 0), we can perform dfs starting from that vertex by calling a function that performs the dfs (say dfs_()). Here's my code: 46903908
 » 4 months ago, # |   0 I solved Problem "E"(Information Graph) using as usual Lowest Common Ancestor . Really it's a good problem for LCA.
 » 4 months ago, # |   0 I think minimum cost should be as my output but it's showing WA 57747709