### Блог пользователя 1-gon

Автор 1-gon, история, 2 недели назад,

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

Разбор задач Codeforces Round #712 (Div. 1)
Разбор задач Codeforces Round #712 (Div. 2)

• +532

 » 2 недели назад, # |   +15 omg hi!
•  » » 2 недели назад, # ^ | ← Rev. 2 →   -34 hello :)
•  » » 2 недели назад, # ^ |   +21 Hey
•  » » » 2 недели назад, # ^ |   +5 Hey
•  » » » » 2 недели назад, # ^ |   0 Hello!!!
•  » » » » » 10 дней назад, # ^ |   0 Recursion
•  » » » » » » 8 дней назад, # ^ |   0 Hi
 » 2 недели назад, # | ← Rev. 2 →   -47 Nah, I am stupid. Have no idea but wait editorial here :<
 » 2 недели назад, # | ← Rev. 2 →   0 bricked, (nvm this was a great round, i gained +35 rating despite literally getting 0 questions)
 » 2 недели назад, # |   -40 imagine figuring that C out
•  » » 2 недели назад, # ^ |   -27 Now just imagine!!
 » 2 недели назад, # |   -13 Is there a proof to solution of C?
•  » » 2 недели назад, # ^ |   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.
•  » » » 2 недели назад, # ^ |   +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?
•  » » » » 6 дней назад, # ^ |   0 I must say most times editorials are written in hurry. No offence but it's what I think.
•  » » 2 недели назад, # ^ |   +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.
•  » » » 2 недели назад, # ^ | ← 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!
•  » » » 2 недели назад, # ^ |   +1 Nice visualization. Helpful. Thanks!
 » 2 недели назад, # |   -39 Lightning fast editorial. Amazing
 » 2 недели назад, # | ← Rev. 2 →   +184 Me : *trying to push monogon contribution to moon Monogon : *making greedy problems that shove my rating into dirt*sad cat noises
 » 2 недели назад, # |   -26 Thanks for fast editorial.
 » 2 недели назад, # |   -30 E is a good problem! I'm so close :(
 » 2 недели назад, # |   0 well, this was fun
 » 2 недели назад, # |   +65 Constructiveforces.
 » 2 недели назад, # |   0 Sry，I went to the wrong place ，I come back to div3 immediately TAT
•  » » 2 недели назад, # ^ |   +3 You are not alone...
 » 2 недели назад, # |   -19 Thanks for the editorial which proved my stupidity.
 » 2 недели назад, # |   -13 Wow!! Fast editorials really helps. Thanks.
 » 2 недели назад, # |   0 In E's solution 1 why only need to add i-> j+1? (i.e. don't need i->j+2....)
•  » » 2 недели назад, # ^ | ← 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.
•  » » 2 недели назад, # ^ |   +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$.
•  » » » 10 дней назад, # ^ |   0 if ci is big and ci+1 is small then the expr is not true,right?
•  » » » 10 дней назад, # ^ |   0 Maybe https://codeforces.ml/blog/entry/89319?#comment-777539 is what you want I guess.
 » 2 недели назад, # |   -13 omg hi cyan
 » 2 недели назад, # |   -6 Can anyone proof solution of problem Div.2 D?
 » 2 недели назад, # |   -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
 » 2 недели назад, # |   -17
 » 2 недели назад, # |   -18
 » 2 недели назад, # |   -27 Pretest for div2B was very weak. Don't know why my O(n) solution exceeded the time limit 111887915
•  » » 2 недели назад, # ^ |   0 Your code is O(n^2) in the worst case since you are doing string z = b + z
•  » » » 2 недели назад, # ^ |   0 Thanks got it!
•  » » 2 недели назад, # ^ |   +89 You should probably look up what weak pretest means before commenting.
•  » » » 2 недели назад, # ^ | ← 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.
 » 2 недели назад, # |   0 Great problem set!!! 1-gon orz
 » 2 недели назад, # |   0 Glad that Div2C, D, and E all passed in python3 even without pypy3!
 » 2 недели назад, # |   0 StringForces
 » 2 недели назад, # |   0 one of the greatest contest i have ever partipicated in . thanks to the author. Waiting soon for ur next contest
 » 2 недели назад, # |   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
 » 2 недели назад, # |   +6 Sorry I am stupid but can you elaborate div1C solution 2's formula
•  » » 2 недели назад, # ^ |   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.
•  » » » 2 недели назад, # ^ |   +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.
•  » » 2 недели назад, # ^ |   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
•  » » 2 недели назад, # ^ |   +29 I didn't understand either. I think the wording is kind of confusing.
•  » » » 2 недели назад, # ^ |   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.
•  » » » 2 недели назад, # ^ | ← 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.
•  » » » » 13 дней назад, # ^ |   +8 Lemma 1 is important. Thanks for the explanation.
•  » » » 13 дней назад, # ^ | ← 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 •  » » » 13 дней назад, # ^ | +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. •  » » 13 дней назад, # ^ | ← 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. •  » » 11 дней назад, # ^ | ← 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. •  » » » 11 дней назад, # ^ | +3 You can see my comment for the proof. I agree that my explanation makes the solution not intuitive.  » 2 недели назад, # | 0 B was so hard for me:( i'm solve it after 1 hour. •  » » 2 недели назад, # ^ | 0 I spent like an hour trying to figure out what's wrong, to find one missing equal sign :? •  » » 2 недели назад, # ^ | +9 How many hours do you code per day bro? Your graph is scary  » 2 недели назад, # | -68 shit contest  » 2 недели назад, # | +2 Those who solved div2C,how do you guys think of that solution? •  » » 2 недели назад, # ^ | 0 I have the same question :) •  » » 2 недели назад, # ^ | +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. •  » » 2 недели назад, # ^ | +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)  » 2 недели назад, # | 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? •  » » 2 недели назад, # ^ | +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... •  » » » 2 недели назад, # ^ | 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!  » 2 недели назад, # | 0 is there a proof for Div2C? •  » » 13 дней назад, # ^ | ← 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.  » 2 недели назад, # | ← 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! •  » » 2 недели назад, # ^ | 0 The very first pretest was n = 2 though... •  » » » 2 недели назад, # ^ | -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  » 2 недели назад, # | +1 I was just an '=' away from getting AC on B. Oh Man! This is such a drag.  » 2 недели назад, # | 0 C problem actually requires backtracking to alternate 0 positions with open and close brackets.  » 2 недели назад, # | +1 I don't understand why my n^4 solution passed in Div 2 D, here is link https://codeforces.com/contest/1504/submission/111924524 •  » » 2 недели назад, # ^ | +6$n$is only$100$and constant factor is pretty low and time limit is$3$secs.  » 2 недели назад, # | -6 IMO only the ones that solved C will understand its editorial.  » 2 недели назад, # | 0 (A + B) VIDEO EDITORIAL : https://www.youtube.com/watch?v=2DBLj6IOJJc  » 2 недели назад, # | 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 •  » » 2 недели назад, # ^ | +3 Proof? •  » » 2 недели назад, # ^ | +9 This is literally the second solution in the editorial. •  » » » 2 недели назад, # ^ | 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. •  » » » » 2 недели назад, # ^ | +2 I couldn't understand either. Can you elaborate your solution? •  » » » » » 13 дней назад, # ^ | 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.  » 2 недели назад, # | +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. •  » » 13 дней назад, # ^ | 0  » 2 недели назад, # | 0 Can anyone help with the TLE error for div2B My solution •  » » 2 недели назад, # ^ | 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. •  » » » 2 недели назад, # ^ | 0 Thanks it worked :)  » 2 недели назад, # | 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 ? •  » » 2 недели назад, # ^ | +86 OK •  » » » 2 недели назад, # ^ | +4 Thanks very useful response . •  » » » » 2 недели назад, # ^ | +86 YES •  » » 2 недели назад, # ^ | +9 The problem given wasn't actually traveling salesman. It was a variation which could be solved much faster when you make some observations.  » 2 недели назад, # | 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 ? •  » » 2 недели назад, # ^ | 0 1 8 10011001  •  » » » 2 недели назад, # ^ | 0 very thanks for help, that was what I needed . How can one find it? •  » » » » 2 недели назад, # ^ | 0 I generated random string with length 8 and compare your solution verdict and mine (AC solution) verdict •  » » » » » 2 недели назад, # ^ | 0 Great. Thankyou for help again sevlll.  » 2 недели назад, # | +10 omg hi !  » 2 недели назад, # | 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  » 2 недели назад, # | 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? •  » » 13 дней назад, # ^ | 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.  » 2 недели назад, # | 0 To decompose an array into two decreasing subsequences, there is a standard greedy approach.Can you share it please? •  » » 2 недели назад, # ^ | ← 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. •  » » » 2 недели назад, # ^ | 0 Can you please explain what's Wrong with my Code in D: 111943902 •  » » » » 2 недели назад, # ^ | 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. •  » » » » » 2 недели назад, # ^ | 0 tnx got It :)  » 2 недели назад, # | +6 Greedyforces •  » » 2 недели назад, # ^ | 0 So many greedy problems! (I love greedy!)  » 2 недели назад, # | 0 How to solve 2F/1C for dp •  » » 2 недели назад, # ^ | 0 maybe it's impossible  » 2 недели назад, # | ← 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 •  » » 2 недели назад, # ^ | ← 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. •  » » » 13 дней назад, # ^ | 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. •  » » » » 13 дней назад, # ^ | 0 Thanks man for pointing it out! Appreciate it! •  » » » » 12 дней назад, # ^ | 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  » 2 недели назад, # | 0 YESorNOforces  » 2 недели назад, # | ← Rev. 2 → +3 Although I always lose rating in your contests, I really like your problems :)  » 2 недели назад, # | 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 . •  » » 2 недели назад, # ^ | +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. •  » » » 2 недели назад, # ^ | 0 Thanks a lot nipungoel11 , i got my mistake .  » 2 недели назад, # | 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 ? •  » » 2 недели назад, # ^ | ← 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. •  » » » 13 дней назад, # ^ | 0 Thanks for reminding! I misunderstood the usage of insert  » 2 недели назад, # | ← Rev. 3 → 0 https://codeforces.com/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? •  » » 2 недели назад, # ^ | 0 That isn't the only difference between your codes. You also changed i  » 2 недели назад, # | ← 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....  » 13 дней назад, # | -17 1-gon, COCU XYU  » 13 дней назад, # | 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) •  » » 13 дней назад, # ^ | +7 On the test case141011You don't output anything. •  » » » 13 дней назад, # ^ | 0 dorijanlendvaj, real. Thank's a lot.  » 13 дней назад, # | ← 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.  » 13 дней назад, # | ← 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  » 13 дней назад, # | +3 Could someone please explain why in the last part of the tutorial of Div1D "there is a unique way to decompose each segment"? •  » » 13 дней назад, # ^ | +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  » 13 дней назад, # | +9 How to solve D1D with 2-sat?  » 13 дней назад, # | ← 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.  » 13 дней назад, # | 0 Can anyone help me why my O(n) solutions: 112036570 and 111956392 both give TLE? •  » » 13 дней назад, # ^ | 0 You are creating array 'arr' many many times •  » » » 13 дней назад, # ^ | 0 I moved the declaration above my while loop here: 112037826 and it still gives me TLE. •  » » » » 13 дней назад, # ^ | 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]; •  » » » » » 12 дней назад, # ^ | 0 You can only create char arrays in C for strings. •  » » » » » » 12 дней назад, # ^ | 0 Use C++ •  » » » » » » » 12 дней назад, # ^ | 0 That doesn't solve my question and I've seen passed attempts in C that use scanf. •  » » » » » » » » 12 дней назад, # ^ | 0 Ok I'm really sorry I don't know C •  » » » » 10 дней назад, # ^ | 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.  » 13 дней назад, # | ← 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  » 12 дней назад, # | ← 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 ? •  » » 12 дней назад, # ^ | 0 Anyone ? •  » » 12 дней назад, # ^ | 0 •  » » 12 дней назад, # ^ | +3 You can decompose a single segment using the greedy algorithm mentioned here.https://codeforces.com/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. •  » » » 11 дней назад, # ^ | 0 Thank you! I got it  » 12 дней назад, # | +16 Div1C/Div2E can also be solved using disjoint set union (similar to Kruskal's algorithm). My code  » 12 дней назад, # | 0 Can someone explain the intuition behind solution 1 of Div1 C? I don't know how to come up with that implicit graph. •  » » 12 дней назад, # ^ | +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.  » 12 дней назад, # | ← 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  » 12 дней назад, # | ← 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 ? •  » » 11 дней назад, # ^ | ← 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 ? •  » » » 11 дней назад, # ^ | ← 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.  » 12 дней назад, # | 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  » 12 дней назад, # | 0 i write my solution in python, its a O(n) solution can someone tell me why i am getting this tle? https://codeforces.com/contest/1504/submission/112123685 •  » » 12 дней назад, # ^ | ← Rev. 2 → 0 Rule nth: Always submit string involved code in Python 3 not PyPy 3.  » 11 дней назад, # | 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 :) •  » » 11 дней назад, # ^ | ← 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. •  » » » 10 дней назад, # ^ | 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 :( •  » » » » 10 дней назад, # ^ | ← 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). •  » » » » 10 дней назад, # ^ | 0 What a crazy problem with so many details...  » 11 дней назад, # | 0 can someone give me the input string that failed my solution code?My Solution •  » » 10 дней назад, # ^ | +3 abaa •  » » 10 дней назад, # ^ | ← Rev. 2 → 0 Try 1 abaa Edit: Alwyn was faster :D  » 10 дней назад, # | ← 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~  » 10 дней назад, # | 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".  » 10 дней назад, # | +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 •  » » 10 дней назад, # ^ | +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? •  » » » 9 дней назад, # ^ | ← 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)$•  » » » » 9 дней назад, # ^ | +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 : )) •  » » » » » 9 дней назад, # ^ | +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)\$.