### Roms's blog

By Roms, history, 3 years ago,

1223A - CME

Idea: Roms

Tutorial
Solution (Roms)

1223B - Strings Equalization

Idea: Roms

Tutorial
Solution (Roms)

1223C - Save the Nature

Idea: MikeMirzayanov

Tutorial

1223D - Sequence Sorting

Idea: Roms

Tutorial
Solution (Roms)

1223E - Paint the Tree

Idea: Neon

Tutorial
Solution (Ne0n25)

1223F - Stack Exterminable Arrays

Idea: Roms

Tutorial
Solution (Roms)

1223G - Wooden Raft

Tutorial

1240F - Football

Idea: MikeMirzayanov

Tutorial
Solution (arsijo)

• +112

 » 3 years ago, # | ← Rev. 2 →   +48 My solution of F: SpoilerWe add edges one by one. If we can't color edge(u, v) without changing color of other edges, there are 2 colors A and B: A is (min+2 of u && +0 of v), B is (+0 of u && +2 of u). We find maximum alternating trail from u, it means, we start from vertex s and repeat (go neighbor vertex by A), (go neighbor by B), (by A), (by B), .... as long as possible. We get trail of A,B,A,B... . Recolor it with B,A,B,A,... Surprisingly, we can color edge(u, v) with color A after recoloring.
•  » » 3 years ago, # ^ |   -83 That is E bro
•  » » 3 years ago, # ^ |   +8 We can build a bipartite graph with $2n$ vertexs.Here,we build an edge connect $x$ and $y+n$ if there is a match with team $x$ and $y$,$(x •  » » 5 months ago, # ^ | 0 You can prove that your solution is correct by bi-coloring the graph. If you can't color (u,v) with A in the end, it means the bi-partite graph has an odd loop, which is obviously wrong.  » 3 years ago, # | +5 Can someone explain the dp part in problem D a bit more clearly. •  » » 3 years ago, # ^ | +23 Here is my (very similar) approach, with identical DP part.Let$X$= input array, and let$Unique()$be removing all duplicates and$Sorted()$be sorting. Here are the key steps: Non-DP part1) All numbers can be split in 3 groups:$A$(ones that were moved to the beginning),$B$(ones that were not moved at all), and$C$(ones that were moved to the end). The resulting sequence in the end would then look like$Sorted(X)$= (some permutation of A)(original order of B)(some permutation of C)2) In other words, some prefix of$Sorted(X)$will contain all members of$A$, and some suffix of$Sorted(X)$will contain all members of$C$. The rest in the middle will be equal to$B$. The answer would then be equal to$|Unique(A)| + |Unique(C)| = |Unique(X)| - |Unique(B)|$. So, we need to maximize the number of unique elements in$B$.Formally, find the biggest sub-array of$Sorted(Unique(X))$such that its elements stand in non-descending order in$X$. DP-part3) First we iterate through$X$and note the first and the last occurrence of each number ($X_i \le N$, so it is$O(N)$).4) Then we iterate through$Sorted(Unique(S))$and each time check: if the last occurrence of$i$-th element goes before the first occurrence of$i+1$-th element, we increment the length of current satisfying sub-array; otherwise we reset the length of current sub-array to 1. Detailed explanationLet$dp[i]$be the longest sub-array of$Sorted(Unique(S))$ending at$i$-th element and satisfying aforementioned condition (its elements stand in non-descending order in X). Then, if the last occurrence of$i$-th element goes before the first occurrence of$i+1$-th element (meaning that the condition is satisfied for these two elements),$dp[i + 1] = dp[i] + 1$. Otherwise condition is not satisfied, meaning that the biggest such sub-array ending at$i+1$-th element is this element itself.The answer would be then the maximum value of all$dp[i]$. In fact, you do not need to remember all DP values, just the last one and the maximum one. Super-detailed explanationConsider X = (1 4 2 3 5 1 2 9 7) and Sorted(Unique(S)) = (1 2 3 4 5 7 9). Step 1: (1 2 3 4 5 7 9) ^ Current sub-array size = 1 (1). Max sub-array size = 1 (1).Do 1 and 2 stand in the ascending order in X? No (1 2 1 2). Reset current sub-array!Current sub-array size = 1 (2). Max sub-array size = 1 (1). Step 2: (1 2 3 4 5 7 9) ^ Current sub-array size = 1 (2). Max sub-array size = 1 (1).Do 2 and 3 stand in the ascending order in X? No (2 3 2). Reset current sub-array!Current sub-array size = 1 (3). Max sub-array size = 1 (1). Step 3: (1 2 3 4 5 7 9) ^ Current sub-array size = 1 (3). Max sub-array size = 1 (1).Do 3 and 4 stand in the ascending order in X? No (4 3). Reset current sub-array!Current sub-array size = 1 (4). Max sub-array size = 1 (1). Step 4: (1 2 3 4 5 7 9) ^ Current sub-array size = 1 (4). Max sub-array size = 1 (1).Do 4 and 5 stand in the ascending order in X? Yes (4 5). Update current sub-array!Current sub-array size = 2 (4 5). Max sub-array size = 2 (4 5) Step 5: (1 2 3 4 5 7 9) ^ Current sub-array size = 2 (4 5). Max sub-array size = 2 (4 5).Do 5 and 7 stand in the ascending order in X? Yes (5 7). Update current sub-array!Current sub-array size = 3 (4 5 7). Max sub-array size = 3 (4 5 7). Step 6: (1 2 3 4 5 7 9) ^ Current sub-array size = 3 (4 5 7). Max sub-array size = 3 (4 5 7).Do 7 and 9 stand in the ascending order in X? No (9 7). Reset current sub-array!Current sub-array size = 1 (9). Max sub-array size = 3 (4 5 7) Mega-detailed explanationCouldn't come up with.The answer is$|Unique(S)| -$(size of the biggest found sub-array). 62057262 •  » » » 3 years ago, # ^ | 0 omg!!! thanks for the effort ! Thanks a lot. •  » » » 3 years ago, # ^ | 0 You are an unsung hero, we salute to you sir!! •  » » » 2 years ago, # ^ | 0 Thanks for the nice explanation . •  » » » 2 years ago, # ^ | +8 comments like these help a lot while upsolving. thanks! •  » » 3 years ago, # ^ | +3 I had another solution, which is a bit slower and more complicated, but should pass TL. Actually we need to find something like LIS, but with two inserting cordinates. •  » » » 3 years ago, # ^ | 0 Can you add the link to your solution. •  » » » » 3 years ago, # ^ | 0 it doesn't work, i've just checked (or bug maby)  » 3 years ago, # | +30 In div 1 F, are these random solutions hackable? 62022214 62023134  » 3 years ago, # | 0 What is the complexity of the model solution to F? Is it possible to prove that it has a reasonable time complexity, or is it just "No idea of the complexity, but it seems to work fast enough"  » 3 years ago, # | +10 What is the time complexity of the model solution for F? •  » » 3 years ago, # ^ | +47 Or maybe I should have started by asking: why does this algorithm always terminate? •  » » » 3 years ago, # ^ | +14 Let's calculate$P(coloring) = \sum_{v} \sum_{c} deg_{vc}^{2}$where$deg_{vc}$is number of edges of color$c$incident to vertex$v$. One can see that$0 \le P(coloring) \le 2VE$always holds, and this function strictly decreases after one transform (if something was bad in at least one vertex). Therefore, number of iterations is at most$2VE$, one iteration can be done in$O(V+E)$time (finding euler cycle), and total complexity is$O(VE(V+E))$.If you assign colors randomly in the beginning, then for vertex of degree$d$expected value of P (restricted to that vertex) is$d+d(d-1)/k=d^{2}/k+d(1-1/k)$while theoretical minimum is$k(d/k)^{2}=d^{2}/k$. So, expected number of iterations is$O(E)$.  » 3 years ago, # | ← Rev. 3 → +80 Solved 1223F - Stack Exterminable Arrays in a more straightforward way in$\mathcal{O}(n \cdot log^2(n))$.Let's use divide and conquer and count number of subarrays that are going through the middle of array. We can simulate process of elimination with stack for each suffix of left part and for each prefix of right part. We can notice that some left part matches with some right part if and only if they have the same stacks. We can use hashes to quickly compare stacks and use maps, hash-maps or merging sorted lists of hashes to count the result. Not really optimized solution 62025172 works in$732 \; ms$. •  » » 3 years ago, # ^ | ← Rev. 2 → +31 If we know We can notice that some left part matches with some right part if and only if they have the same stacks., we can just count the number of pairs of the same stacks by storing hashes in a map instead of doing divide-and-conquer. The complexity will be$O(n \log n)$•  » » » 3 years ago, # ^ | +18 In my solution I am building left and right parts from some middle point, that's why I actually need D&C to cover everything. But your solution just calculates all the stacks from the beginning and says that the answer is$\sum_{distinct \; stacks} \binom{number \; of \; occurences}{2}$That makes further observation that is "if we are at some position$l$and we have added all elements from$a_{l \cdots r}$and stack configuration did not change so$a_{l \cdots r}$defines stack-exterminable subarray." So we can take any pair of positions with the same stack-from-beginning configuration as endpoints of correct stack-exterminable subarray. That is quite nice and simplifies things a lot. Thanks. •  » » 3 years ago, # ^ | +13 That's what I did too, but without hashes. Instead, I store the sequence of all stack states when adding elements to the left as a trie and to the right as a second trie. Then, I just find the tries' intersection (e.g. by basic DFS), count the number of states from the left part and from the right part corresponding to each vertex of this intersection and get the sum of their products. It's completely deterministic and with the same complexity when I store the edges from the tries in a map (using a hashmap instead actually slows down the program). •  » » » 3 years ago, # ^ | 0 it gave MLE if the memory wasn't freed for the nodes(of trie). My question is, do you'll always free memory for nodes after its use? Since it is done on the expense of time... •  » » » » 3 years ago, # ^ | +23 It's not at the expense of time unless you consider allocator/processor magic. For every malloc(), you need a corresponding free().Immediately cleaning up variables you don't need is a good thing for your memory (both computer and head).  » 3 years ago, # | +13 Alternate approach for D. observations: which element will we choose if we were to perform only one left operation, we will definitely choose the smallest element. same way if we had only one right operation we will choose the largest element.In general if we had x left operations we will choose the smallest x elements. Let us try to find out the minimum right operations needed if we could only perform L left operation. Let L be the number of left operations allowed and R be the number of right operations. We will find minimum of L + R where L will vary from 0 to N.For 0 left operations(i.e. only right ops allowed), if there exists a number X in the array such that Y is a number greater than X but is to the left of X we need to move this Y to the right end and since we move this Y to the right end we need to move all elements larger than Y to the right end as well. Hence find smallest such Y and move all elements to the right end that are greater than equal to Y. We can find number of elements greater than equal to Y in logN time which will be required ops R.Similarly for 1 left operation you may consider the same procedure only that the smallest element may be considered absent. for L left operations allowed consider 1st L smallest elements absent.https://codeforces.com/contest/1223/submission/62028221  » 3 years ago, # | ← Rev. 2 → +4 Hi all, my greedy idea for E was to simply sort the edges in non-increasing edge weight, then greedily take the largest edges as long as both of its vertices have enough in-degree to accept this edge. The intuition is similar to the greedy idea in Kruskal's MST algo. Can anyone poke a hole in this idea? I get WA on test case 3. (link to my code 62028517) •  » » 3 years ago, # ^ | +14 1 4 1 1 2 5 2 3 6 3 4 5 The answer for this should be 10 but your code outputs 6. •  » » » 3 years ago, # ^ | +5 thanks! •  » » » 16 months ago, # ^ | 0 thanks  » 3 years ago, # | +10 In 1223F — Stack Exterminable Arrays, why$nxtX_{nxt_i + 1}$will never be used again so that we can use swap? •  » » 3 years ago, # ^ | 0 I'm pretty sure it's provable that no 2 indices will have the same R value.  » 3 years ago, # | +29 P.S.: We decided to allow the O(Alog2A) solution which binary search x for each y to pass if it's carefully written. It's not like you could stop that anyway. Good luck distinguishing between$O(A\log^2 A)$and$O(A\log A)$where the extra factor is binsearch — you can't even use huge$A$without requiring insane constant factors from optimal solutions too. I implemented that and my solution runs in half a second without trivial optimisations like "stop binsearch when it's clear you can't improve the answer". •  » » 3 years ago, # ^ | +10 So it was a strategically wise decision.  » 3 years ago, # | ← Rev. 2 → +1 For 1223C/Div2C — Save the Nature, count(len) can be calculated in constant time by precalculating the prefix sum of sorted p. Then we don't need to do a binary search on the answer. This is my accepted solution https://codeforces.com/contest/1223/submission/62030690 •  » » 3 years ago, # ^ | 0 https://codeforces.com/contest/1241/submission/62043926Getting WA dk why •  » » » 3 years ago, # ^ | 0 firstly why are you doing this /* for1(i,m){ if(i%a==0 && i%b==0){ cxy++; } else if(i%a==0) cx++; else cy++; } */ inside your binary search .. there is no point in doing binary search then..i have done some corrections on your code and here it is accepted.. https://codeforces.com/contest/1241/submission/62047120 home work for you to find the mistakes!! •  » » 3 years ago, # ^ | 0 your code even after precalculating the prefix sum would find answer in linear time you can do binary search after precalulating if you want even though no effect on the overall tc.. as sorting is nlogn.. here is my accepted code with prefix sum and binary search on thathttps://codeforces.com/contest/1223/submission/62045245 •  » » 4 months ago, # ^ | 0 I have done with a similar approach but sorted x,y and x+y first. Why my solution is wrong?  » 3 years ago, # | ← Rev. 3 → 0 Can anyone help me finding what's wrong in my code of Paint the Tree, https://codeforces.com/contest/1240/submission/62017811It seems I was the only one who failed pretest 5, I did the same as mentioned in tutorial (just my notation is opposite, so dp[node][0] means node has taken atmost k-1 edges)I take pair of child's dp[child][0] + edge , dp[child][1] , and sort them by (p.F — p.S) > (q.F-q.S)then I iterate and take first k-1 pairs in both where x.F > x.S and one more for dp[cur][1],If x.S >= x.F or i already took the required edges, i take x.S •  » » 3 years ago, # ^ | +13 in C++, comparators should return false when element are equal !!! •  » » » 3 years ago, # ^ | ← Rev. 2 → 0 Woaah..!! It got accepted. I would never think that this can cause the problem. Can you please elaborate or give a link describing why it causes an error ??I used to think that when elements are same, it doesnt matter if comparator gives true or false. (If two elements have same order, it wont matter which gets placed firstEDIT : Got it thanks for your help. •  » » » » 3 years ago, # ^ | 0 Please tell why it causes an error. •  » » » » » 3 years ago, # ^ | ← Rev. 3 → 0 The compare function simply models a "less than" operator. Consider how the < operator works for primitive types like int:int a = 1, b = 2; a < b == true a is less than bint a = 2, b = 1; a < b == false a is not less than b, because a is greater than bint a = 1, b = 1; a < b == false a is not less than b, because a equals bReturning true means you want a to be ordered before b. So return false if that is not the case, either because you want b to be ordered before a, or because their order doesn't matter.If you return true when the arguments are equal, then you are saying that you want a to come before b and you want b to come before a, which is a contradiction. •  » » » » » » 3 years ago, # ^ | 0 Still confused.say a=b, and you return a<=b.so I want a before b. (or b before a. it wont matter, right? since a=b)what's the problem here? •  » » » » » » » 21 month(s) ago, # ^ | 0 so sorting process never ends  » 3 years ago, # | 0 D is really nice.  » 3 years ago, # | ← Rev. 2 → -9 Nice!  » 3 years ago, # | +5 Can anyone explain more this part of the editorial of problem D ?"For each integer l we want to find the maximum index dpl=r such that we can sort sequence a without moving elements in range l…r. We can do it with dynamic programming.Let's consider all integers occurring in sequence a in descending order s1,s2,…,st (si−1>si for each i from 2 to t). If maxInd(si) •  » » 3 years ago, # ^ | ← Rev. 4 → +8 Hello！ I would fain help you. (Sorry for my poor English.)First of all, the size of the specific value is meaningless.So we can reduce its value to$[1,t]$and all the numbers in the$[1,t]$appear at least once.The answer is obviously constructed as follows ：We can put$ l, l-1, l-2, ..., 1$one by one at the beginning of the sequence at the cost of$1$.After that , We should put$ r,r+1,r+2,...,t$one by one at the end of the sequence at the cost of$1$.If such a scheme is legal, then it must be guaranteed that the numbers in the middle are in order.However, the time complexity of such an algorithm is$O(n^3)$So, we can first determine the ordered interval in the middle, and then calculate the answers to the answers on both sides.We can define$dp[i]$for each i. This means one of the biggest extensions length which let$ i-dp[i]+1 , i-dp[i]+2 ... i$are ordered in the sequence.To calculate$dp[i]$, we should calculate MinInd[i] MaxInd[i] ($i \in [1,t]$) .First of all ,$ dp[1] = 1 $if$ MinInd[i] > MaxInd[i-1]$then$ dp[i] = dp[i-1]+1$else$dp[i] = 1$So , The answer is the minimum value of$t-dp[i]$($i \in [1,t]$)Now, the time complexity of the algorithm is$O(n)$My Code •  » » » 3 years ago, # ^ | +8 what a beautiful solution !  » 3 years ago, # | 0 It seems in problem D should be: "Let's consider all integers occurring in sequence a in descending order st,st-1,…,s1 (si+1>si for each i from t-1 to 1). If maxInd(si)  » 3 years ago, # | +4 The editorial of problem Div2 D seems to have a mistake. You first call$dp_l$, the index$r$, s.t. we can sort the sequence without moving elements$[l .. r]$. But, in the recurrence, you have taken$dp_l$to be the length of the sequence$[l .. r]$•  » » 3 years ago, # ^ | 0 Roms can you please correct it? It might be a difficulty for people who try to solve this problem later by reading the editorial •  » » » 3 years ago, # ^ | +5 Fixed, thank you  » 3 years ago, # | ← Rev. 2 → 0 For 1223C Solve the Nature, I am not satisfied with the fact that we need to check only if x>y.The terms a and b should also have a role.It can be that b is very small as compared to a.In that case even if x is smaller than y we would wish to allot greater ticket price to y% contributed tickets because they appear for every multiple of b which is very large as compared to a based on our assumption. I think in the solution suggested above it has been considered that a is smaller than b. Do correct me if i am wrong! •  » » 3 years ago, # ^ | ← Rev. 2 → 0 Well, x>y or y>x, a>b or b>a, all this stuff does matter only for easier implementation. I'll try to explain the main idea in pictures. I think it's easier to understand.Let's consider the particular case: Data that we haveSo, let we already sold n tickets. Than we got m for the Nature and m is the maximum value. How to find the m? If our segment has a and b blocks, than put the most expensive tickets there. After that, put the remaining tickets into a if x>y or b if x= k and n is minimal. So we need to find cont(n) for every n in range len(tickets). In our case it's 7. cont(n) from 0 to 7Well, in this case the answer will be 4, becuse k=240 and cont(3)=200, cont(4)=250.But we can notice that cont(n) is monotonous, because as n rises cont(n) rises.That's why the array [cont(1), cont(2), ... cont(len(tickets))] will be already sorted.And we want to find such element that will be >=k and its index will be minimal, what is the best way to do it? Of course it's left binary search. •  » » » 3 years ago, # ^ | +3 Thanks for the explanation!Now i get it. •  » » » 3 years ago, # ^ | ← Rev. 4 → 0 sardina Can you please explain your logic on this example: n = 9, p =[500, 500, 100, 100, 100, 100, 100, 100, 100], x=10, a=2, y=90, b=9, k=100 •  » » » » 3 years ago, # ^ | 0 ok, x < y, than we swap them. Now x = 90, a = 9; y = 10, b = 2; We do binary search on function cont(L), the graph would look like: values would be:(l, r]l = -1; r = 10; m = 4; cont(m) = 100l = -1; r = 4; m = 1; cont(m) = 0l = 1; r = 4; m = 2; cont(m) = 50l = 2; r = 4; m = 3; cont(m) = 50l = 3; r = 4: (r - l > 1)? -> false; we have found the lower boundr < n? -> true:answer: 4  » 3 years ago, # | ← Rev. 2 → 0 Hi,In problem E — Paint the Tree, I don't understand why I can use dp[v][k] since v and f can be up to 3 * 10^5. The solution of the Tutorial would be O(n * k), wouldn't?Thank you, Rosklin •  » » 3 years ago, # ^ | ← Rev. 2 → 0$f$is boolean flag ($f \in \{0,1\}$). So, we have dp[n][2], where dp[x][0] is optimal painting of subtree$x$not including edge to the parent, dp[x][1] is optimal painting of subtree$x$including edge to the parent. •  » » » 3 years ago, # ^ | 0 Thank you!  » 3 years ago, # | -11 please give me the solution of B in c++  » 3 years ago, # | 0 The editorial solution for D fails on this simple test. 1 2 5 6 Please change it. •  » » 3 years ago, # ^ | +4 Your test is incorrect. All$a_i$must not exceed$n$.  » 3 years ago, # | -11 sometimes i feel like a wet pile of crap  » 3 years ago, # | ← Rev. 2 → 0 Here's my solution for D (lol, it took about an hour to figure this one out):Firstly, in any legal sequence of operations all numbers moved to the left must be less than all numbers moved to the right (otherwise the resulting array is not sorted).So let's fix a number k, such that all numbers moved to the left are less than or equal to k, while all numbers moved to the right are greater than k. Some numbers may not be moved at all, for example if part of our array is 3 1 4 2 and we move all of them to the left, then we only need to move numbers 2 and 3, in that order.First we calibrate the array such that all numbers used are consecutive integers. Another way would be to declare arrays prev and next, and that's OK, since the numbers are relatively small.Now, let's say that we've fixed this k, and we need to decide how many numbers we need to move to the left so that the elements 1, 2, ..., k are sorted. It can be noticed that if there exists a sequence k - c, ..., k - 1, k (in that order), we do not need to do any operations with those numbers, since they are already relatively sorted! So we only have to move numbers 1 through k - c - 1.To find the longest such sequence (which results in the smallest number of elements that we need to move), we create an array up. up[i] — the length of the longest sequence of consecutive numbers (possibly, with intermediary ones) ending in i (sorted in increasing order). We can do this with a linear pass through the array.So, given a fixed k, the number of elements we need to move to the left, given that elements 1 through k must be sorted afterwards, is equal to k - up[k].We tackle the other case similarly. down[i] — the length of the longest sequence of consecutive numbers (again, sorted in increasing order) starting in i. So, the number of elements we need to move to the right, given that elements k + 1 through mark — the maximum number in the array must be sorted afterwards, is equal to (mark - k) - down[k + 1].For a given k, we sum those two values and receive the local answer. There's one catch, if there is an occurrence of k later than an occurrence of k + 1, we have to sort one of the pieces of the array entirely. We simply choose which one gives the minimum number of total operations.In this way, the answer is simply the minimum of local answers from 1 to mark - 1.By the way, it's only 80 lines of code in Java :)  » 3 years ago, # | -10 can we please have C++ solutions as well, as C++ is easy to understand for beginners.ps- it's my first comment  » 3 years ago, # | ← Rev. 4 → +90 Div1 D can also be solved by creating, for each$x \in [1,n]$a random vector$b_i$in 3D, setting$z_0$to a random 3D point, and then setting$z_{i+1}$to be the reflection of the point$z_i$along the direction of$b_{a_i}$. Then a segment (0-indexed)$[l,r)$of the array is stack exterminable iff$z_l = z_r$. Code  » 3 years ago, # | ← Rev. 3 → 0 Can anyone help me finding what's wrong in my code of Problem C, Save the Nature, 62077457update : got it  » 3 years ago, # | ← Rev. 2 → +6 I laughed very hard when i read this:You are an environmental activist at heart but the reality is harsh and you are just a cashier in a cinema.Maybe i'm already dead inside.  » 3 years ago, # | ← Rev. 2 → 0 update: got it.  » 3 years ago, # | 0 I solved Div-2 D with two pointer + BIT. Maybe it was an overkill, but quite intuitive, cause we need to maximize the range of numbers with no inversions between themselves. Brief explanationLet, inv = inversions between current two pointers. pos[i] = vector saving positions of all i in a. When shifting right pointer from r-1 to r, inv += bit.rangeSum(pos[r]+1,n). When shifting left pointer from l to l+1, inv -= bit.prefixSum(pos[l]-1)My solution: 62025259  » 3 years ago, # | 0 Can someone summarize Div2 E? I can't understand the statement.  » 3 years ago, # | +1 Can anyone suggest more problems like D?  » 3 years ago, # | 0 Hi all! How can I accelerate my code? I think my input is very slow 62119639  » 3 years ago, # | ← Rev. 2 → 0 Can someone please explain as to how we can calculate cont(len) in O(n) in Div2 C as written in tutorial, I tried but i can only come up with O(n^2).here Thanks!Update : Got it by using prefix sum array  » 3 years ago, # | 0 Can someone please explain the greedy approach of problem C,if we get priority to tickets which are numbered as lcm(a,b) then what is the guarantee of minimum no. of tickets sold if we are on one hand looking to maximize income?  » 3 years ago, # | ← Rev. 3 → 0 My code showing correct output but on submitting the results change .Am i doing something wrong while input or is it something else. P.S-I am new here:) My code to 'Save the nature' https://codeforces.com/contest/1241/submission/62256956  » 3 years ago, # | +5 In Div1 D, instead of swapping the maps$nxtX_i$and$nxtX_{nxt_i+1}$, it is also possible to move$nxtX_{nxt_i+1}$to$nxtX_i$using std::move in$O(1)$time by doing nxtX[i] = move(nxtX[nxt[i] + 1]).  » 3 years ago, # | 0 Hello,In problem E (Paint The Tree) is there any benefit to using a DP array? I was able to solve it without one, in this submission https://codeforces.com/contest/1223/submission/62262784  » 3 years ago, # | +8 D is very similar to AtCoder Grand Contest 24 — B: [](https://atcoder.jp/contests/agc024/tasks/agc024_b)  » 3 years ago, # | 0 Hello,Can anyone help me with 1223C? Here is my submission. What I'm doing: Sort the ticket values in non increasing order Create prefix array preSum Create a function check that takes$preSum,x,a,y,b$and the number of tickets to sell$n$.Working of check : Find an : number of tickets within n that have the x% scheme Similarly, find bn for the y% scheme. cn for the tickets that have both the schemes applicable. Tickets with max values should be placed at positions which have both the schemes applicable. Their contribution would be the presum of first cn items * (x+y) Then assuming that allocating the higher tickets to ath positions will yield a better result, we can find (presum of$a_n$items — presum of$c_n$items)$\times (x)$(as cn items are already taken from an). The rest is allocated to bn by: (presum of$a_n+b_n-c_n$items- presum of$a_n$items)$\times y $(as we only need$b_n-c_n$items next to the already used$a_n$items. Then doing the same assuming$b^{th}$positions will yield better results as compared to the$a^{th}$positions. The maximum of these two +$x+y$contribution is returned.$Finally$a binary search is done over$[1,n]\$. For the middle element, we use the check function, which yields the maximum sum for the middle element. If the sum is more than or equal to k, then it is saved in the variable ans. Once the search is complete, ans is printed.I do not understand where am I going wrong in here. Any help is appreciated!
•  » » 3 years ago, # ^ |   0 I spend almost half a day to find a mistake. I believe that: int an = n/a ; int bn = n/b ; int cn = n/(a*b) ; is wrongI had exactly the same test failed: Here is solution.But I don't understand why?
•  » » » 3 years ago, # ^ |   0 UPD: We could make solution faster if: intead of iterating like in tutorial var (cX, cY, cXY) = listOf(0, 0, 0) for (i in 1..len) { if (i % a == 0 && i % b == 0) cXY++ else if (i % a == 0) cX++ else if (i % b == 0) cY++ } we use lcm Accepted solution
 » 3 years ago, # |   0 What is the significance of m <= n*k in the tutorial of problem 1240F.
 » 3 years ago, # |   0 Div 2D and E are just amazing!
 » 3 years ago, # |   0 For problem C. Another idea to solve problem in linear time. Consider thug behaviour.You sell ticket, but you can take it back! Any time!Solution.
 » 2 years ago, # |   0 About problem F (div 1): There's a small mistake in the editorial:The difference between the two colors for each vertex should be at least 2, which happens when all vertex degrees are even and the Euler cycle length is odd. (for example, with the graph with edges [1 2, 2 3, 3 1])
 » 2 years ago, # |   0 can anybody tell me C
•  » » 2 years ago, # ^ |   0 C can be done in linear time using prefix sum https://codeforces.com/contest/1223/submission/81961631
 » 14 months ago, # |   0 please someone help me in problem b. how can we change string 1st to 2nd with this test case: ac ab ?
 » 4 months ago, # |   0 Problem C can also be solved using number theory. So, (number theory) tag can be added to the problem
 » 4 months ago, # |   0 To anyone(from the future) who is looking for Problem D's solution, I have a much easier logic for this problem.Hint 1: It is mentioned that in one operation we can take all occurences of a particular element and place it in beginning or the end. So does it really matter to actually do this operation?Key observation: We can reduce the problem to a longest increasing subsequence problem ,and if we know the longest ascending subsequence we can just subtract it from distinct elements to get the answer. Note: here we will actually look for the just previous element while making the longest increasing subsequence .eg: lets say we have 2 3 4 in our array in some order ,so we while we are at 4 we will just take 3 into account for updating our ans .After the above observation we can easily do this problem by using map data structure.