### errorgorn's blog

By errorgorn, history, 20 months ago,

## 1526A - Mean Inequality

Setter: antontrygubO_o
Preparer: errorgorn

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

## 1526B - I Hate 1111

Setter: errorgorn
Preparer: errorgorn

Hint 0
Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

## 1526C1 - Potions (Easy Version) and 1526C2 - Potions (Hard Version)

Setter: errorgorn and oolimry
Preparer: oolimry

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
Code 2 (C++)
Code (Python)

## 1526D - Kill Anton

Setter: errorgorn
Preparer: errorgorn

Hint 1
Solution
Code (C++)
Code (Python)

## 1526E - Oolimry and Suffix Array

Setter: iLoveIOI
Preparer: iLoveIOI

Hint 1
Solution
Code (C++)
Code (Python)

## 1526F - Median Queries

Setter: errorgorn and oolimry
Preparer: errorgorn

Hint 1
Hint 2
Solution
Code (C++)
Code (Python)

## Code Golf

You may have realized that python codes in the editorial are quite short. We actually had a code golf challenge among testers. You are invited to try code golf our problems and put them in the comments. Maybe I will put the shortest codes in the editorial ;)

Rules for code golf:

• any language allowed
• codes will be judged by number of characters
• must get AC in the respective problems

• +199

| Write comment?
 » 20 months ago, # |   +21 ERRORGORN OFZ
 » 20 months ago, # |   +12 I wish they were BUGABOO's so that I can solve them.QUESTIONS are really hard to ANSWER :")
 » 20 months ago, # |   +92 When the problemsetters have plans for the night: Source: 1526B - I Hate 1111
•  » » 20 months ago, # ^ |   0 nice
•  » » 20 months ago, # ^ |   +9 If that was the case , then answer for it should be "YES"...lol
•  » » 20 months ago, # ^ |   0 Sadly for him the answer for the test case "69" was "NO".
 » 20 months ago, # |   -34 speedforces :)
•  » » 20 months ago, # ^ |   +18 It was more about how fast you come to solution and not how fast you type. Code for first 4 tasks were short.
•  » » » 20 months ago, # ^ |   +18 He is talking about how fast the editorial came.
 » 20 months ago, # |   +40 I seriously hate 1111 after this contest.
•  » » 20 months ago, # ^ |   -14 I even tried Dynamic programming for multiple times. But the constrain of 10^9 killed me badly :(
•  » » » 20 months ago, # ^ |   0 You just need to use brute force to see that a number bigger than 1000~2000 will always return true, also bigger than 2000 always be true. So you can only use DP to find in a very small range, not 1e9 range :)
•  » » » » 20 months ago, # ^ |   0 good job :)
•  » » » » 20 months ago, # ^ |   0 Excellent! Thanks a lot! I cannot express to you how glad I am after getting accepted the B with Dynamic Programming! I just put a condition that any number greater than 1500 will be "YES". And Woo ! It got accepted.Here is the DP Solution for Problem B
•  » » » » » 19 months ago, # ^ |   0 bro please give me itterative dp solution if possible
•  » » » » » » 19 months ago, # ^ |   0
 » 20 months ago, # | ← Rev. 2 →   +10 Did not see solution to A.Edit: Which is a shame because I solved B and and both C correctly.
•  » » 20 months ago, # ^ |   +2 You could random shuffle the array until it becomes good. Though it makes the code longer (not that much longer), it's a nice alternative to the proposed solution.
•  » » » 20 months ago, # ^ |   0 Actually I thought about that, but was not able to aproximate the probability that it works.
•  » » » 20 months ago, # ^ |   0 It is going to take a lot of time.
•  » » » » 20 months ago, # ^ |   0 Let the number of all permutation of the 2*n elements be p=50!, without the rotations counted double it is p=49!So, how much of these p permutations qualify as "no solution" in the worst case? What is the expected number of shuffles until we find a good solution?It seems obvious that we got the most "no solution" permutations if the array is an arithmetic sequence, so WLG lets assume it is 1,2,3...,nConsider the third element, it must not be one of n-2, because all other of the n-2 elements produce a good solution. Same for the next element... and so on.So one aproximation to get a good perm looks like $(n-2)/(n-1) * (n-3)/(n-2) * (n-4)/(n-3) * ...$This formular is a of course a simplyfication and kind of simply wrong, however, it yields an propabilty of ~0.04, ie an expected value of ~25 shuffles until we find a good permutation.
•  » » 20 months ago, # ^ |   0 You could have solved A later and maybe then you would have got the idea. I usually solve problems in order, but I was not sure of my solution to A (though it was right), then moved to B which again I failed to solve. I opened C1,C2 and was able to solve them fast. Then returned to A and then to B.In A i sorted the elements first say for example 1 2 3 4 5 6 and arranged them like 1 6 2 5 3 4.
•  » » » 20 months ago, # ^ |   +3 Well, I've gotten used to thinking twice before submitting the first time.When I cannot solve A this means at some point of time I solved B, then have to decide, do I really want to participate with this? I am late, I have no solution to A.Most likely the answer is simply no, at least for me. In this contest, it turns out I would have had a positive delta even without solving A. But that is usually not the case.I would have to overcome this "rating-thinking", which would actually be good on a rational level, because it really doesn't matter whether I'm 1500 or 1600. But the point is still difficult for me.
•  » » » » 20 months ago, # ^ |   +1 It does feels bad when i lose rating but i don't skip if i don't get any solution for 40 minutes (happened in this contest). As long as we don't cross our highest rating, any rating below it will be temporary.
 » 20 months ago, # |   +98 All numbers other than 11 and 111 are useless. 
•  » » 20 months ago, # ^ | ← Rev. 2 →   -23 11 and 1 are enough as 111=11*10+1if the below condition satisfies, its YES11*a+1*b=n and a>=b*10;
 » 20 months ago, # |   +9 despite bricking the round, i enjoyed it. thanks for the amazing round!
 » 20 months ago, # | ← Rev. 2 →   +7 Thanks the authurs for nice bugaboos statements and detail + quick solutions for those bugaboos
 » 20 months ago, # |   0 i've never seen so many memes in 1 editorial
 » 20 months ago, # |   -24 i know everyone will downvote this but problem 2 is such a bad problem. CP problems should never be based one single tricky clue
•  » » 20 months ago, # ^ |   +23 i agree that it's tricky, but it's no different from any anton problem where the solution becomes trivial after finding a key observation
•  » » 20 months ago, # ^ |   +10 Why not?
•  » » » 20 months ago, # ^ | ← Rev. 2 →   -11 because problems should be built on something that you know, so that you will deduce the unknown from the known. that’s the beauty of cf. I cannot just give you riddles in cf problemsAnyways that’s just my opinion. Feel free to ignore
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   +5 Your opinion based only on solution in editorial? There are more others solutions with easy logic.
 » 20 months ago, # |   0 Please someone explain why in 2nd problem only 11 and 111 are useful. Thanks :|
•  » » 20 months ago, # ^ |   0 you can express 11111 as 111*100 +11 and 1111 as 11 * 100 +11 and use a similar argument for all other numbers of the sort
•  » » » 10 months ago, # ^ |   0 can u please tell me how to break 2047 according to this?
•  » » » » 10 months ago, # ^ |   0 i think i got it 2047=111+11*176 ♥de ka question tha
•  » » 20 months ago, # ^ |   0 let's call k times 1 as k-1. So 4-1, 6-1 and 8-1 could be made just by 2-11(1100 + 11, 110000 + 1100 + 11, 11000000 + 110000 + 1100 + 11). Further 5-1 and 7-1 can be made by 2-1 and 3-1 alone(11100 + 11, 1110000 + 1100 + 11) so instead of using 4-1, 5-1, 6-1, 7-1, 8-1 we can simply use 2-1 and 3-1 so we can ignore everything except 2-1 and 3-1.
 » 20 months ago, # |   +14 will this be the fastest editorial of all time?
 » 20 months ago, # |   0 So we can just brute force all 11 value of D to check whether X can be made. but we would still have to find A and C to satisfy equation ?
•  » » 20 months ago, # ^ |   0 but this is a YES/NO.If we find (A+C,D) then the answer is YES. we dont care about what A and C actually are.
•  » » 10 months ago, # ^ |   0 Spoilerreplacing 111 with 11 vice versa will also work , since we can derive X=(C.11+B).111+D.11 , when A=C.111+D But need more iterations(<200 i hope) , since value 11 is small to subtract int TC; cin>>TC; while (TC--){ int n; cin>>n; rep(x,0,20){ if (n%111==0){ cout<<"YES"<
 » 20 months ago, # | ← Rev. 2 →   +10 I used random shuffle until the array is good :( (problem A)
 » 20 months ago, # |   +1 Pls tell me how to improve my skills! I couldn't solve any problems in this contest. :(
•  » » 20 months ago, # ^ |   +8 first have decent knowledge of known algorithms, mathematics, number theory and probability. Then solve past problems. The last one is necessary
 » 20 months ago, # |   +1 How in problem C1, the dp does not depend upon the actual potions taken? I mean, how can I calculate ans for dp[i][k] without knowing what is my current health?
 » 20 months ago, # |   +5 Well put-together editorial!
 » 20 months ago, # |   0
 » 20 months ago, # |   +8 Thanks for B.
 » 20 months ago, # |   0 Can anybody explain what is wrong in my solution for problem C1 div2(https://codeforces.com/contest/1526/submission/117651697)
•  » » 20 months ago, # ^ |   +3 Consider a multiset of integers: { 1 , 1 , 2 , 3 , 4 }When you write this line : a.erase(*a.begin()); // or try to erase any occurrence of an element SpoilerIt erases all the occurrences of that element. The multiset becomes : { 2 , 3 , 4 } SolutionTo avoid this, You can make use of iterators: auto it = a.begin(); a.erase(it); or you can use a.erase(a.begin());The multiset now becomes : { 1 , 2 , 3 , 4 }I hope you understand this simple issue with your code.
•  » » » 20 months ago, # ^ |   0 thnx man u really told a very good point! i was doing the very same mistake and was stuck on this since yesterday , thnx again !!
 » 20 months ago, # |   +22 Vote if you hate 1111 too :(
 » 20 months ago, # |   +4 Weird Idea for Problem A Though the idea is not good, we can random_shuffle() the whole array for infinity times and check if it satisfies the condition at any moment. (In this way, my problem A got accepted)
•  » » 20 months ago, # ^ |   +9 Yea... the array that cause this to fail with most probability is $1,2,3,4,\ldots$Even then its like around 50% chance to fail...
 » 20 months ago, # |   0 C1 was easier than B for me even though I wasn't able to solve both
•  » » 20 months ago, # ^ |   0 Brother can you please tell what is the error in my solution for C1(https://codeforces.com/contest/1526/submission/117651697).
•  » » » 20 months ago, # ^ |   0 This line: s.erase(*s.begin());Erases all copies of the value of s.begin(). You can pass an iterator to s.erase so just replace it withs.erase(s.begin());
 » 20 months ago, # |   0 I tried Top Down DP approach for C1. Potions (Easy Version) but I got TLE on pretest-3. Here is my code. Can you tell me why I got TLE for this and what should be the optimal Top-Down DP Solution for the same? #include using namespace std; #define ll long long int vector v; ll n; map,ll> dp; ll fun(ll i,ll cur) { if(i>n or cur<0) return 0; if(i==n) return cur>=0; if(dp.find({i,cur})!=dp.end()) return dp[{i,cur}]; ll ans=fun(i+1,cur); if((cur+v[i]) >=0) ans=max(fun(i+1,cur+v[i])+1,fun(i+1,cur)); return dp[{i,cur}]=ans; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(ll i=0;i>x; v.push_back(x); } cout<
•  » » 20 months ago, # ^ |   +9 Put the code in the spoiler tag, it's annoying
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 What is spoiler tag? I don't know can you tell me about this?
•  » » » » 20 months ago, # ^ |   0 some code some code... It is written like this, without spaces, ofc.< spoiler summary="some code" > some code... < /spolier >You can also click the CF logo above the text box and see the spoiler thing.
 » 20 months ago, # |   +11 For B, what about this simpler solution:Consider $x=n \mod 11$ We need to use at least x times 111, so if $n>=111*x$ then there is a solution since $n-x*111=0 \mod 11$, else there is none.
•  » » 20 months ago, # ^ |   0 Can you please explain how your solution works?I mean the idea behind this solution. Thanks.
•  » » » 20 months ago, # ^ | ← Rev. 3 →   0 The idea is the same as in the editorial, a number that can be build by the rules of the problem can also be build as a sum of 11 and 111.111%11==1 So we must use at least n%11 times a 111 to build n. This means n cannot be smaller than (n%11)*111. And we can build n by using (n%11)*111 + y*11 for some arbitray y.117686327
•  » » » » 20 months ago, # ^ |   +1 n can be written as : n = q*11 + (n%11), let (n%11) = x.I am not getting this line:So we must use at least n%11 times a 111 to build n.
•  » » » » » 20 months ago, # ^ |   0 $(x*11 + 1*111) = 1 \mod 11$$(x*11 + 2*111) = 2 \mod 11$$(x*11 + 3*111) = 3 \mod 11$...
•  » » » » » » 20 months ago, # ^ | ← Rev. 4 →   0 Sir, can you please tell me what's wrong in my code down below? x= 11*a+ 111*b (a>=0 and b>=0) therefore I check whether (x-111*i)%11==0 or (x-11*i)%111==0 for some i in the valid range. This however doesn't seem to work!Code: Spoiler#include using namespace std; #define ll long long int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ ll x; cin>>x; bool flag= false; for(int i=0; i<90909092; i++){ if((x-11*i)<0) break; if(((x-111*i)%11==0) or ((x-11*i)%111==0)){ flag= true; break; } } if(flag) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 0; } 
•  » » » » » » » 5 months ago, # ^ |   0 Hint : ( n — i * 111) can be negative.
 » 20 months ago, # |   +6 Spoilermt19937 rng(177013); Oh no
 » 20 months ago, # | ← Rev. 2 →   0 You can drink Potion with 0, right? but the ans is not according to that, what's wrong in this code int main() { int n;cin>>n; vector v(n); vector ne; int ans=0; int count = 0; for(int i=0;i>v[i]; if(v[i]>=0){ count+=v[i]; ans++; } else ne.push_back(-1*v[i]); } sort(ne.begin(),ne.end()); int len = ne.size(); for(int i=0;i=0){ ans++; }else{ break; } } cout<
•  » » 20 months ago, # ^ |   0 Your solution is wrong. You are adding all the negative values at the end, which is not what the question is asking for.For example, for the case1 -2 1000if you add positives and then subtract negatives you will get 3 as the answer. However, we cannot take -2, since that would decrease your running total to -1, which is not allowed.
•  » » » 10 months ago, # ^ |   -10 thanks , i was also doing the same thing
 » 20 months ago, # |   0 What is the base case for 1526C1, (Method 1)DP solution? Also, shouldn't k increase, if we are counting how many potions are we taking?
•  » » 20 months ago, # ^ |   0 dp[0][0] = 0
 » 20 months ago, # |   +3 Love the way "You write editorial".
 » 20 months ago, # |   0 Problem D, I used cin, cout, unordered_map to solve and get TLE, change these to scanf, prinf and character to number and unordered_map to array and got AC.Poor me!
 » 20 months ago, # |   +6 wtf is Chicken McNugget and why on earth should one even know this sht????
•  » » 20 months ago, # ^ |   0 It's an interesting theorem that has a rather remarkable statement, after a certain number, every number can be written in the form of ax + by (given a, b are coprime).
•  » » » 20 months ago, # ^ |   +6 It is easy to understand once you know it, but it is not known/popular and thus a problem which intended to be easy (Problem B Div. 2) should not require these kinds of knowledge, but instead, it should require thinking.
 » 20 months ago, # |   0 In question C, why using upper_bound in multiset while substituting the ith number gives wrong answer but removing the last element does the trick?
 » 20 months ago, # |   0 How to solve C using dp ,please explain.
•  » » 20 months ago, # ^ |   0 say dp[i][j] means max HP after reaching i_th glass and having drunk j health potions. For the transition we can say that dp[i][j] = max(dp[i-1][j](meaning we did not drink the i_th potion), dp[i-1][j-1]+a[i](meaning we did drink the i_th potion)). For base case dp[-1][-1] = 0.(Take care of the indexing :))))
•  » » » 20 months ago, # ^ |   0 Aren't we trying to maximize the number of potions we take, So in the dp why did we take dp[i][j] to be maximum health?
•  » » » » 20 months ago, # ^ |   0 yeah, see the answer will be the max j for which dp[n-1][j] is non negative. We are trying to keep the track of max health that we can have after being on i_th potion and having drunk j potions. The reason for that is that in future we might have to drink potions that'll decrease the character's health and so it should be as high as possible right now to be able to drink those negative potions while remaining alive.
 » 20 months ago, # | ← Rev. 11 →   -31 Easiest Solution. Explanation: all the numbers 1111,11111,111111..... can be written as x*11+y*111 where x,y are non-negative integers. So the only numbers we have to bother are 11,111. Therefore we have to check if the given number can be written as a*11+b*111 where a,b are non-negative integers.  Spoiler#include using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; if(n%11==0 || n%111==0) cout << "YES" << endl; else{ int y = n/11; int b = n%11; int a = y-10*b; if(a>0) cout << "YES" << endl; else cout << "NO" << endl; } } } [contest:723][problem:B]
•  » » 20 months ago, # ^ |   +5 Put your codes in spoiler, please!
 » 20 months ago, # | ← Rev. 5 →   +5 Problem B can be solved in a much simpler way, the given number (say x) will be of the form x = a1 * 11 + a2 * 111 since, 111 can be written as 11*10 + 1, we can obtain the value of a2 as, a2 = x % 11Then we can check if x - a2*111 is non-negative and divisible by 11.
•  » » 20 months ago, # ^ |   +4 Actually you only need to check if it is non-negative.
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Can anyone plz elaborate why 11*10 + 1 ensures that we can take value of a2 as x % 11 ?
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +1 Doing that, we can write the equation as x = a1 * 11 + a2 * (11*10 + 1) => x = a1 * 11 + a2 * 11 * 10 + a2 => x = 11 * (a1 + 10 * a2) + a2 The equation takes the form, a = b*q + r Hence a2 will be remainder of x % 11
 » 20 months ago, # |   +22 Anton lived today, but I'll get him next time for sure.
 » 20 months ago, # |   +12 Thanks for providing method 2 with Chicken McNugget Theorem in solution B.
•  » » 19 months ago, # ^ |   0 For those who are interested in understanding the proof of correctness of this theorem can refer this resource
 » 20 months ago, # | ← Rev. 2 →   0 I used multiset in C1 and C2 instead of priority queue codevoid solve() { int n;cin >> n; vector a(n); int ans = 0; forn(i, n)cin >> a[i]; int su = 0; multiset s; forn(i, n) { su += a[i]; ans++; s.insert(a[i]); while (su < 0) { su -= *s.begin(); s.erase(s.begin()); ans--; } } cout << ans; } 
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Priority queue works faster than multiset, except for that they don't differ.
•  » » » 20 months ago, # ^ |   0 and, priority queues don't have iterators afaik
•  » » » » 20 months ago, # ^ |   0 I meant in problem C.
•  » » 20 months ago, # ^ |   +5 I used segment tree with min() merge function! Your solution is much nicer though.
•  » » » 20 months ago, # ^ |   0 Please can you explain the segment tree aproach?The editorial was a bit difficult for me to understand.Thanks in advance.
•  » » » » 20 months ago, # ^ |   +3 You need to track the sum over the prefix [0, len]. Each time this sum dips below 0 you use segment tree to find the minimum value and the corresponding index. This is the one drink that we retroactively decide not to drink. Set it's value to zero in the tree and increase your sum (current health) by an appropriate amount. Repeat until your health is no longer negative. Move on to the next prefix. n*log(n) time. At least that's how I used it.
•  » » » » » 20 months ago, # ^ |   0 Thanks a lot .I think I got the basic idea.
 » 20 months ago, # |   +5 I have some questions regarding the proof of D. What is D1 and D2 ? Could you pls elaborate the equation and the next line "upto a contradiction"
 » 20 months ago, # |   0 I think my solution on D should give TLE, but i can't prove it. In my code, i did a 4! * (2^3) * N log N solution, and in first time i got TLE on pretest 5 . Basically the solution was: For any permutation of the 4 letters, try to rearrange the string by put the same letter together on the left or right side (well, that's not necessary cause im trying all the permutations, but i didnt realize) and then use FenwickTree to count inversion (same solution of editorial, but with *8 because of bitmask).To avoid TLE i used a set that checks if the initially string miss some letter, in that case, i can avoid use some permutations. By doing that, i think the constant factor (4! * (2^3)) was reduced a little, but i think too that maybe in any worst case it shouldn't change. It passed from TLE on pretest5 to accepted with 970ms.If anyone can find a case, or prove why using the set improves the code, it would be cool. Thanks.
 » 20 months ago, # |   0 memesforces.
 » 20 months ago, # |   +3 Can anyone provide code/ intuition for the Merge Sort approach for bugaboo D?
•  » » 20 months ago, # ^ |   0 I didn't solved because I didn't notice that there were only 4 characters , :( . But I had the intuition , see I observed that all the elements will be together by righting a few things down and verifying with sample test cases , then I thought there were 26! Permutation ( as I didn't read 4 chars , :( ) . So now if you would look at that there are just 24 permutations and for sure the solution will be one of those permutation , then for the merge sort technique it is a well known idea of that number of inversion = minimum no. Of adjacent swaps , and it could be solved using PBDS and Merge sort .
•  » » » 20 months ago, # ^ |   0 What's PBDS?
•  » » » 20 months ago, # ^ |   +3 What was the intuition behind the elements would be together? @dhruv7888
•  » » 20 months ago, # ^ |   0 The whole idea is that that it is a number of inversions, after that you just calculate inversions using mergesort, a standard trick.You can look at my submission (yeah, I just copy-pasted merge sort from the internet if anything)
 » 20 months ago, # |   +3 I think I don't understand why greedy for C2 works. I wonder can it not happen that one swap with the minimum in priority queue is not enough and we might need two swaps? Sure, it will decrease the number of potions for now, but it might happen that the potentially more positive value gained will help us take more negative potions in the future or something like that? And i am only talking about the case when after one swap our sum remained < 0, but after two swaps the sum became >= 0.
•  » » 20 months ago, # ^ |   0 If the current element is -11 and you had -10 before as most negative element , then you will not remover , but if you had -11 before and now the current element is -10 then deleting -11 is enough you don't need to delete any more.
•  » » » 20 months ago, # ^ | ← Rev. 2 →   0 No I mean, if let's say our priority queue contains -7 and -5 . I just came across -11 and I can't take it as my sum becomes less than 0, so I check sum + 7 — 11 and it is negative still but if I also take 5, then it becomes sum + 7 + 5 — 11 which somehow comes out to be >= 0 , then isn't it optimal to remove both -7 and -5 and take the 11? Sure, the number of potions decreased but since our sum is now greater than earlier value and greater than 0, we might able to take more potions later on. Did I miss something? EDIT: I understood . Thanks :)
 » 20 months ago, # |   0 Can someone explain question B in very simple language to someone who suck at Cp..
•  » » 20 months ago, # ^ |   +16 The simplest solution:All the given numbers mod 11 are 0 or 1.Suppose X%11 is not zero, then we need to cancel this out. This needs at least 111*(X%11). So the one-line solution is (X>=111*X%11? "YES":"NO").
 » 20 months ago, # |   0 In the potions problem, why do we keep the number of potions taken till now as one of the states? I mean that is something that we need to calcuate right? Why do we include it in the states?
 » 20 months ago, # |   0 Problem C1 easy version: how ro solve this provlem using 1D dp
•  » » 20 months ago, # ^ |   +4 dp[i] = maximum health you can have with drinking exactly i potions in this level.for i : 1 -> n: potions for j : n -> 1: number of potions we want to drink if(dp[j - 1] + a[i] >= 0) dp[j] = max(dp[j], dp[j - 1] + a[i])Answer is the largest i, that we have a valid value for dp[i]
•  » » » 20 months ago, # ^ |   0 Can you explain a bit more why are you defining dp[i] as the "Maximum Health"?
•  » » » » 20 months ago, # ^ |   +3 Dp from editorial: "Let dp[i][k] be the maximum possible health achievable if we consider only the first i potions, and k is the total number of potions taken."Just like what editorial have explained, but we wanna remove the part of "if we consider only the first i potions" and we will only have dp[k]. So now dp[i] = maximum health that can be achieved by taking i potions in this level (we will iterate over array of potions and "level" will be that). The only thing is we need to iterate over number of potions we wanna take form n to 1, since we need to update our dp from last level, so that if we are updating dp[i], we need dp[j] (for all j < i) to be just like the last level and haven't been updated yet.
 » 20 months ago, # |   +20 segment tree in Div2 C seriously?
•  » » 20 months ago, # ^ |   +13 Well it was not a segment tree bugaboo though I solved it using it as well ( You can verify it from editorial they havent even mentioned it ).
•  » » » 20 months ago, # ^ |   +13 However, using a range add range max lazy propagation segment tree, we can check if a certain potion can be drunk without dying
•  » » » » 20 months ago, # ^ |   +8 Yeah I did the same :)
 » 20 months ago, # | ← Rev. 2 →   0 For problem C2 "Method 2 — Greedy 1" can be implemented without a lazy segment tree using BIT: Maintain a set of positive potion positions, and a priority queue of {negative potion value, index}. Check if the negative potion can be consumed using BIT. Greedily start decrementing the potion value of positions in descending order of positions that are less than the index while exhausting the priority queue & remove the position from the set if potion value reaches zero.UPD: It turns out that my previous submission (without BIT) gives TLE for this hack case since my worst-case time complexity was $\mathcal{O}(n^2\log{}n)$, after optimizing using BIT it reduces to $\mathcal{O}(n\log{}n)$. Cheese submission: 117672658, Optimized submission: 117983932
 » 20 months ago, # |   +3 There is a little difference of alphabet between D and editorial. It looks like DNAs initially and you modified it for your outstanding coordinator.
 » 20 months ago, # |   +8 smallest and lovely solution for I Hate 1111 can be:-as we know we have to check only for 11, 111 (from editorial), if we can represent x = a*11 + b*111 (where b is as low as possible), we return true else, we return false And also 111 = 11*10 + 1, therefore equation reduces to x = (a+10*b)*11 + bnow b = x%11 and a + 10*b = x/11 so if the above conditions match we output true, else false. The neat sol. can be found at :- https://codeforces.com/contest/1526/submission/117617666Hope it helps ;)
 » 20 months ago, # | ← Rev. 3 →   0 Is the name Anton came from Silicon Valley series?
•  » » 20 months ago, # ^ |   0 nope, its name of coordinator that reject a lot of problems
 » 20 months ago, # |   +4 Can someone explain how they got the intuition for placing the same letters together in D?
 » 20 months ago, # |   +2 Problem B was really nice and loved the editorial and the way solutions are given to the problems. Kudos to writers and testers!!
 » 20 months ago, # |   -8 I loved I Hate 1111
 » 20 months ago, # |   0 what if in problem B there are 3 numbers left 11a+111b+(s)c=x how will we find if x can be made by adding any number of these 3 numbers 11,111,s ?
•  » » 20 months ago, # ^ |   0 Read about Extended Euclidian and Linear Diophantine. CP-ALGO
 » 20 months ago, # |   +6 I have another visual proof of the Chicken McNugget theorem (from problem B)n = 5 and m = 7, so it can get all the numbers after 5*7-5-7 = 23Here is the number line of 5's Then, here's the multiples of 7 lined up with it You shift the marks of 7's by 5, which represent the multiples of 7 after 5 was added to them. Then you shift them again, which represent the multiples of 7 after 2*5 was added to them. (the red are the oranges shifted by 5 once, green are shifted by 5 twice) For the formula of 5*7-7-5, when you subtract 7 from 35, you get to the last orange mark, which is 28. When you subtract 5 from 28 you get the last empty mark. 28 is the last distinct mark (has a position of 3 while others have positions 1, 2, and 4) that you need to get all the numbers, as you can see from the picture. If you ignore the colors you see the positions between the multiples of 5 slowly fill up.
 » 20 months ago, # |   0 Can anybody explain what is wrong in my solution for problem C2？ First step I choose all positive number and calculate the sum of them. Second step I use priority_queue to find the minimum negative number, considering the sum and the sum of prefix of positives . Third I use BIT to substract the negative number I choose Here is my code:Your text to link here...
 » 20 months ago, # |   0 Can anyone share DP solution for problem 3?
•  » » 20 months ago, # ^ |   0 see submissions of different peoples'. u might find one. ;)
•  » » 20 months ago, # ^ |   0 You can see my submission it's pretty messy though since it's a recursive code.
•  » » » 20 months ago, # ^ | ← Rev. 3 →   0 Hey weakestOsuPlayer_244, I saw your code for C1 and C2 non are recursive DP. Can you please provide me the recursive DP code or maybe point out, what I'm doing wrong in my submission : 117812458 Thanks.
•  » » » » 20 months ago, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/1526/submission/117724267It's the same as the iterative version at least in my code I just reversed the string and updating dp recursively..you can view this submission too.https://codeforces.com/contest/1526/submission/117686218
 » 20 months ago, # | ← Rev. 3 →   0 Code Golf for Question B 117721466
 » 20 months ago, # |   0 why tag dp for problem B ? is there a dp soln too?
•  » » 20 months ago, # ^ |   0 Here is a dp solution for method2 117718666
 » 20 months ago, # | ← Rev. 7 →   0 //PROBLEM C EASY VERSION//GOT TLE USING MAP **** //USE MAP BECAUSE I WANT TO STORE ARRAY ELEMENTS WHICH IS NOT POSSIBLE IN 2D DPmap, int> dp;//USE MAP PAIR FOR INDEX AND SUM OF ELEMENTS OF ARRAY// AND STORE THE COUNT OF POTIONSint helper(int arr[], int i, int sum,int cnt,int n){ if(i == n){ return cnt; } if(dp.find({i,sum}) != dp.end()){ return dp[{i,sum}]; } if((sum + arr[i]) < 0){ return helper(arr,i+1,sum,cnt,n); } **//I USE KNAPSACK PROBLEM TO CHECK** **//IF I INCLUDE I INCREASE THE COUNT OF POTION** **//AND RETURN THE MAXIMUM COUNT** //IN INCLUDE I SUM THE POTION AND INCREASE THE COUNT int inc = helper(arr, i+1, sum + arr[i], cnt+1,n); //IN EXCLUDE I DO NOTHING PASS SAME int exc = helper(arr, i+1,sum, cnt,n); return dp[{i,sum}] = max(inc,exc); } void solve(){ int n; cin >> n; int arr[n]; for(int i = 0;i < n; i++)cin>>arr[i]; cout<>arr[i]; cout<
•  » » 20 months ago, # ^ | ← Rev. 2 →   0 Can AnyOne Help me with this TLE.??
•  » » » 20 months ago, # ^ |   0 Seems like you can use a vector, instead of using a map. So something like — vector> cache(n+1, vector(n+1, -1)).
 » 20 months ago, # |   +22 after reading each problem in this round i felt like "no one come up with this problem before, really?", especially for problem E
•  » » 20 months ago, # ^ |   0 it's not a good or bad, it's just a fact :)
•  » » » 20 months ago, # ^ | ← Rev. 2 →   +27 yea the way i usually set problems is taking existing problems and twisting them.B: I looked at 1517A - Sum of 2050 and wondered what happens if instead of $2050, 20500,\ldots$ we have $2050,20502050,\ldots$ instead.D: The problem of minimal number of swaps is well known, so I wondered can be find a string that maximizes the number of swaps.F: I think there are probably a few interactives with queries such as $|p[a]-p[b]|$, so I tried to make it annoying with median of $\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$. But the turns out the solution was quite interesting.It's crazy how difficult you can make a problem become after just a tiny change. Like one of my favourite examples is AGC51_F. I think most people might know about telling the time using two sandglasses with integer times, but I think only someone amazing like rng_58 would dare to ask what happens if one of them have a irrational time.
 » 20 months ago, # | ← Rev. 2 →   -10 Problem B be like: Read the name of the problem ;) Sometimes, Name also tells the intuition behind the problem. ;)
 » 20 months ago, # |   +6 Another approach for B, as 111=11*10+1if the below condition satisfies, its YES11*a+1*b=n and a>=b*10;
 » 20 months ago, # |   +15
 » 20 months ago, # |   0 where σ(x)={1,if x>0 −1,if x<0, or rather σ is the sign function. Can anyone explain me the meaning of these symbols used in D problem
•  » » 20 months ago, # ^ |   0 Yea sorry about that. I did not realize cf screwed up the formatting of it.I have updated it in the editorial.It was meant to look like this.But I could not get it to render like this on cf. If anyone finds out how to do, please reply
•  » » » 20 months ago, # ^ |   0 I got it. Thank you for clarification
 » 20 months ago, # | ← Rev. 3 →   +3 For Problem 1526C1, Method 2 — Greedy 1 — In the editorial, we have — We iterate through the potions in non-decreasing order and drink the potion if we do not die. Shouldn't it be non-increasing order?
 » 20 months ago, # |   0 Can anyone tell why problemset name is changed to bugabooset?
 » 20 months ago, # |   0 I am confused on C problem on test case #2.There is array of numbers -3 -3 -7 -7 -1 -7 3 3 -2 -1 0 -7. Well, if you choose -1,3,3,-2,-1 and 0, it will be non-negative result, hence the maximum number you can pick is six. Why they state in solution that the answer is five, if obviously I have proved that you can pick six of them?
•  » » 20 months ago, # ^ |   0 Read the problem carefully, it is told that healt at any instance should be non-negative, so even if heath is negative at some point and then becomes +ve later, the answer is wrong.
 » 20 months ago, # |   +1 What is WLOG here, in the proof of D. Since D1+D2≥0, either D1≥0 or D2≥0. WLOG, D1≥0.
•  » » 20 months ago, # ^ |   +6 Without Loss of Generality: Wikipedia. It is done to reduce the number of cases in a proof, without making the proof invalid, because there is a certain kind of symmetry.
 » 20 months ago, # | ← Rev. 2 →   +1 Sorry...
 » 20 months ago, # | ← Rev. 3 →   0 How are the D1 and D2 written in the editorial of problem D? I am not getting the intuition that letters should be grouped together :( Or maybe someone can explain clearly how they come up with the intuition of grouping letters together? NVM GOT IT :)
 » 20 months ago, # |   0 1526B - I Hate 1111 Can someone give the solution code using method 1 in the B problem?
•  » » 20 months ago, # ^ |   0
 » 20 months ago, # |   +3 I think there is a typo in Problem E's editorial. "Now, this becomes count how many arrays of $(n-1+2)=(n+1)$ non-negative elements sum to $k-cnt$." This should be "sum to $k-cnt-1$".Therefore final answer should be $C_{n+1-1}^{n+1+k-cnt-1-1}$ i.e. $C_n^{n-1+k-cnt}$
•  » » 19 months ago, # ^ |   0 Why the sum is k - cnt - 1, we want cnt elements >= 1, so the rest sum should be k-cnt? Or am I missing something?
 » 20 months ago, # |   0
 » 20 months ago, # | ← Rev. 2 →   +1 It's tough for me to come up with the proof of the Greedy solution of C on my own, and also, I find it very difficult to understand the proof of greedy solution of C.Any help, how can I get over this? Usually, I cannot prove my solutions clearly (It usually gets unorganised, I don't know how). Any specific advice which will help me?
•  » » 20 months ago, # ^ |   0 https://www.youtube.com/watch?v=zf9G9x9bs9c&t=2319s this may help
 » 20 months ago, # |   +3 can someone please give a easy mathematical proof for problem d.For me the proof given is a bit difficult to understand.
•  » » 20 months ago, # ^ |   +1 Let s be the original string and t be the optimal ans string so that the number of moves to convert t into s is maximum.So, how do we calculate the number of moves? Basically we go on moving from left to right reading each character of si one by one , find the earliest occurence of this character in the substring t[i..n-1] and then do the swap and appropriate value to our no. of moves.Let us assume we are currently reading the character at ith pos which is x. Also let j be the next pos where x ocuurs. So we have something like .........x????????????x????????? where ? can be any valid character other than x and '.' means we have already settled that position with appropriate character. Lets also assume that now t something looks like ..........???????x???????x???????. As you can clearly see as we move x by one our ans also increase by 1 and hence it is always optimal to club all the x's to the rightmost x in our suboptimal ans string.
•  » » » 20 months ago, # ^ |   0 THANK YOU VERY MUCH NOW I UNDERSTOOD.THANKS A LOT AGAIN
 » 20 months ago, # |   0 Code Can anyone help me with problem D Kill Anton? Here, I have tried to calculate the number of inversions by segment tree. I have solved 1430E-String Reversal using the same segment tree method for calculating the number of inversions, and here is my submission for that. I couldn't figure out what mistake I am making here. Here is my Code for Kill Anton.
 » 20 months ago, # |   0 Can C1. Potions (Easy Version) be solved using Top-Down DP?
•  » » 20 months ago, # ^ |   0 did it just now .. you can check my submission here ... 118020188
 » 20 months ago, # |   0 Anyone who understood C2 using DP / SegTree given in editorial ? .... , It will be great help if it can explained in simpler words...Anyone?
 » 20 months ago, # |   0 aaaaa I'm fukn stupid. for problem F, I didn't realize that if there was a tie for the furthest $x$, you could simply choose any one of them.Instead, I did the following. Consider the four numbers $x, y, z, w$. Suppose $x$ and $y$ are tied for furthest, and $z$ and $w$ are tied for second-furthest. We can repeat the same queries on those numbers using $(b, c)$ and $(a, c)$ instead of $(a, b)$. Out of those, it's guaranteed that one of them won't produce a tie for the furthest number.needed hint 1 and a full day in order to upsolve, my brain is melted now tho :)
 » 20 months ago, # | ← Rev. 2 →   0 I have O(1) general solution for problem B (div2). Please find submission at: https://codeforces.com/contest/1526/submission/118087579I have tried to capture the logic in the image attached. HerePlease let me know if you find error in the solution. Thanks!!
•  » » 20 months ago, # ^ |   +3 No problem I think.
 » 20 months ago, # |   0 Hi! can someone please explain the logic of problem D, please? I'm not able to approach the problem right.
•  » » 20 months ago, # ^ |   +3 This problem is basically a "sequel" to this other one : https://codeforces.com/problemset/problem/1430/E.In this problem, we have an extra observation to make, which is that any optimal string will always have equal characters as a consecutive substring. The proof of this is in the editorial. Having said that, you can notice that we only have 4 different characters in our initial string (big hint) and therefore the problem is reduced to trying all $4!$ permutations of the four characters and manually counting the inversions (i did this with lazy segment tree). This last part of counting inversions is basically the same idea as the problem in the link above.My solution : https://codeforces.com/contest/1526/submission/118123584
•  » » » 20 months ago, # ^ |   0 Thank you! This helped a lot! So the time complexity would be, O(N!(NlogN)) right? Assuming we have N unique characters? (if we use mergesort to calculate number of inversions)
•  » » » » 20 months ago, # ^ |   0 It's $O(24Nlog(N))$ where $N$ is the length of the input string.
 » 20 months ago, # |   +14 what is the intuition behind problem D's solution or how did people came up their idea ?
 » 20 months ago, # |   0 potions easyversion....dp method...isnt it wrong?...we need the max potions possible
 » 20 months ago, # |   +5 Excuse me, why we can say |y2-a|<=|a-1| in Proof 4, Problem F? As we have no idea how large "a" exactly is. What if "a" were too large? Thanks for anyone's help! Noted that "pa
•  » » 20 months ago, # ^ |   +5 Good catch!The editorial has been updated with a (hopefully) correct proof now :)
•  » » » 20 months ago, # ^ |   0 Thanks for replying! And I think ksun48's solution was nice, that he found where 3 and N-2(or N-3)was, and try query(1,y1,y2) when y1 maybe 2 or N or N-1 and y2 maybe 3 or N-1 or N-2. If we got response "1", we found 2.My English is not so good, sorry:)
 » 19 months ago, # |   0 can anyone explain c2 greedy 1 solution. i couldnt understand the editorial
 » 19 months ago, # |   0 why sorting (in decending) not working in problem C.
•  » » 19 months ago, # ^ |   0 Because you can't change the order of potions.
 » 18 months ago, # |   0 In the solution for problem E, the last step is calculating However, in the solution(python), it says k-cnt+n-1 choose nMy result is also n+k-cnt-1, and my submission is accepted https://codeforces.com/contest/1526/submission/122438057Is there a typo, or I missed something?Thank you!
 » 10 months ago, # |   0 simple solution for c(hard) https://codeforces.com/contest/1526/submission/150283870
 » 10 months ago, # |   0 For B: the number can represent by n = 11*x + y*111; n = 11*x + y*(11*10+1); n = 11(x+10*y) + y; (n-y)/11 — 10*y = x; if x>=0 ans "YES" otherwise "NO" (Where y = n%11);
 » 9 months ago, # |   0 Div2B Solved using Linear Diophantine: https://codeforces.com/contest/1526/submission/155051115
 » 9 months ago, # |   0 // rep0(i,n) // { // sum+=a[i]; // } // if(sum>=0) // { // cout<= 0) // {break;} // } // } // }can someone tell how my approach is wrong for C?
 » 7 months ago, # |   0 in the solution of problem B (1526B — I Hate 1111), the author only run the loop for 20 times, how it is guaranteed that the answer will be found within 20 iterations?because if x is too large, like 10e8, after 20 iterations it will still remain tense to 1e8please help me to understand thisi am taking about this loop : rep(x,0,20){ if (n%11==0){ cout<<"YES"<