### 1-gon's blog

By 1-gon, history, 4 months ago,

omg hi!

1504A - Déjà Vu

Tutorial

Implementation

1504B - Flip the Bits

Tutorial

Implementation

1504C - Balance the Bits

Tutorial

Implementation

1504D - 3-Coloring

Tutorial

Implementation

1504E - Travelling Salesman Problem

Tutorial

Implementation 1

Implementation 2

1504F - Flip the Cards

Tutorial

Implementation

1503E - 2-Coloring

Tutorial

Implementation

1503F - Balance the Cards

Tutorial

Implementation

• +566

 » 4 months ago, # |   +15 omg hi!
•  » » 4 months ago, # ^ | ← Rev. 2 →   -34 hello :)
•  » » 4 months ago, # ^ |   +21 Hey
•  » » » 4 months ago, # ^ |   +5 Hey
•  » » » » 4 months ago, # ^ |   0 Hello!!!
•  » » » » » 4 months ago, # ^ |   0 Recursion
•  » » » » » » 4 months ago, # ^ |   0 Hi
 » 4 months ago, # | ← Rev. 2 →   -47 Nah, I am stupid. Have no idea but wait editorial here :<
 » 4 months ago, # | ← Rev. 2 →   0 bricked, (nvm this was a great round, i gained +35 rating despite literally getting 0 questions)
 » 4 months ago, # |   -40 imagine figuring that C out
•  » » 4 months ago, # ^ |   -27 Now just imagine!!
 » 4 months ago, # |   -13 Is there a proof to solution of C?
•  » » 4 months ago, # ^ |   0 After adding brackets for positions where $s = 1$ you can observe that when you add a new pair of alternating brackets your balance will never be lower than zero after putting the first bracket and it will come back to the original balance after putting the second one.
•  » » » 4 months ago, # ^ |   +8 Yes, that 'balance' thing is really nice way to approach. But could you please explain the part where we fill first $\frac{k}{2}$ 1's with opening brackets and the rest with closing?
•  » » » » 4 months ago, # ^ |   0 I must say most times editorials are written in hurry. No offence but it's what I think.
•  » » 4 months ago, # ^ |   +22 Imagine a 2d plane where (x,y) = (no. of unclosed open brackets in first sequence, no. of unclosed open brackets in second sequence). We can then map the 4 possible moves:-> adding a '(' to first string when s[i]=1 => we go from x,y to x+1,y+1-> adding a '(' to first string when s[i]=0 => we go from x,y to x+1,y-1.. and similarly for adding ')' in both cases, we get opposite moves.We start at origin, and our objective is to return to the origin after n moves without crossing any of the axes. If you draw it out on paper or something, it will be clear that by following the given strategy, we either stay on the x = y line or x = y + 1 line, and dont cross any of the axes, unless the string begins or ends with a 0.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +9 Wow! This approach is really interesting. Thank You!Your explanation is truly fantastic, I tried to rebuild it on my own, and it's super amazing!
•  » » » 4 months ago, # ^ |   +1 Nice visualization. Helpful. Thanks!
•  » » » 2 months ago, # ^ |   0 thanks! this visualisation made it much more clearer
 » 4 months ago, # |   -39 Lightning fast editorial. Amazing
 » 4 months ago, # | ← Rev. 2 →   +184 Me : *trying to push monogon contribution to moon Monogon : *making greedy problems that shove my rating into dirt*sad cat noises
 » 4 months ago, # |   -26 Thanks for fast editorial.
 » 4 months ago, # |   -30 E is a good problem! I'm so close :(
 » 4 months ago, # |   0 well, this was fun
 » 4 months ago, # |   +65 Constructiveforces.
 » 4 months ago, # |   0 Sry，I went to the wrong place ，I come back to div3 immediately TAT
•  » » 4 months ago, # ^ |   +3 You are not alone...
 » 4 months ago, # |   -19 Thanks for the editorial which proved my stupidity.
 » 4 months ago, # |   -13 Wow!! Fast editorials really helps. Thanks.
 » 4 months ago, # |   0 In E's solution 1 why only need to add i-> j+1? (i.e. don't need i->j+2....)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +8 it's at least as cheap to go i->j+1->j+2 as i->j+2 because you get to subtract $c_{j+1}$. There's always a path from j+1 to j+2 because of either edge 3 or a combination of the edges from 1 and 2.
•  » » 4 months ago, # ^ |   +17 It can be proved that $cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$. The following is the proof. Since $a_i$ is increasing and $cost(i,j+1)=a_{j+1}-a_i-c_i$, therefore $cost(i,j+2)=a_{j+2}-a_i-c_i$. So $cost(i,j+2)-cost(i,j+1)=a_{j+2}-a_{j+1}\ge \max(0,a_{j+2}-a_{j+1}-c_{j+1})=cost(j+1,j+2)$. Therefore, $cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$, so we needn't add $i\ \rightarrow j+2$.
•  » » » 4 months ago, # ^ |   0 if ci is big and ci+1 is small then the expr is not true,right?
•  » » » 4 months ago, # ^ |   0 Maybe https://codeforces.ml/blog/entry/89319?#comment-777539 is what you want I guess.
 » 4 months ago, # |   -13 omg hi cyan
 » 4 months ago, # |   -6 Can anyone proof solution of problem Div.2 D?
 » 4 months ago, # |   -13 damn, I was correct for E. Just 10 min left to implement so couldn't implement in time. I wish I didn't cost much time at B
 » 4 months ago, # |   -17
 » 4 months ago, # |   -18
 » 4 months ago, # |   -27 Pretest for div2B was very weak. Don't know why my O(n) solution exceeded the time limit 111887915
•  » » 4 months ago, # ^ |   0 Your code is O(n^2) in the worst case since you are doing string z = b + z
•  » » » 4 months ago, # ^ |   0 Thanks got it!
•  » » 4 months ago, # ^ |   +89 You should probably look up what weak pretest means before commenting.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Sorry for my bad statement. But my solution passed the pretest with O(n*n) approach. And then failed the system tests.
 » 4 months ago, # |   0 Great problem set!!! 1-gon orz
 » 4 months ago, # |   0 Glad that Div2C, D, and E all passed in python3 even without pypy3!
 » 4 months ago, # |   0 StringForces
 » 4 months ago, # |   0 one of the greatest contest i have ever partipicated in . thanks to the author. Waiting soon for ur next contest
 » 4 months ago, # |   0 If anyone wants to see how I overkilled 1C with 2 segment trees and coordinate compression and then forgot to sort wrt $a[]$ and couldn't get AC in contest : 111939130
 » 4 months ago, # |   +6 Sorry I am stupid but can you elaborate div1C solution 2's formula
•  » » 4 months ago, # ^ |   0 python: 111931953C++: 111890876Essentially each city must have an outgoing cost of its floor. Additionally, we're going to need to pay the cost max(a) — min(a). However, if we use a sequence of cities to go from min(a) to max(a), we can use the floors to "pay" for max(a) — min(a). In other words, we only need to pay for the parts of the segment from min(a) to max(a) that aren't already paid for by the floors of the cities along the way.
•  » » » 4 months ago, # ^ |   +10 I mean I can understand the dijkstra one and everything before, but I can't understand why the formula in solution 2 is true.
•  » » 4 months ago, # ^ |   0 I think its missing the sum of c , otherwise it should be correct . the summation in the editorial is counting how much extra cost we have to pay to reach i if we can jump from any city j with j
•  » » 4 months ago, # ^ |   +29 I didn't understand either. I think the wording is kind of confusing.
•  » » » 4 months ago, # ^ |   0 The formula is $max(0,a_j-a_i-c_i)$. There are two cases. If $a_j>a_i+c_i$ then $a_j+c_j$ must update the greatest value. Otherwise $max(0,a_j-a_i-c_i)=0$ and it won't contribute to the answer.
•  » » » 4 months ago, # ^ | ← Rev. 5 →   +75 I think we actually need a detailed analysis to justify the formula. Maybe I am just not that good for having the intuition, though.Here is the analysis, consider constructing the path from a1:Lemma 1. Consider without max(0,), it is always beneficial for us to break one step into two steps.proof: two step cost is a[3]-a[2]-c[2] + a[2]-a[1]-c[1], one step cost is a[3]-a[1]-c[1], since c[2]>0 the two step cost is better.Now add max(0,) back, so sometimes breaking steps are useless (but never worse).Lemma 2. To reach the i-th block, the one step with minimum cost is from j with max a[j]+c[j] before.proof: I am not considering the steps before j but only this step, this should be trivial.Now let's call this maximum a[j]+c[j] "premax". (prefix max)Lemma 3. If we reach some i such that a[i]>premax, than a[i]+c[i] becomes new premax in the next iteration. Let's call such i "breakpoint". Also note that when reaching a breakpoint, the cost>0 so max(0,) is useless and thus we can apply Lemma 1 later.proof: Because c[i]>0. So a[i]+c[i]>a[i]>premax.Combine these all, we would obtain the strategy. Strategy:Suppose we are standing at some certain block, then we can keep going right and update premax with zero cost until we reach a breakpoint. Then because of Lemma 1 we should make a step to the breakpoint, and because of Lemma 2 we should go from the premax we've found. Because of Lemma 3, paths like this won't happen: i -> j -> i -> k (where a[i]+c[i] is the premax for both j and k) since j would be the premax for k. So we won't need to step on a premax twice, which allows us to reconstruct a Hamiltonian Cycle later. Thallium54 Although not rigorous, hope this helps.
•  » » » » 4 months ago, # ^ |   +8 Lemma 1 is important. Thanks for the explanation.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +24 I think this is the reasoning behind the formula: we want to get from $a_1$ to $a_n$ in a number of steps, with the minimum cost. If these steps are $s_1, s_2, ... s_k$, with $s_1 < s_2 < ... < s_k$ ($s_1 = 1$ and $s_k = n$), then the path will be $a_{s_1}, a_{s_2}, a_{s_3}, ..., a_{s_k}$. So the $a_i$ not included in the step series will be the nodes on the path from $a_n$ to $a_1$.In the summation, I found it a bit easier to do it backwards (from $n$ to $1$, the final answer will remain the same): so, firstly, we want to see from which node $a_j$ we get the best cost from $a_j$ to $a_n$ and, as the editorial shows, it's the $j$ with the maximum $\max(a_j+c_j)$. So this $j$ will be the the step $s_{k-1}$. Then, when we have $i = j$, we update the $j$ index for the next best $\max(a_j+c_j)$ and this new $j$ will be $s_{k-2}$. We repeat this process until we reach $i = 1$, when we know for certain that we have calculated the whole step series (because then we just get that $s_1 = 1$, which we already knew). So basically we construct the path from $a_1$ to $a_n$ edge by edge, the only difference between my explanation and the editorial being the order in which we construct the step series. The $i$ indexes for which we have $a_i-\max_{j •  » » » 4 months ago, # ^ | +6 All the proofs above are extremely cool and clear up the whole idea. Colin's stream has also a similar proof. I got it from there. Folks can see there too if they are still unsure. •  » » 4 months ago, # ^ | ← Rev. 3 → +25 I guess I'll also put my proof here, since I've been thinking about it for a while.The problem is the following: you are given a weighted directed graph with$n$vertices (numbered from$1$to$n$). The$i$th vertex has outgoing edges to all vertices$j < i$with weight$0$, and outgoing edges to all vertices$j > i$with weight$\max(0, a_j - a_i - c_i)$. What is the weight of the shortest path from vertex$1$to$n$, plus$\sum c_i$?This problem is equivalent to the original problem, because any path from vertex$1$to$n$in this problem can be turned into a tour in the original problem with the same cost: simply follow the same cities along the shortest path from$1$to$n$, and then visit all unvisited cities (plus city$1$to complete the tour), in decreasing order. Furthermore, the weight of the shortest path from vertex$1$to$n$is a lower bound for the answer in the original problem, since some path from city$1$to$n$must exist in the tour.To find the weight of the shortest path from$1$to$n$in the new problem, define$dp[i] := \max(0, a_i - \max\limits_{j < i}(a_j + c_j))$for$1 < i \leq n$(same expression as in the editorial) and$dp[i] := 0$for$i = 1$. Let's prove that the weight of the shortest path from$1$to$n$is equal to$\sum\limits_{i = 1}^{n} dp[i]$using induction from$1$to$n$.Our inductive hypothesis is the following: suppose we're at step$k$; then for all$1 \leq j \leq k$, the weight of the shortest path from vertex$1$to$j$in the subgraph containing the first$j$vertices is equal to$\sum\limits_{i = 1}^{j} dp[i]$. This is true for$k = 1$, because the weight of the shortest path from vertex$1$to$1$in the subgraph containing one lonely vertex is$dp[1] = 0$.Now suppose we're at step$1 < k < n$and that the inductive hypothesis is true for$k$; let's show that the inductive hypothesis is true for$k + 1$. There must exist some last directed edge$(u \rightarrow k + 1)$in some shortest path from$1$to$k + 1$.Firstly, let's show that all previous shortest paths don't change by adding vertex$k + 1$to the subgraph. Suppose that there exists some$1 \leq j \leq k$such that the shortest path from$1$to$j$decreases by adding this new vertex. Then one such new path must be a concatenation of some shortest path from$1$to$u$(in the subgraph containing the first$k$vertices), plus the edge$(u \rightarrow k + 1)$, and then the edge$(k + 1 \rightarrow j)$. If$j \leq u$, then the previously computed shortest path from$1$to$j$must have been at least as good, since prefixes of$dp$are monotonically increasing. If$j > u$, then the concatenation of the shortest path from$1$to$u$, plus the edge$(u \rightarrow j)$, is at least as good, because the weight of the edge$(u \rightarrow j)$is less than or equal to the weight of the edge$(u \rightarrow k + 1)$. Either way, there is a contradiction.Now let's show that the weight of the shortest path from$1$to$k + 1$in the subgraph containing the first$k + 1$vertices is equal to$\sum\limits_{i = 1}^{k + 1} dp[i]$.Welp, my tablet pen clicked outside of the comment box, so I lost a bunch of work... Just gonna give up here... In short, the idea is the following: let$j$be the greatest index such that$dp[j] > 0$, or$j := 1$if no such index exists. Then it must be true that$u \geq j$. Since all prefixes past$j$are the same, it doesn't matter from which one we transition from. So we can just choose the index$j \leq i \leq k$with the maximum$a_i + c_i$value, and transition from that. Turns out, the maximum$a_i + c_i$value in general (for$i < k + 1$) must lie in that range. •  » » 4 months ago, # ^ | ← Rev. 2 → +1 After reading the explanations here, I was able to understand a bit more about the formal-"why does it work", but I still had not intuitive-"why does is work". After sleeping and thinking and trying, what finally helped me understand it, in the editorial we have this implementation:  sort(ve.begin(), ve.end()); long long mx = ve[0].first + ve[0].second; for(int i = 1; i < n; i++) { ans += max(0LL, ve[i].first - mx); mx = max(mx, ve[i].first + ve[i].second); } I didn't get how this works, and why this works. I made another implementation for myself.  sort(ve.begin(), ve.end()); long long mx = ve[0].first + ve[0].second; for(int i = 1; i < n; i++) { if(ve[i].first + ve[i].second >= mx) { ans += max(0LL, ve[i].first - mx); mx = ve[i].first + ve[i].second; } } It is pretty much the same... I added an if-statement and removed the max(mx, ...) from calculating mx. But it changes one thing, which helped me understand this. The summation to sum is more explicit. We only add something, if we can improve our mx. This means we check each city from the ugliest city to the most beautiful one and always enter a city if we can improve our mx. The algorithm is 100% greedy now. It's also the same as in the editorial. ve[i].first - mx > 0 implies ve[i].first + ve[i]second > mx. So we also only add when we can improve mx. I have no prove why this works, but this helped me on the "intuition"-part, why it should work. •  » » » 4 months ago, # ^ | +3 You can see my comment for the proof. I agree that my explanation makes the solution not intuitive.  » 4 months ago, # | 0 B was so hard for me:( i'm solve it after 1 hour. •  » » 4 months ago, # ^ | 0 I spent like an hour trying to figure out what's wrong, to find one missing equal sign :? •  » » 4 months ago, # ^ | +9 How many hours do you code per day bro? Your graph is scary  » 4 months ago, # | -68 shit contest  » 4 months ago, # | +2 Those who solved div2C,how do you guys think of that solution? •  » » 4 months ago, # ^ | 0 I have the same question :) •  » » 4 months ago, # ^ | +3 This was my approach during the contest.The first and last char should be 1 because if it is 0 at any of these positions then the string can't be complete {i.e they will look like (...( and (...) }. For the answer to exist, the count of 1 and 0 should be even (self explanatory) and the prefix sum in both the string should be >=0 at any index, if we give +1 for character being '1' and -1 for being '0' and total sum should be 0. (just like we do in checking balanced parenthesis).For finding the strings: For index with val = 1, put '(' for half the times and ')' for other half. {Eg- If the string is 11100111, then both the strings will be initialized by (((00))) } For index with val = 0, start with ( and alter for rest of the indices for the 1st string and for obtaining the 2nd string, start with ) and then alter. {Eg — If the string is 1001000011, then x = 1()1()()11, y = 1)(1)()(11 and one can be substituted by the above method }If you carefully observe, this procedure basically leads to prefix sum >= 0 at every index. •  » » 4 months ago, # ^ | +1 uh.. I am not satisfied with the solution.. probably because I couldn't come up with a convincing proof..To add on that I thought that perhaps the editorial would have some mention of proof (up to the part of even number of zeroes it is fine) but it seems the construction just works in favour over any other possible construction you can manage to do..So you can do some drawing on paper and see that you want to keep the stuff as close to 0 otherwise the bracket sequences will diverge and I guess that's closest to what can be called a proof. (What hasn't been mentioned though that the prefix sum criteria is usually followed with this construction i.e prefix sum >= 0 except for 1 — 2 cases, the only thing which needs to be taken care of is to get a final sum of 0 and this construction works in favour of it)  » 4 months ago, # | 0 While I figured out the first two observations mentioned in C's editorial, how do I arrive at the idea to populate the first k/2 1's with '(' and the last k/2 1's with ')' and then alternate the 0-positions?Does anyone have any advice on what I need to think about or ask myself, to reach this idea? •  » » 4 months ago, # ^ | +8 Since the string must always end with a '1' and start with a '1', all '0's will be sandwiched by '1's, so it would look like ((( ()()() ))) and ((( )()()( ))). The net number of '('s is simply carried forward by the ()()() or )()()(. hope this tells you something new... •  » » » 4 months ago, # ^ | 0 I see, so the idea that the 0's in the input string will have zero long-term effect on the running sum if they're alternating, allows me to handle the 1's separately and then just fill in the 0's with alternate brackets.Had I thought of input strings like 110011 or 1111000011 then this may have struck me, but I got confused with imagining inputs which had alternating 1s and 0s.Anyway, thanks!  » 4 months ago, # | 0 is there a proof for Div2C? •  » » 4 months ago, # ^ | ← Rev. 2 → +1 ProofStandard parenthesis validity checker: counter++ for '(', counter-- for ')'. The sequence is valid is counter is always non-negative and hits zero at the end. Now, let's assume the string starts with '('. Counter = 1.Every time string A[i] = B[i], we have either a counter++ or counter-- at both places.So, it's safe to do the counter++ for the first half and the other for the second. For A[i] != B[i], every 2 0s, can reset counter to 0 in both the strings. If the number of 0s is odd, there's an unsymmetrical counter residue that cannot be cleared by the equality case (as the equal case adds the same number to both A and B). From these observations, there needs to be even number of 1s and 0s.First half of 1s should be open, 2nd half of 1s closed.Odd-even flip of paranthesis order for 0s.  » 4 months ago, # | ← Rev. 2 → -14 Is it just me who lost problem D because the pretests didn't have the n=2 case?? I'm deeply saddened by this and it has affected my confidence. Was this a conspiracy against negligent coders like me?? (sobs profusely.)Forgot to thank the creators for this amazing contest. The problems were really fun and they kept me at the edge of my seat! •  » » 4 months ago, # ^ | 0 The very first pretest was n = 2 though... •  » » » 4 months ago, # ^ | -16 oh sorry, but i failed the 16th test case which had n=2, i must now proceed to quit codeforces, thanks for pointing out. bye. i will now delete all my comments  » 4 months ago, # | +1 I was just an '=' away from getting AC on B. Oh Man! This is such a drag.  » 4 months ago, # | 0 C problem actually requires backtracking to alternate 0 positions with open and close brackets.  » 4 months ago, # | +1 I don't understand why my n^4 solution passed in Div 2 D, here is link https://codeforces.cc/contest/1504/submission/111924524 •  » » 4 months ago, # ^ | +6$n$is only$100$and constant factor is pretty low and time limit is$3$secs.  » 4 months ago, # | -6 IMO only the ones that solved C will understand its editorial.  » 4 months ago, # | 0 (A + B) VIDEO EDITORIAL : https://www.youtube.com/watch?v=2DBLj6IOJJc •  » » 3 months ago, # ^ | 0 nice  » 4 months ago, # | 0 Alternative solution for 1504E - Travelling Salesman ProblemBasic observation is similar. Cost for$i→j$is$c_i + max(0, a_j - (a_i + c_i))$. There is another thing to look for. We can start from any city instead of city$1$and still get same answer as our path is a cycle. That's how, we can just sort the cities based on$a_i$. Now, starting from the lowest$a_i$city, we can go one by one and we can do transition from most optimal city to current city based on$(a_j + c_j)$values.Code — 111946687 •  » » 4 months ago, # ^ | +3 Proof? •  » » 4 months ago, # ^ | +9 This is literally the second solution in the editorial. •  » » » 4 months ago, # ^ | 0 My bad, didn't understand what he meant at the 2nd solution, it looks like implementation is exactly same. Now I just noticed that sorting was mentioned in the very beginning. •  » » » » 4 months ago, # ^ | +2 I couldn't understand either. Can you elaborate your solution? •  » » » » » 4 months ago, # ^ | 0 I am not entirely sure if this proof is correct, but this is how I convinced myself of this solution. Sort array a. So we have a1<=a2<=a3....<=anWe start at a1. We want to greedily spend as little as possible. That is it would be locally preferable to have a 0 cost on going to the next city. Consider the set S of all cities having ai <= a1+c1. Obviously, S would be of the form {City 2, City 3...., City k} for some k.(City i has value (ai,ci). a is increasing after all:/).Now, simply go to city 2, There are two cases a2+c2 < a1+c1. In this case, having a1 in the front is better than having a2, since from a1 we can go to more cities free of cost. So we try rearranging the visiting pattern. We start from a2. Visit a1 free of cost since a2+c2>a1. Now, we have a1+c1 again at the front and we can visit other cities in S free of cost. In the other case, a2+c2 > a1+c1, in this case, don't change the ordering since a2+b2 in front would allow us to potentially visit even more vertices free of cost than those contained in S.This can be expanded to arbitrary lengths by induction. Say that you have observed {City 1, City 2, City 3,...., City k-1} and found a permutation such that the city with the maximum value of (ai+ci) observed so far (call it j) is in front. We prove that there exists an optimal ordering with this property. By Induction Hypothesis, assume this works for k-1. Then, The order of visit so far will then be {'Some other cities in some optimal order', City j} and this is the most optimal of all orderings possible with the available cities. Now the next city k can have 3 possibilities. Case 1: a_k > a_j + c_j In this case, there is no way to get 0 costs using any of the previously visited cities. Using aj+cj which is the maximum observed so far is the best choice in minimizing the current cost(a_k — (a_i+c_i)) for any i a_j + c_j. Again keep the order as {'Same order as before',City j,City k}. This involves 0 cost and the front element (k) has the maximum { ai+ci } value observed so far. We have expended 0 extra cost here!.Case 3: a_k <= a_j + c_j and a_k+c_k <= a_j + c_j. This time we would like City j to be on the front and at the same time expend 0 extra costs for visiting City k. The solution is to simply visit City k first. The resulting order will be {City k,'Nothing changes in between', City j}.Proceeding this way, this strategy optimises the local value every step of the way and hence would give us the globally optimal solution.Please correct me if I am wrong.  » 4 months ago, # | +1 Can anyone provide a logical chain of Div2C? I understand how the answer is constructed but I am confused about how we come up with the idea from scratch and know its correctness. •  » » 4 months ago, # ^ | 0  » 4 months ago, # | 0 Can anyone help with the TLE error for div2B My solution •  » » 4 months ago, # ^ | 0 This code is O(n^2).This line is actually c!=s1.length() O(n) in nature followed by for loop. U should use simulation starting from rightmost unmatching bit and using flips as a variable. •  » » » 4 months ago, # ^ | 0 Thanks it worked :)  » 4 months ago, # | 0 traveling sales man problem is NP hard so how it's possible to solve problem DIV2 E or DIV 1 C for given constraints ? •  » » 4 months ago, # ^ | +86 OK •  » » » 4 months ago, # ^ | +4 Thanks very useful response . •  » » » » 4 months ago, # ^ | +86 YES •  » » 4 months ago, # ^ | +9 The problem given wasn't actually traveling salesman. It was a variation which could be solved much faster when you make some observations.  » 4 months ago, # | 0 Is there a way I could look at test case 60 and like that for a pretest. It is shown for the first few testcases like till 30 approx. . I wanted to know if I could download or view the complete test case file or at least the first test case where I made mistake . Is it possible ? •  » » 4 months ago, # ^ | 0 1 8 10011001  •  » » » 4 months ago, # ^ | 0 very thanks for help, that was what I needed . How can one find it? •  » » » » 4 months ago, # ^ | 0 I generated random string with length 8 and compare your solution verdict and mine (AC solution) verdict •  » » » » » 4 months ago, # ^ | 0 Great. Thankyou for help again sevlll.  » 4 months ago, # | +10 omg hi !  » 4 months ago, # | 0 I'm having an issue with a corner case on test case #64 with the second tests run, anyone got ideas? Check my profile with my last submission  » 4 months ago, # | 0 The solution described for C Div. 2 would give identical strings in case the input has only 1's. Is that the expected behavior or those should be different? •  » » 4 months ago, # ^ | 0 Did you mean deterministically single answer for a fixed length?If so, yes, although there can be other valid answers. The strings being identical is the expected behavior.All 1s indicate that all positions are equal, which implies equal strings.  » 4 months ago, # | 0 To decompose an array into two decreasing subsequences, there is a standard greedy approach.Can you share it please? •  » » 4 months ago, # ^ | ← Rev. 2 → 0 https://www.google.com/amp/s/www.geeksforgeeks.org/minimum-number-of-increasing-subsequences/amp/(just swap the terms increasing and decreasing)Essentially you build some sequences as you process the elements. Always add an element to the end of the first possible subsequence. •  » » » 4 months ago, # ^ | 0 Can you please explain what's Wrong with my Code in D: 111943902 •  » » » » 4 months ago, # ^ | 0 wrong answer Integer 3 violates the range [1, 2] It seems that when you output b, i, j, the coordinates (i, j) are out of bounds. •  » » » » » 4 months ago, # ^ | 0 tnx got It :)  » 4 months ago, # | +6 Greedyforces •  » » 4 months ago, # ^ | 0 So many greedy problems! (I love greedy!)  » 4 months ago, # | 0 How to solve 2F/1C for dp •  » » 4 months ago, # ^ | 0 maybe it's impossible  » 4 months ago, # | ← Rev. 8 → -16 I tried implementing prob D in python.It gave runtime error on TC1. But the code works fine on my local compiler. Can anyone please point out what is wrong in it. Thanks in advance.nipungoel11 can you please helpdorijanlendvaj can you please help •  » » 4 months ago, # ^ | ← Rev. 2 → 0 given s = {1,2,3} My strategy is to consider that element from s that is different from : Alice input the element above that position if it exists (matrix[i][j-1]) the element before that position if it exists (matrix[i-1][j]) We are going sequentially from left to right and row-by-row, so we need not consider the element after that position (matrix[i+1][j]) and below that position( matrix[i][j+1]).After getting the element from s that is different from all of those position, I will fix that value as the color of that position and move for next position after that and so on.My issue is not that I will get WA or TLE . My problem is that why I am getting RE on my present code. Any help would be appreciated!! Thanks. •  » » » 4 months ago, # ^ | 0 Consider input:21 2 1 2There is no correct choice for last move. So, your bob_poss list is empty and you have "list out of range" error. •  » » » » 4 months ago, # ^ | 0 Thanks man for pointing it out! Appreciate it! •  » » » » 4 months ago, # ^ | 0 Would you be able to help in this solution for D ? I'm essentially doing the same checkerboard thing by keeping the track of odd sum and even sum matrix cells. SUBMISSION : 112126961  » 4 months ago, # | 0 YESorNOforces  » 4 months ago, # | ← Rev. 2 → +3 Although I always lose rating in your contests, I really like your problems :)  » 4 months ago, # | 0 Anyone please help me in C , Here is my submission 1504CI have taken two characters from string at a time and created two brackets array according to them(if first two chars are 10)10 -ch1+=()ch2+=((11 — ch1+=()ch2+=()01 — ch1+=()ch2+=))This is done iteratively and at last i checked both brackets array for balance using stack then accordingly printed "YES" or "NO"I am not able to figure out why it is failing in test case 2 only . •  » » 4 months ago, # ^ | +3 Consider the following case: 10010101Now as per your algo: a = ()()()() b = (()))))) And so you will print "NO". But it is possible to find valid bracket sequences and they are as follows: a = (()(())) b = ()(())()Hope this helps. •  » » » 4 months ago, # ^ | 0 Thanks a lot nipungoel11 , i got my mistake .  » 4 months ago, # | 0 111968151 For problem A, Insert 'a' into the symmetrical position of the first letter that is not equal to 'a', why it is wrong ? •  » » 4 months ago, # ^ | ← Rev. 2 → 0 You should insert it into the position n-i, not n-i-1. For example, on the test case bab you output baab instead of baba. •  » » » 4 months ago, # ^ | 0 Thanks for reminding! I misunderstood the usage of insert  » 4 months ago, # | ← Rev. 3 → 0 https://codeforces.cc/contest/1504/submission/111914872 my code runs well if i use Sytsem.out.println. But when i append my ans on bufferWriter it does not show the String with extra 'a' in codeforces ide but when running on my eclipse ide it gives correct output. Why is it so? •  » » 4 months ago, # ^ | 0 That isn't the only difference between your codes. You also changed i  » 4 months ago, # | ← Rev. 2 → 0 I think in the editorial of Problem E, it should be mentioned that it is always optimal to go from i to j+1 instead of j+2,j+3,j+4 etc....  » 4 months ago, # | -17 1-gon, COCU XYU  » 4 months ago, # | 0 111918468 Problem C, what's wrong with my answer? Input: 4 1111 Output: YES ()() ()() Checker: wrong answer a[i] = b[i] <=> s[i] = 1 broken at i = 1 Thank's for help) •  » » 4 months ago, # ^ | +7 On the test case141011You don't output anything. •  » » » 4 months ago, # ^ | 0 dorijanlendvaj, real. Thank's a lot.  » 4 months ago, # | ← Rev. 2 → +1 People after submitting C : Well prob was easy , i can go to D now. . . . test-case 64 : You ain't going anywhere.  » 4 months ago, # | ← Rev. 2 → 0 can anyone please tell what's wrong in my code:112000170 of div2-D. for 1st test case : 2 1 2 1 3 my output is : 2 1 1 1 1 2 3 2 1 2 2 2 but jugdement is showing conflict on (2,2) and (2,1) please tell my whats wrong  » 4 months ago, # | +3 Could someone please explain why in the last part of the tutorial of Div1D "there is a unique way to decompose each segment"? •  » » 4 months ago, # ^ | +23 Took me a while, but I think I figured it out. Suppose that we're trying to find a decomposition for some segment$[a, b]$($1 \leq a \leq b \leq n$). Let's maintain two subsequences$s_1$and$s_2$, initially empty at the start of the segment. Without loss of generality, let's immediately add$f(a)$to the end of$s_1$. Now let's greedily choose placements for all characters in the range$[a + 1, b - 1]$(yes, this is intentional).Firstly, let's define$s(i) = \max\limits_{j > i} f(j)$for$0 \leq i < n$and$-1$for$i = n$. Similarly, let's define$p(i) = \min\limits_{j \leq i} f(j)$.Suppose that we're currently choosing a placement for index$i$. Now, there's 2 cases: either$f(i) > s(i)$, or$f(i) < s(i)$.In the first case, since there's no divider between$i$and$i + 1$, it must be true that$p(i) < s(i)$. Furthermore,$f(i) \neq p(i)$, since$f(i) > s(i)$and$p(i) < s(i)$. Therefore,$p(i - 1) = p(i) < s(i)$. The key observation here is that$p(i - 1)$must be equal to some$f(j)$for$a \leq j < i$(since either this segment was the first one, or there was a divider before this segment), and therefore must also be the value at the end of either$s_1$or$s_2$. Since$f(i) > p(i - 1)$, it must be added to whichever subsequence doesn't end with$p(i - 1)$.In the second case, it must be true that$s(i - 1) = s(i)$. Since there's no divider between$i - 1$and$i$, it must be true that$p(i - 1) < s(i - 1) = s(i)$. Once again,$p(i - 1)$must be at the end of either$s_1$or$s_2$. This time, we must add$f(i)$to whichever subsequence has$p(i - 1)$at the end of it, since otherwise we would have both subsequences ending in something less than$s(i)$, which is impossible.What's left is determining in which subsequence$f(b)$should go (if$b = a$, then we're done). Suppose that$f(b) < s(b)$. Then$s(b - 1) = s(b)$. Since there's no divider between$b - 1$and$b$,$p(b - 1) < s(b - 1) = s(b)$. However, this is a contradiction, since this implies$p(b) \leq p(b - 1) < s(b)$, which shouldn't be the case if either there is a divider between$b$and$b + 1$, or$b = n$. Therefore,$f(b) > s(b)$. It follows that$p(b - 1) < s(b - 1) = f(b)$. Once again, since$p(b - 1)$is at the end of either$s_1$or$s_2$,$f(b)$must be placed at the end of the other subsequence.In all cases, the choice of adding to the end of either$s_1$or$s_2$is deterministic. Note that if we began by adding$f(a)$to the end of$s_2$instead of$s_1$, all decisions would have been swapped due to symmetry, hence the only choice we have to make is which subsequence is which.lmk if I made any mistakes, I'm too tired to proofread :D  » 4 months ago, # | +9 How to solve D1D with 2-sat?  » 4 months ago, # | ← Rev. 2 → 0 In 1504E's solution2How do I know that if I solve that solution, I won't visit where I visited again?I am so curious.  » 4 months ago, # | 0 Can anyone help me why my O(n) solutions: 112036570 and 111956392 both give TLE? •  » » 4 months ago, # ^ | 0 You are creating array 'arr' many many times •  » » » 4 months ago, # ^ | 0 I moved the declaration above my while loop here: 112037826 and it still gives me TLE. •  » » » » 4 months ago, # ^ | 0 I'm not sure but seems that scanf(" %s", &arr); is O(n) not O(the size of the string) so try to use string arr instead of char arr[300001]; •  » » » » » 4 months ago, # ^ | 0 You can only create char arrays in C for strings. •  » » » » » » 4 months ago, # ^ | 0 Use C++ •  » » » » » » » 4 months ago, # ^ | 0 That doesn't solve my question and I've seen passed attempts in C that use scanf. •  » » » » » » » » 4 months ago, # ^ | 0 Ok I'm really sorry I don't know C •  » » » » 4 months ago, # ^ | 0 112208235I changed scanf(" %s", &arr) to scanf("%s", &arr) and got AC. I have also ever faced similiar bug, but I don't understand the cause as well. Maybe somebody else might be able to explain.  » 4 months ago, # | ← Rev. 4 → +3 My approach for Problem div2C: Let us consider balance of a string as the difference of opening and closing brackets. So in order for the string to be perfectly balanced, the balance of the string should never be < 0 in any iteration and should be 0 at the end of all iteration.bal1=balance of 1st string bal2=balance of 2nd stringthe main approach here is that we want our balance to be as close to 0 as possible.Notice that '1' always increases or decreases the balance of both string by 1 and '0' decreases the balance of one string and increases the balance of the other one.Therefore we would greedily increase or decrease the balance of both the string so that their balance remains closer to 0.There is also an edge case where bal1=1 and bal2=1 and the current position in string has '1' in it. in this case we have to check the next character of the string.Why we have to check the edge case?As because greedy solution will decrease both the balance by 1 and if the next character is '0' then balance of one of the string would become negative.My solution:112041165  » 4 months ago, # | ← Rev. 2 → +5 In Div1 D : "We can independently choose how to decompose each segment into two subsequences" Can anyone tell me how to decompose a single segment ? •  » » 4 months ago, # ^ | 0 Anyone ? •  » » 4 months ago, # ^ | 0 •  » » 4 months ago, # ^ | +3 You can decompose a single segment using the greedy algorithm mentioned here.https://codeforces.cc/blog/entry/89319?#comment-777475This gives you two sequences, and you just have to choose which one to call the first subsequence. Choose the one that requires the fewest flips. •  » » » 4 months ago, # ^ | 0 Thank you! I got it  » 4 months ago, # | +16 Div1C/Div2E can also be solved using disjoint set union (similar to Kruskal's algorithm). My code  » 4 months ago, # | 0 Can someone explain the intuition behind solution 1 of Div1 C? I don't know how to come up with that implicit graph. •  » » 4 months ago, # ^ | +1 The intuition is that we've reduced the problem to shortest path in a graph with$O(n^2)$edges. We just have to think which edges are redundant (because the other edges create a better or equal cost between the same pair). If you remove enough redundant edges, you find that you only need$O(n)$edges.  » 4 months ago, # | ← Rev. 2 → 0 Can anyone help me in finding the mistake in Problem D Div 2? I am doing as per the editorial only. It is failing on Test Case 6. 111982213  » 4 months ago, # | ← Rev. 3 → 0 In problem DIV2 F (flip the cards) , could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of$i$is greater than maximum of right to$i$. I didn't get why we are doing this.What i understood is that it's necessary we need to split [f(1),f(2),f(3),...,f(n)] into 2 decreasing subsequences (where one can also be empty). If we minimize length of one of the subsequence then number of flips would be minimized . But how we splitting is helping us here ? •  » » 4 months ago, # ^ | ← Rev. 2 → +3 1-gon could you please help here why we are splitting when minimum to left of$i$is greater than maximum of right to$i$. I understand that finding$2$decreasing subsequence directly might not give optimal solution . So how we justify that splitting it like that will help us find the optimal solution ?According to the editorial two subsequences will be unique if we split in that way. How to prove it ? •  » » » 4 months ago, # ^ | ← Rev. 2 → +12 could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of i is greater than maximum of right to i. Suppose there is a place where the prefix min is greater than the suffix max. Then if we split here and decompose the two halves independently, they can be combined in any way, and it will still be a valid decomposition into decreasing subsequences. The fact that we can make independent choices is intuitively good, because we can now focus only on optimizing each individual choice. According to the editorial two subsequences will be unique if we split in that way. How to prove it ? We need to show that an array with no position such that prefix min > suffix max has a unique decomposition into two decreasing subsequences (up to naming the two subsequences). Consider the maximum element in the array, let's say it is in subsequence$1$. It cannot be the first position since it would violate the condition, so everything before it must be in subsequence$2$.Now we have the unique decomposition of the prefix. Now consider the maximum element of the remaining elements. We cannot place it in subsequence$2$, or it would violate our assumption. So we are forced to place it in subsequence$1$, and all unassigned elements before it must be in subsequence$2$. Keep repeating this process until all elements are assigned to subsequences. Every decision we made was forced except for naming one of the subsequences$1$and the other$2$, so it is the unique decomposition.  » 4 months ago, # | 0 import java.util.*; public class codeforces { public static void main(String[] args) { Scanner s=new Scanner(System.in); int t=s.nextInt(); for(int tt=0;tt  » 4 months ago, # | 0 i write my solution in python, its a O(n) solution can someone tell me why i am getting this tle? https://codeforces.cc/contest/1504/submission/112123685 •  » » 4 months ago, # ^ | ← Rev. 2 → 0 Rule nth: Always submit string involved code in Python 3 not PyPy 3.  » 4 months ago, # | 0 In Div1 problem F,how can I get the solution after doing operations? And how can I find the leftmost point? I found judge points by ai>0,bi>0 will get wrong. thanks :) •  » » 4 months ago, # ^ | ← Rev. 2 → +10 You should find a point with$a_i>0$,$b_i > 0$, has an incoming$1$edge, and has an outgoing$1$edge. With these conditions, the choice doesn't matter.By doing operations, we represent the curve implicitly by a linked list of the points (besides the leftmost one) as they appear horizontally. Each point keeps the card ID, so in the end the solution is given precisely by the order of elements in the linked list. •  » » » 4 months ago, # ^ | 0 And how can I do operator 3?Should I keep the head,tail of the linked list,and the places of incoming edge and outgoing edge?I think it is a little troublesomely to merge two linked list,or maybe I lose some properties :( •  » » » » 4 months ago, # ^ | ← Rev. 2 → 0 You can look at 111940018 for the list solution. (It's also solvable using treaps, relevant submission: 111939934, and both solutions use a similar interface for the curve structure). •  » » » » 4 months ago, # ^ | 0 What a crazy problem with so many details...  » 4 months ago, # | 0 can someone give me the input string that failed my solution code?My Solution •  » » 4 months ago, # ^ | +3 abaa •  » » 4 months ago, # ^ | ← Rev. 2 → 0 Try 1 abaa Edit: Alwyn was faster :D  » 4 months ago, # | ← Rev. 2 → 0 Statement in tutorial of Problem 1504F: "Also, there is a unique way to decompose each segment: the only choice is in which one we call the first subsequence". Why it is unique? Could someone give me a detailed explanation, thanks~  » 4 months ago, # | 0 Please correct me if I'm incorrect on anything, but on the 41st token of the 2nd test case of problem 1504B, the following is inputted: 3 001 010The expected output is "NO", but I'm confused to why it's not "YES". Shouldn't you be able to take the last 2 bits of binary array "A" and invert them so that the resulting array is "010", as the number of zero's and one's is equal in the original prefix, thus making binary array "A" equal to binary array "B". •  » » 2 months ago, # ^ | ← Rev. 2 → 0 read the question carefully ..question says you just take a prefix .... 001 you can not take the string 01 because it is not prefix you can not take any any prefix here because any predix string does not have equal 0 and equal 1.. coolclicker2021  » 4 months ago, # | +22 Alternative (messier?) solution for 1503D - Flip the Cards Actually it turns out to be very similar to the solution in the editorial, but maybe the "path" to this solution is more intuitive. Consider each card as a segment$[\min(a_i, b_i), \max(a_i, b_i)]$. Let's say that a segment has color$0$if$a_i < b_i$,$1$otherwise. If two segments don't intersect, there is no solution. Two segments such that the biggest one contains entirely the smallest one can be colored in any way. In any other case, the two segments should have different colors. Let's find a coloring of an interval of length$n$. Our goal is to construct a graph such that two segments connected by an edge have different colors. If there is a solution, the graph is bipartite: for every connected component, there are two possible colorings, and we have to choose the one that minimizes the number of flips. There are two cases: There is a segment$[1, n]$. It can be discarded (since it makes a connected component of size$1$), and the problem can be solved recursively in the interval$[2, n-1]$. There are two segments$[1, x]$and$[y, n]$(let's define them "special" segments). The other segments should be contained in at least one of the special segments (otherwise the graph is not bipartite, since it contains a cycle of length$3$). There are three types of segments: inside$[y, x]$, inside$[1, x]$but not$[y, x]$, inside$[y, n]$but not$[y, x]$. If two segments of type$2$are connected by an edge, they also form a cycle of length$3$with$[y, n]$. Hence, all the pairs of segments of type$2$(and$3$) are such that the biggest one contains entirely the smallest one. Hence, the special segments and the segments of type$2$and$3$make a connected component, and any of them isn't connected to a segment of type$1$. Then, the problem can be solved recursively in the interval$[y, x]$. How to find all the connected components in$O(n)$? For each component, we can find the segments of type$2$and$3$in$O(\text{# of such segments})$. Let$[l_1, r_1]$,$[l_2, r_2]$be the special segments. While there exists a segment$[l, r]$with$l < l_2$and$r < r_1$, replace$[l_1, r_1]$with such$[l, r]$with minimum$l$. Do the same for$[l_2, r_2]$, then again for$[l_1, r_1]$, etc., until no more segments can be found. 112259448 •  » » 4 months ago, # ^ | +16 nice solution i have some ideas of another graph model of the problem but ive didnt finished it maybe you can help me with it! my idea : if we consider 2n graph nodes which the node 2i is the i-th card normally and the 2i — 1 is the reverse of the i-th card and if we put a directed edge between node v, u(v -> u) it means that the representing card of u has bigger elements on both representing sides(like card v = {1, 5}, card u = {3, 6}) in this graph we dont have directed Cx(cycle with lengh x > 2) and we dont have even directed P3(v -> u -> z) if we have, the answer is -1 because in the answer there will be two of them in same side. so the graph is some directed stars but ive couldnt do any decomposition to get the answer do you have any idea? •  » » » 4 months ago, # ^ | ← Rev. 2 → +16 Directed edges don't seem to work (if I understand, they make a dag so they can't make cycles). If the edges are undirected, you can have cycles of even length and an answer$\neq -1$(for example,$(1, 6) \leftrightarrow (3, 8) \leftrightarrow (2, 5) \leftrightarrow (4, 7) \leftrightarrow (1, 6)$). In your graph, there are edges between each pair of cards that in my solution is$(\text{card of type 2}, \text{card of type 3})$in the same connected component. For example, in$(1, 6)$,$(2, 5)$,$(3, 8)$,$(4, 7)$, there is only one connected component, with cards of type$2$:$(1, 6)$,$(2, 5)$cards of type$3$:$(3, 8)$,$(4, 7)$edges:$(1, 6) \leftrightarrow (3, 8)$,$(1, 6) \leftrightarrow (4, 7)$,$(2, 5) \leftrightarrow (3, 8)$,$(2, 5) \leftrightarrow (4, 7)$•  » » » » 4 months ago, # ^ | +8 well the directed graph has the star property because in your example the graph is kinda like this -> a -> c, b -> c, a -> d, b -> d. idk just and idea : )) •  » » » » » 4 months ago, # ^ | +8 Yes, every connected component is a complete bipartite graph. But there may be more than$1$connected component, for example in$(1, 7)$,$(2, 8)$,$(3, 5)$,$(4, 6)\$.
 » 3 months ago, # |   +10 [user:Mihir2422]hi
 » 3 months ago, # | ← Rev. 2 →   0 good A problem
 » 3 months ago, # |   0 For problem 2-Coloring, when you mention a monotonically increasing path from (1,0) to (rA,c) What exactly does it mean? For example, for the (x, y) mentioned, are the Ox and Oy the normal mathematical Ox (left to right) and Oy (down to top)? Or are they row (top to bottom) and column (left to right) axes?Can you give a clearer example?
•  » » 2 months ago, # ^ |   +28 Coordinates are (row, column). Here is a picture of the described situation.
 » 11 days ago, # |   0 Extremely elegant and fast solution for F: 123227611