### jdurie's blog

By jdurie, 3 weeks ago,

1966A - Card Exchange

Solution
Code

1966B - Rectangle Filling

Solution
Code

1965A - Everything Nim

Solution
Code

1965B - Missing Subsequence Sum

Solution
Code

1965C - Folding Strip

Solution
Code

1965D - Missing Subarray Sum

Solution
Code

1965E - Connected Cubes

Solution
Code

1965F - Conference

Solution
Code
• +246

 » 3 weeks ago, # |   0 Super Fast Tutorial
 » 3 weeks ago, # |   -8 Ultralightning fast editorial !!!
 » 3 weeks ago, # |   +1 Auto comment: topic has been updated by jdurie (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 bros made tutorial even before the contest
 » 3 weeks ago, # |   0 Nice Super-fast Tutorial
 » 3 weeks ago, # |   +11 Round #877 editorial?!
•  » » 3 weeks ago, # ^ |   +11 oops, fixed it
 » 3 weeks ago, # |   0 Thank for so fast tutorial!
 » 3 weeks ago, # |   +9 Good round. I enjoyed the problems.
•  » » 3 weeks ago, # ^ |   0 why is he getting downvoted I do not understand how this works bunch of crazy people
 » 3 weeks ago, # |   -32 Very bad problem D!!!
•  » » 3 weeks ago, # ^ |   0 This problem is constructed without providing any information. Most of the time, unless we find out that the lack of information doesn't affect something.But the Problem D in last contest which is Div.1 has difficulty of 2800,why are you angry about not doing it.
•  » » » 3 weeks ago, # ^ |   0 A difficulty of 2800 , are you sure? I managed to solve it.
•  » » » » 3 weeks ago, # ^ |   0 "Div.1" D
•  » » » » » 3 weeks ago, # ^ |   0 Just shows my great reading skills:)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +7 Imo div2 D was actually pretty good. It was construction which is pretty meh but you could solve it by writing things down instead of just guessing so it wasn't so bad.
•  » » » 3 weeks ago, # ^ |   0 The unsaid rule on codeforces is — Able to solve the problem — Wonderful problem,Wonderful contest,Wonderful authors, Thanks the authors in the comments section. Not able to solve the problem — Crap problem,crap contest,crap authors, comments mathforces adhocforces xyzforces in the comments section.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   -16 you got me haha, I would've hated D if I hadn't solved iton an unrelated note, E was terrible and ad hoc
 » 3 weeks ago, # | ← Rev. 2 →   -27 Was my first comment and ppl demoted me
 » 3 weeks ago, # |   0 Can someone who solved Div2-C DP explain his approach please
•  » » 3 weeks ago, # ^ |   0 hey no offense but why do it with DP when there is a pretty simple solution, it involves just counting the number of leading 1's in differences between consecutive elements of array sorted in ascending order.
•  » » 3 weeks ago, # ^ |   0 I didnt use the editorial approach but the idea is similar: sort the array for better understanding [Assumption 1] we solve it more list if there are piles with rocks > 1 you will win irrespective of the number of piles --> if there is one pile you pick up all rocks else you pick up n-1 forcing next person to pick 1 -- as that is the min acc. to the question. obvious question --> how do I track the number of rocks per move when rocks are being removed from all piles??? --> you can sore the piles as delta difference for each pile and ignore repeating numbers --> now you can simply deduce which valid moves can be made. after this calculation now you have a delta vector and a base condition that if there is just one pile Alice wins. now treat this as a dp problem so while delta[i]>1 Alice wins --> first assumption if delta[i] == 1 winner 'Bob' now simply maintain who was wining at position n+1 while moving back and toggle it whenever you find 1; The editorial does this much simply by just checking if there is an increasing sequence but I couldnt really get to such a simple solution in the contest.
•  » » 3 weeks ago, # ^ |   0 This is my solution from the contest using recursion with memoization.First I sort the array and remove duplicates for convenience. In the array dp I remember whether or not the player wins if it's his turn on a certain index. If there is a move that the current player can make such that the opposing player is in a losing position on the next index, then he is in a winning position on the current index. The current player is also in a winning position if he can make it so he is in a winning position on the next index.It is possible to do both moves if the difference between the current pile and the previous one is greater than 1, so we take both into account. This works because you can leave 1 rock in the current pile and then it is your turn on the next index, or you can take all the rocks and then it is the opponent's turn on the next index. If the difference between the current pile and the previous one is equal to 1 then is impossible to have the next move on the next index, so it is only the opponents.Look at the code as well, I think it is quite clean.
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 Div2-C dp solution Initially sort the numbers and remove the duplicates and then take difference with respect to previous element. Now start iterating from backward. We can say that when the the diff is not equal to 1 the first player always wins. but when it is equal to the 1 the player who wins i+1 will lose so dp state is dp[i]=1^dp[i+1] when 1 is diff value at an index, dp[i]=1 when the diff is equal to any value other than 1
 » 3 weeks ago, # |   0 Awesome
 » 3 weeks ago, # |   +40 Can we just talk about how disgustingly simple the code for D2E — Folding Strip looks??
 » 3 weeks ago, # |   +45 Why are bounds so tight in D1E? My solution only uses 348800, do you think it is a good practice to set bound to 350000 and also make your solution fail?
•  » » 3 weeks ago, # ^ |   +10
•  » » » 3 weeks ago, # ^ |   +22 max = 281150 sol : 258515976
 » 3 weeks ago, # |   +56 conqueror_of_tourist could you share how you managed to solve C in just 4 minutes? Did you see the problem before? It's hard to believe it could be that easy
•  » » 3 weeks ago, # ^ |   +202 If you view the problem as: "construct the smallest possible final strip such that you can create a 'walk' on the strip that corresponds to the original string", then you can see that any repeated 00 or 11 is 'suboptimal'. From there there's only one possible string you can create and you can simulate it.Of course, formally proving that the final string cannot contain any 00s or 11s is harder (and I eventually did it using the same solution as the editorial) however for my original submission I just used 'proof by AC' after it passed the samples.
•  » » » 3 weeks ago, # ^ |   +8 I see, that's really impressive! Thanks for the explanation :)
 » 3 weeks ago, # |   +3 Awesome contest, almost got Div2 D, will get it next time! Thanks for the super fast tutorial.
 » 3 weeks ago, # |   0 Great problem 1E! However, I am still unclear about the optimality proof for problem 1C. Is there a more intuitive or formal explanation for "composing" the valid foldings?
•  » » 3 weeks ago, # ^ |   +8 I thought, if you have three consecutive characters you can "merge" them into 1 by doing the zig-zag fold. By doing this repeatedly you end up with a string with maximally 2 consecutive characters. Also it's never bad to do this because if there was an optimal folding which contained an overlap between more than 2 consecutive characters, both sides of the fold could be merged, resulting in a better solution. When the max number of consecutive characters is 2, I felt like it was pretty intuitive that you should always fold between the consecutive pairs because it always works and you do maximum folding.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +8 Oh, I have a simple idea: If a string t has consecutive same characters, it's always possible to apply the greedy folding algorithm again and obtain a strictly shorter string. Another folding is intuitively always possible, I think this is what "compose" means.
 » 3 weeks ago, # |   0 Is there a category for the game problems "Alice" & "Bob" play optimally?How do I improve on these problems?
•  » » 3 weeks ago, # ^ |   -15 Nim games (Game theory) — gfg link
•  » » » 3 weeks ago, # ^ |   +5 That problem litterally had nothing to do with nim.
•  » » » » 3 weeks ago, # ^ |   +1 It would probably give him insight and confidence for these problems, when I read "nim" in an easy problem, I feel confident lol! I read about it through it's Wikipedia article and got some idea about strategy games. Also the idea of transitioning positions at will comes up in a lot of problems.
•  » » » » » 3 weeks ago, # ^ |   +3 true.
•  » » » » 3 weeks ago, # ^ |   +3 I solved the problem pretty naively applying grundy nums 258426128.
•  » » 3 weeks ago, # ^ |   +4 You should try to find out when someone has control over the rest of the game the one who does wins the rest doesnt matter thats how i solved C
•  » » 3 weeks ago, # ^ |   +1 The CF problems usually don't require any knowledge other than basic math and number theory, these are called game theory problems, when you're trying to play optimally as bad ur opponent plays is called Maximin strategy, the kind of game where the participants remove objects, etc is called nim games, which for CP, in general, there is no need other than just simple logic + math.
•  » » 3 weeks ago, # ^ |   +1 Learn the “plus-minus” principle (retroanalysis of the game).
•  » » 3 weeks ago, # ^ |   0 How to force player to play the only possible bad move
•  » » » 3 weeks ago, # ^ |   0 If number of piles remaining is 1 pick all which means you won else pick exactly min-1 forcing the opponent just one option that is picking up 1. You will win as long as you are not forced to pick just one stone which leads to the increasing sequence logic. Hope this helps!
•  » » » » 3 weeks ago, # ^ |   +8 It wasn't a question lol :)
 » 3 weeks ago, # |   -27 if I'm not mistaken, problem B can be solved in O(n+m) 258432155 the solution is quite long, but still
•  » » 3 weeks ago, # ^ |   +11 Taking input is O(nm).
•  » » » 3 weeks ago, # ^ |   0 oh, yeah... sounds logicthank you
•  » » 3 weeks ago, # ^ |   0 or may be like this 258432643
 » 3 weeks ago, # | ← Rev. 2 →   +3 What should be the general thought process while approaching problems like Div2-D/ Div1-B? I was trying to come up with some constructions on paper but every time I got stuck on the same idea, nothing special was popping out. What should be done when stuck like this?
•  » » 3 weeks ago, # ^ |   0 To solve problems like Div2-D one must always try to see the problem using different perspectives especially when it is less intuitive. In other words, if one approach doesn't work then jump to other approaches. I tried to solve using greedy and dp but could not do it.
•  » » 3 weeks ago, # ^ |   +2 it says: you want have every possible sum, how? One way is to have n ones. but something else, there is always a way to represent a number as the sum of powers of 2, so you think of log and power 2-based solution, now the main point is how to tweak those powers of 2 such that, there won't be a possible sum but others will be possible, there is a trap I fell into in the contest time: To make it work, How to remove/add some other integers based on k to the {1, 2, 4, 8, 16, ...} sequence. which may be possible but requires a lot of case forking on the set bits in k.there is also another important observation, $k = k/2 + k/4 + \cdots$ Proof$A = k/2 + k/4 + k/8 + \cdots \newline 2*A = k + k/2 + k/4 + \cdots \newline 2A - A = k \newline => A = k$which with a little bit of tweaking with the math, you get that you can go from $(k-1)/2$ to $1$ and $k+1$ to $2*n$, using multiplying by 2. which will give you the solution, now there is left to prove that you can create anything, but k.which is the proof represented in the editorialI hope this was helpful to let you understand the intuition to how to get the solution. cheat codeAlways use pen and paper during the contest, even if u don't write anything, it'll help you adjust your mind
 » 3 weeks ago, # |   0 For Problem B, why are test cases 6 and 8 NO? For example, test case 8 "WBBWB", we can select 2nd cell B, all the way to last cell B and color all white to end with "WWWWW" or alternatively, select 1st cell W and 4th cell W and color all black.Similarly, test case 6, we could select either the upper black square or the lower white square and color it to match the other one. BB BB WW WW
•  » » 3 weeks ago, # ^ |   -6 Read the Question Once Again
•  » » 3 weeks ago, # ^ |   0
•  » » 3 weeks ago, # ^ |   0 The color you fill the rectangle with is the color that the cells you select are.
 » 3 weeks ago, # |   0 i'm pretty sure c is 1300 but i failed badly :(
 » 3 weeks ago, # |   0 For Div2 C, what should be the answer for testcase: [1, 3, 5]According to me it should be "Bob", if I'm wrong please explain.
•  » » 3 weeks ago, # ^ |   0 Yes, correct answer is Bob
 » 3 weeks ago, # | ← Rev. 4 →   0 it's a really fast tutorial, but why most codes in python?if you add c++ I will be thankful!
 » 3 weeks ago, # |   0 Could someone try to hack my solution for D?https://mirror.codeforces.com/contest/1966/submission/258465640
•  » » 3 weeks ago, # ^ |   0 I failed...it is so correct.
•  » » » 3 weeks ago, # ^ |   0 Yeah, after covering [1, 4x + 1] and using all the bits except $2^i$ it is actually correct.
 » 3 weeks ago, # |   0 man if the contest was 5 more minutes I'd solved D :)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -8 I also got the idea in the last few minutes, but luckily solved 2 minutes before contest ends
•  » » » 3 weeks ago, # ^ |   0 Man! orz
•  » » » 3 weeks ago, # ^ |   0 can you explain your code please
•  » » » » 3 weeks ago, # ^ | ← Rev. 5 →   0 Sorry, I don't know how to explain my code in an intuitive way.
•  » » » » » 3 weeks ago, # ^ |   +1 Consider n = 6, k = 1. k-1 = 0, so you won't add anything. Then add k+1, i.e. 2. Now, next powers of 2 that are greater than k but <=n is 4. So, in total you have {2,4}. You can't get a subsequence of sum 3 from this.
 » 3 weeks ago, # |   0 I honestly can't see why my solution is failing. Shouldn't it give the same answer as solution in the editorial? 258438670
•  » » 3 weeks ago, # ^ |   0 I got it, nevermind
 » 3 weeks ago, # |   +12 Very fast editorial. Thanks!
•  » » 3 weeks ago, # ^ |   +10 what a beautiful profile picture
 » 3 weeks ago, # |   0 "C" you the next time
 » 3 weeks ago, # |   0 Does problem 2D has any other more intuitive solution and can anybody explain it please
•  » » 3 weeks ago, # ^ |   +1 I took 2k, 4k, 8k... until 2^i*k is less than n, I also took 3k; also another k+1; then to be able to make all the numbers smaller than k:  k--; while(k!=0){ add((k+1)/2); k/=2; } So we have numbers from 1 to k-1, if we add k+1 we have all from k+2 to 2k2k,4k,8k.. helps us to get any M*k, if M is odd we can take 3k add this to (M-3)*kIf we use it, we can make all M*k+x, x<=k-1
•  » » » 3 weeks ago, # ^ |   0 thanks man
•  » » » 3 weeks ago, # ^ |   0 First time competitor here. Solved D2D post-round.I wasn't fully confident in the "descending from k" strat for the bottom part, went ascending from 1. Add powers of 2 starting from 1, stop when the next sum would be >= k, then add such a number to obtain a sum of k-1.The >k part I did exactly as you wrote (shouldn't it say 2^i*k greater than n?).
 » 3 weeks ago, # |   -38 Thanks for the tasks. But actually disappointed with С. I don't like such tasks
 » 3 weeks ago, # |   0 Another approach in 1B for obtaining subset sums in interval $[0;k)$. Let us say that by induction we can build a set of numbers such that its subset sums make an interval of $[0; \frac{k+1}{2})$. Now if we add $\frac{k}{2}$ to that set we can make an interval of $[0; k)$. So we just always add rounded down $\frac{k}{2}$ to the set and replace $k$ with rounded up $\frac{k}{2}$ until $k$ equals 1.
 » 3 weeks ago, # |   +26 minecraft is useable to create edtiorial picture of D1E.
 » 3 weeks ago, # |   0 div 2d is not very intuitive to me but it seems that a lot of people have used different approaches, can someone tell me their thought process , i dont care about the proof but how people came to the conclusion is what i want to know.
 » 3 weeks ago, # |   0 For Div2D proof If v>k, we can take k+1 along with the binary representation of v−k−1Can't understand how it is possible to take the binary representation of v-k-1?
•  » » 3 weeks ago, # ^ |   0 if v>k there are two cases for v-k-1 Case 1: v-k-1 does not have ith digit on,in that case we already have all the power of 2 from 0 to 19 except i so v-k-1 can be easily obtained by combining those numbers; Case 2: v-k-1 have ith digit on, in that case lets remove the ith digit by subtracting (1<
 » 3 weeks ago, # |   +6 I have a slightly different solution of 1965B - Missing Subsequence Sum.If you know subset sum using Bitset, then it is way easier to visualize. IdeaLet $bs$ be a Bitset of size $n + 1$. $bs[i]$ is true if we can get a sum of $i$ using some elements in $a$.Now, if we add another element $x$ in $a$, the bitset would change accordingly. bs |= bs << x; Since we choose the value of $x$, we can control which bits we want to be set. ApproachInitially, only $bs[0] = true$ and all other $bs[i] = false$.Eventually, we want only $bs[k] = false$, and all other $bs[i] = true$.At each step, we'll choose $x$ such that we can set as many unset bits as possible, without setting the k-th bit.For example: Let $n = 15$ and $k = 6$.$bs = 0000000000000001$ (The LSB $bs[0]$ is at the right) We only have one set bit, so one or-shift operation can set only one more bit. So choose $x = 1$.$bs = 0000000000000011$ Now we can use these two bits to set the second and the third bit. Choose $x = 2$$bs = 0000000000001111 Now, we cannot choose x = 4, because that will also set the k-th bit. Choose x = 2, that'll set all bits before the k-th bit.bs = 0000000000111111 Now, we'll avoid setting the k-th bit. Choose x = 7$$bs = 0001111110111111$ One more step should be enough. Choose $k = 13$$bs = 1111111110111111$For this example, it was enough. But if you notice, on adding $x (> k+1)$ in $a$, $0$ will be present at the $(x+k)-th$ bit.On further observation, you can see that the gap between the zeros is $2k + 1$ (if not handled). Why?Because we are repeating a pattern of $k$ 1s, 0, $k$ 1s. So there are $2k$ 1s between two 0s.So a final addition of $x = k + 1$ is enough to set all those unset bits.My Submission: 258434678I wonder if that's how the checker is also built.
•  » » 3 weeks ago, # ^ |   0 thats a damn cool solution bro
•  » » 2 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } could you explain the implementation ?
 » 3 weeks ago, # |   +8 Felt kinda frustrated after proof-by-ACing C, but not anymore after reading the intended solution. It’s an extremely clever problem, thanks for the contest!
 » 3 weeks ago, # |   0 Hi!I am not able to understand editorial for Problem: Everythin Nim. Can anyone explain me in simpler terms?Thanks in advance.
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 First observe that when the smallest pile contains 1 then the player is forced to choose 1. Thus it is a forcing move. Now remove all the duplicates in array and sort it in ascending order, as this does not affect the answer.Now consider the case when no consecutive numbers in the new array have a difference of 1 between them. You will see that when a person is forced to move (that is, the least pile is 1 in the person's chance), he/she will definitely lose.Now let's focus on the case when there are is some sequence of consecutive numbers starting from the least element.Case 1 -> they start from 1. For eg: 1 2 3 4 8 9 .... In this case Alice can convert this to 1 8 9 .... for Bob. Hence Alice wins. eg2: 1 2 3 8 9.... In this case Alice will only be able to convert this to 1 8 9... for herself. Hence she loses. Case 2 -> they do not start from 1. For eg: 2 3 4 5 8.. In this case Alice always wins because she can convert this situation to 1 2 3 6... for bob and the situation 2 3 4 8 to 1 2 3 7 for Bob. Hence we have covered all the cases. You can see my code for more clarity. You will have to try these examples yourself and convince yourself.
 » 3 weeks ago, # |   0 I’m not one to judge a contest or problems. On average, they were good, but Div2D/Div1B was a bit lucky if you wrote things down or used brute force. It felt like guessing sometimes. Personally, I implemented a constructive/brute force solution using a bitset, similar to knapsack optimization.Thanks for the contest!
 » 3 weeks ago, # |   0 Can anyone explain me question C?
 » 3 weeks ago, # |   0 1965D — Отсутствующая сумма подмассива? Hmm, probably you need to fix this (in English Version)
 » 3 weeks ago, # |   0 Nice Turorial
 » 3 weeks ago, # |   +16 Div1 B has a different approach:First, we construct a sequence $a$ containing $1,2,4,8\dots 2^l,v$. The sum of those integers in the sequence is equal to $k-1$. It can be proved that for every integer $i\in [1,k-1]$, there exists a subsequence of $a$ with a sum of $i$.Next, consider finding the smallest integer that can't be presented as the sum of a subsequence of $a$. After finding such integer (Let it be $s$), append $s$ to the end of $a$. This can be done using knapsack dp.This approach comfortably fits in the limits.258500094
 » 3 weeks ago, # | ← Rev. 3 →   +11 DIV 1 A: what will be the answer if test161 3 4 6 9 15from the tutorial: it is Bob but what if if we do like below:After Alice : 2 3 5 8 14After Bob: 1 3 6 12 ( as bob sees that winning state)after alice: 2 5 11after bob : 3 9 (as bob sees winning state)after alice: 1 7 (as not winning state)after bob: 6after alice: [] so why not alice is winning here?
•  » » 3 weeks ago, # ^ |   0 When the condition is "2 5 11" and it is Bob's turn, Bob can choose $k = 1$ and the stones will be "1 4 10". Now Alice must choose $k = 1$ and the stones will be "3 9". Then Bob can choose $k = 2$ and it will be "1 7". So Alice has to choose $k = 1$ and there will be only one pile of stones which has 6 stones. It means that Bob can remove all of them and win the game.I think the key of this problem is when the least number of stones is $1$, the player who should remove some stones does not have any choice but let $k = 1$. So Alice and Bob should jump out of this "rule" and force each other to be trapped in this "rule".Hope to help you.:D
•  » » » 3 weeks ago, # ^ |   0 Thanks. I have understood
 » 3 weeks ago, # |   0 Thanks for the amazing tutorial !!! It helped me for the questions I couldn't solve.
 » 3 weeks ago, # | ← Rev. 2 →   +8
 » 3 weeks ago, # |   0 Really good editorial especially for D
 » 3 weeks ago, # |   0 here is my dp solution for problem c https://mirror.codeforces.com/contest/1966/submission/258437818
 » 3 weeks ago, # |   0 I'm interested in problem missing subsequence sum. The proof is understandable but hard to come up with the solution during contest. Do you have any other similar problem like that?
•  » » 3 weeks ago, # ^ |   +1
•  » » » 3 weeks ago, # ^ |   0 I've solved it yet couldn't intuitively solve missing subsequence sum problem :(. Do you have more problem similar to that?
 » 3 weeks ago, # | ← Rev. 2 →   0 .
 » 3 weeks ago, # |   0 The solution of CF1965E is so ingenious OMG. How can you grandmasters bethink of it??!
 » 3 weeks ago, # |   0 Which problem was the one from the yandex cup
 » 3 weeks ago, # |   0 First problem was really good.