### errorgorn's blog

By errorgorn, history, 3 weeks 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 Tutorial of Codeforces Round #723 (Div. 2) Comments (262)
 » ERRORGORN OFZ
 » I wish they were BUGABOO's so that I can solve them.QUESTIONS are really hard to ANSWER :")
 » When the problemsetters have plans for the night: Source: 1526B - I Hate 1111
•  » » nice
•  » » lol
•  » » If that was the case , then answer for it should be "YES"...lol
•  » » Bagaboosetter ;-)
•  » » Sadly for him the answer for the test case "69" was "NO".
 » speedforces :)
•  » » It was more about how fast you come to solution and not how fast you type. Code for first 4 tasks were short.
•  » » » He is talking about how fast the editorial came.
 » I seriously hate 1111 after this contest.
•  » » I even tried Dynamic programming for multiple times. But the constrain of 10^9 killed me badly :(
•  » » » 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 :)
•  » » » » good job :)
•  » » » » 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
•  » » » » » 2 weeks ago, # ^ | ← Rev. 3 →   DP is overkill for this. The highest number that's not possible is 1099, which is less than 1111, so you basically need to check if the number is of form 11x+111y. This can be written in a simple for loop with max 10 iterations for a number. My submission Logicif (n>1099){ cout<<"YES\n"; return; } for(ll i=0; i*111<=n; i++){ if ((n-(111*i))%11==0) { cout<<"YES\n"; return; } } cout<<"NO\n"; 
•  » » » » » » can you elaborate a little bit pls
•  » » » » » bro please give me itterative dp solution if possible
•  » » I thought I just need to find mod of the 111.. up to string length and then reduce it till it becomes 0 or one-digit number but the wrong answer on pretest 2 I really got frustrated.
•  » » » Same here man
 » 3 weeks ago, # | ← Rev. 2 →   Did not see solution to A.Edit: Which is a shame because I solved B and and both C correctly.
•  » » 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.
•  » » » Actually I thought about that, but was not able to aproximate the probability that it works.
•  » » » It is going to take a lot of time.
•  » » » » 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.
•  » » 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.
•  » » » 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.
•  » » » » 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.
 » All numbers other than 11 and 111 are useless. •  » » 3 weeks ago, # ^ | ← Rev. 2 →   11 and 1 are enough as 111=11*10+1if the below condition satisfies, its YES11*a+1*b=n and a>=b*10;
 » despite bricking the round, i enjoyed it. thanks for the amazing round!
 » 3 weeks ago, # | ← Rev. 2 →   Thanks the authurs for nice bugaboos statements and detail + quick solutions for those bugaboos
 » i've never seen so many memes in 1 editorial
 » i know everyone will downvote this but problem 2 is such a bad problem. CP problems should never be based one single tricky clue
•  » » +1
•  » » 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
•  » » Why not?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   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
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   Your opinion based only on solution in editorial? There are more others solutions with easy logic.
•  » » » » » Yeah, whatever helps you sleep at night
 » Thanks for the early tutorial!
 » Please someone explain why in 2nd problem only 11 and 111 are useful. Thanks :|
•  » » 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
•  » » bcoz all even 11... can be divided into 11*10^x +11*10*x-2.... in this manner and this way all odd for 111.
•  » » » Hey, 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! Codeint main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ int x; cin>>x; bool flag= false; int i=0; while(true){ if((x - 11*i)<0){ break; } else if((x - 11*i)%111 == 0 or (x - 111*i)%11 == 0){ flag= true; break; } i+=1; } if(flag) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 0; } 
•  » » » » seems fine to me is it giving WA or TLE?
•  » » » » » WA, if I remove (x — 111*i)%11 == 0) condition from the if statement, it gives AC. Why so though?
•  » » » » » » But you are using or condition it should not have happen may be a bug!!
•  » » » Understood, thanks guys
•  » » 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.
 » will this be the fastest editorial of all time?
 » 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 ?
•  » » 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.
•  » » » Thanks.
•  » » » how?
 » 3 weeks ago, # | ← Rev. 2 →   I used random shuffle until the array is good :( (problem A)
 » Pls tell me how to improve my skills! I couldn't solve any problems in this contest. :(
•  » » first have decent knowledge of known algorithms, mathematics, number theory and probability. Then solve past problems. The last one is necessary
 » 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?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Yes.. It depends.. That is why we have to store those values in dp array.You can see this here-> 117723683
 » Well put-together editorial!
 »
 » Thanks for B.
 » Can anybody explain what is wrong in my solution for problem C1 div2(https://codeforces.com/contest/1526/submission/117651697)
•  » » 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.
•  » » » 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 !!
 » Vote if you hate 1111 too :(
 » 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)
•  » » 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...
•  » » » Yes. I also believe this is the worst possible solution.Btw, Can you please suggest some resources to get more ideas and more problems like problem B?
 » C1 was easier than B for me even though I wasn't able to solve both
•  » » Brother can you please tell what is the error in my solution for C1(https://codeforces.com/contest/1526/submission/117651697).
•  » » » 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());
•  » » » » Thank you I feel so bad now that I realize it :(
 » 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<
•  » » Put the code in the spoiler tag, it's annoying
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   What is spoiler tag? I don't know can you tell me about this?
•  » » » » 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.
•  » » You Used Map that is a problem because it will also add up to the time complexity i.e when you did dp.find() in between and also time limit is 1 sec so your code will not satisfy the constraints properly.
•  » » » Then what should I use instead of map because sum will be in very high range.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Your Complexity is O(N*log2(size of map)*H), H is the number of all possible sum can be created in array which is very large
 » 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.
•  » » This is exactly what I thought during the contest.
•  » » Can you please explain how your solution works?I mean the idea behind this solution. Thanks.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   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
•  » » » » 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.
•  » » » » » $(x*11 + 1*111) = 1 \mod 11$$(x*11 + 2*111) = 2 \mod 11$$(x*11 + 3*111) = 3 \mod 11$...
•  » » » » » » ok thanks
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 4 →   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; } 
•  » » Got the exact same relation during contest after multiple attempts.
 » Alternate solution to A: You can just sort the array and swap all elements by 1 on right except first and last elements
 » I tried problem B with Dynamic programming but couldn't solve it because of that high constraint. After the contest, I was just shocked to see the solution. Can anyone suggest me of any resource to improve myself in this numerical observation like 11,111?
 » Spoilermt19937 rng(177013); Oh no
 » 3 weeks ago, # | ← Rev. 2 →   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<
•  » » 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.
 » 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?
•  » » dp = 0
 » Love the way "You write editorial".
 » 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!
 » wtf is Chicken McNugget and why on earth should one even know this sht????
•  » » 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).
•  » » » 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.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   I wasn't able to solve it either, but I think it's a theorem that one should certainly be aware of, (like people know about Extended Euclidean algorithm). Anyways, as the editorial has mentioned, this theorem was not the only method to solve it, the other one was pure observation, and looking at the constraints (only 10^4 test cases), it hinted that some kind of brute-forcing was required. I think this perfectly fits Div2 B difficulty.
 » 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?
 » How to solve C using dp ,please explain.
•  » »
•  » » 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 :))))
•  » » » 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?
•  » » » » 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.
 » 3 weeks ago, # | ← Rev. 11 →   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]
•  » » Put your codes in spoiler, please!
•  » » » Oh, I am so sorry, I don't know much about that.
 » 3 weeks ago, # | ← Rev. 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.
•  » » Actually you only need to check if it is non-negative.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Can anyone plz elaborate why 11*10 + 1 ensures that we can take value of a2 as x % 11 ?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   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
•  » » » » oooh nice. Thanks.
•  » » Hey, thanks for the solution but could you also 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#include using namespace std; #define ll long long int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ int x; cin>>x; bool flag= false; int i=0; while(true){ if((x - 11*i)<0){ break; } else if((x - 11*i)%111 == 0 or (x - 111*i)%11 == 0){ flag= true; break; } i+=1; } if(flag) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 0; } 
 » Anton lived today, but I'll get him next time for sure.
 » Thanks for providing method 2 with Chicken McNugget Theorem in solution B.
 » 3 weeks ago, # | ← Rev. 2 →   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; } 
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Priority queue works faster than multiset, except for that they don't differ.
•  » » » and, priority queues don't have iterators afaik
•  » » » » I meant in problem C.
•  » » I used segment tree with min() merge function! Your solution is much nicer though.
•  » » » Please can you explain the segment tree aproach?The editorial was a bit difficult for me to understand.Thanks in advance.
•  » » » » 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.
•  » » » » » Thanks a lot .I think I got the basic idea.
 » 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"
 » Great round, Thank you :)
 » 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.
 » memesforces.
 » Can anyone provide code/ intuition for the Merge Sort approach for bugaboo D?
•  » » 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 .
•  » » » What's PBDS?
•  » » » » policy based data structures I guess
•  » » » What was the intuition behind the elements would be together? @dhruv7888
•  » » 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)
 » 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.
•  » » 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.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   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 :)
 » Can someone explain question B in very simple language to someone who suck at Cp..
•  » » 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").
•  » » » Thanks a lot for this one! 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#include using namespace std; #define ll long long int main(){ ios::sync_with_stdio(0); cin.tie(0); int t; cin>>t; while(t--){ int x; cin>>x; bool flag= false; int i=0; while(true){ if((x - 11*i)<0){ break; } else if((x - 11*i)%111 == 0 or (x - 111*i)%11 == 0){ flag= true; break; } i+=1; } if(flag) cout<<"YES"<<"\n"; else cout<<"NO"<<"\n"; } return 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?
 » Problem C1 easy version: how ro solve this provlem using 1D dp
•  » » 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]
•  » » » Can you explain a bit more why are you defining dp[i] as the "Maximum Health"?
•  » » » » 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.
 » //Snowflakes are fluttering and the north wind screams //The world is vast
 » segment tree in Div2 C seriously?
•  » » 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 ).
•  » » » However, using a range add range max lazy propagation segment tree, we can check if a certain potion can be drunk without dying
•  » » » » Yeah I did the same :)
 » 3 weeks ago, # | ← Rev. 2 →   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
 » There is a little difference of alphabet between D and editorial. It looks like DNAs initially and you modified it for your outstanding coordinator.
 » Really enjoyed going through the hints before the actual solutions, it was a nice touch!
 » 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 ;)
 » 3 weeks ago, # | ← Rev. 3 →   Is the name Anton came from Silicon Valley series? •  » » nope, its name of coordinator that reject a lot of problems
 » Can someone explain how they got the intuition for placing the same letters together in D?
 » Thanks a lot
 » C1 Portions easy version: how to solve this question using top down dp .Please, Provide code also
•  » » Here is the code https://codeforces.com/contest/1526/submission/117767850 Feel free to ask for any further explanation
 » Problem B was really nice and loved the editorial and the way solutions are given to the problems. Kudos to writers and testers!!
 » I loved I Hate 1111
 » 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 ?
•  » » Read about Extended Euclidian and Linear Diophantine. CP-ALGO
 » 111
 » can someone please explain the dp approach of c1
 » 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.
 » 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...
 » Can anyone share DP solution for problem 3?
•  » » see submissions of different peoples'. u might find one. ;)
•  » » You can see my submission it's pretty messy though since it's a recursive code.
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   Hey sayan_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.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   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
•  » » » » » The Priority Queue one, I understood before. Thanks for the recursive Code, I was trying to do it using DP now.
 » guys what i did was in problem b,that sorted the digits of the number if the number was equal to the original one and its last two digits were equal then yes otherwise no.please help me.
•  » » Try this 54321
 » 3 weeks ago, # | ← Rev. 3 →   Code Golf for Question B 117721466
 » why tag dp for problem B ? is there a dp soln too?
•  » » Here is a dp solution for method2 117718666
•  » » » But isn't this solution based the deduction that only 11, 111 are required
•  » »
 » can anyone share solution of problem c using dp( by o(n2) approach ),shown in first method in editorial ???
 » 3 weeks ago, # | ← Rev. 7 →   //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<
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   Can AnyOne Help me with this TLE.??
•  » » » Seems like you can use a vector, instead of using a map. So something like — vector> cache(n+1, vector(n+1, -1)).
 » after reading each problem in this round i felt like "no one come up with this problem before, really?", especially for problem E
•  » » it's not a good or bad, it's just a fact :)
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   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.
 » 126B - Password i am using this code :- for i in range(int(input())) : num = int(input()) for j in range(len(str(num))+1,1,-1) : sum = int(str(1)*j) n = num//sum num = num - sum*n if num == 0 : print("YES") else : print("NO") why it is not running on pretest 2 it passed the pre-test 1
 » Thank u
 » 117723739 Can someone please help. I am new on codeforces. Why my code isn't working for PROBLEM B
 » My solution for B has been "uphacked". But as far as I know we already got our ratings updated for this contest. Can anyone tell me, will there be any change in my ratings because of this "successful hacking attempt"?
 » 3 weeks ago, # | ← Rev. 2 →   Problem B be like: Read the name of the problem ;) Sometimes, Name also tells the intuition behind the problem. ;)
 » Another approach for B, as 111=11*10+1if the below condition satisfies, its YES11*a+1*b=n and a>=b*10;
 » » Good contest ! But problem B could have been better . Too much observations for a B problem !
 » 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
•  » » 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
•  » » » I got it. Thank you for clarification
 » 3 weeks ago, # | ← Rev. 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?
 » What is the number which can not be created by 11 and 111 in range [1000, 1099], I've thought it only need >= 1000 to be always correct during the contest :( .
 » could anyone explain the proof of problem-c greedy?
•  » » Maybe this example will help you. 4 -3 -1 -1 -1
 » Can anyone tell why problemset name is changed to bugabooset?
 » 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?
•  » » 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.
•  » » » Thanks. Now I see it. They even bolded it.
 » What is WLOG here, in the proof of D. Since D1+D2≥0, either D1≥0 or D2≥0. WLOG, D1≥0.
•  » » 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.
 » 2 weeks ago, # | ← Rev. 2 →   Sorry...
 » Can someone explain me the python code ?
 » This can also be seen as an efficient way to to transition from one layer of the dp table to the next.any ideas/submissions for 1526C2 using dp optimizations?
 » 2 weeks ago, # | ← Rev. 3 →   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 :)
 » Just done up-solving and am so mad at myself for not giving this wonderful contest :)
»
2 weeks ago, # |
Rev. 3

Code Golf for problem C :)

//BitWiseOperatoR

# include <bits/stdc++.h>

using namespace std;

int main(){ ios::sync_with_stdio(NULL); cin.tie(0);

long long sum=0,cnt=0,x,n;
cin>>n;

multiset<long long> tmp;

for(int i=1; i <= n; ++i){
cin>>x;
sum+=x;

if(x<0)tmp.insert(x);

if(sum<0){
auto it = tmp.begin();
sum+=abs(*it);
tmp.erase(it);
}
else cnt++;

}

cout << cnt;

return 0;


}

 » 2 weeks ago, # | ← Rev. 2 →   Submission Link for A: Mean Inequality, This solution gave a TLE but this was accepted. All I did was declare the array after taking input of the size of the array, how is that causing a TLE?
 » how we can prove that every no. grater than 1111 can be formed by only using 111 and 11?please help !Thanks in advance: )
 » 1526B - I Hate 1111 Can someone give the solution code using method 1 in the B problem?
•  » »
 » 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}$
•  » » 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?
 » Hello Everyone! Can anyone help me in understanding to how to memoize my recursive solution, I tried very hard to do it, but could not find a way! Any help would be much appreciated. Thanks Link to my recursive solution (which is giving TLE) :-(https://codeforces.com/contest/1526/submission/117816251)
 » The problems are really nice and the tutorial is clear to understand, but I still have question in problem F, that is, why there are at most two candidates for element 2 after we've found element 1? (or for element n-1 after we've found n)Sincerely thanks again!
•  » » Thanks again, I've solved this problem, which means the maximum appears when asking $(a,b,1)$ or $(a,b,n)$, so we just need to store each number and the return value when asking it, then we found the maximum $mx$ and the candidates appears in $mx-1$
 » For problem C1, if one is at position 'i' with 'j' potions drunk, does it define an unique state? One could have different health points at the same 'i' and 'j' which will play a role in further computation, isn't it?
•  » » Yeah, even I thought it should be dp[i][health points till now] but couldn't implement due to high constraints on health.
 » what's wrong with my Dp solution of c1: code : https://codeforces.com/contest/1526/submission/117828172
 »
 » 2 weeks ago, # | ← Rev. 2 →   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?
•  » » Maybe this example will help you. 4 -3 -1 -1 -1
•  » » https://www.youtube.com/watch?v=zf9G9x9bs9c&t=2319s this may help
 » can someone please give a easy mathematical proof for problem d.For me the proof given is a bit difficult to understand.
•  » » 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. •  » » » THANK YOU VERY MUCH NOW I UNDERSTOOD.THANKS A LOT AGAIN
 » 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.
 » Can C1. Potions (Easy Version) be solved using Top-Down DP?
•  » » did it just now .. you can check my submission here ... 118020188
 » ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); can anyone explain what these means?
 » Anyone who understood C2 using DP / SegTree given in editorial ? .... , It will be great help if it can explained in simpler words...Anyone?
 » 2 weeks ago, # | ← Rev. 2 →   In problem B I wrote the code almost like the code provided. But still get wrong answer.Could you tell me why? thanks in advance cpp #include #include #include using namespace std; int main() { int n, jud; long long x; cin >> n; while (n--) { cin >> x; x = x % (111 * 11); jud = 0; for (; ; ) { if (x % 11 == 0 || x % 111 == 0 ) { jud = 1; break; } x -= 111; if (x < 0) break; } if (jud == 1) { cout << "YES" << endl; } else cout << "NO" << endl; } } `
 » 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 :)
 » 2 weeks ago, # | ← Rev. 2 →   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!!
•  » » No problem I think.
 » DP solution for C1: https://codeforces.com/contest/1526/submission/118098987
 » I Have a doubt. Is the second test case for Potions valid? Since they asked for maximum number of potions you can drink without making health negative we can choose 3,3,0,-1,-1,-2 and that would be 6 potions But the answer is 5 Can someone clarify ? Did i perceive the question incorrectly?
 » Hi! can someone please explain the logic of problem D, please? I'm not able to approach the problem right.
•  » » 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
•  » » » 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)
•  » » » » It's $O(24Nlog(N))$ where $N$ is the length of the input string.
 » what is the intuition behind problem D's solution or how did people came up their idea ?
 » can anybody share the solution of easy version of potion with dp?
 » 13 days ago, # | ← Rev. 2 →   In Problem C Method-3 I get the solution that replacing the most negative element in the priority queue with less negative yields an optimal solution. But, I don't understand what are they trying to prove later in the explanation. In short, I don't understand the proof and also I very badly want to know that as It will help me proving other things better and also I will enjoy the proof. So, please anyone explain to me the proof that is mentioned there. Your efforts will be highly appreciated.
 » 13 days ago, # | ← Rev. 2 →   What is wrong with my approach for problem C, I sorted the array in non-ascending order and counted till the sum of values is less than 0. Anyone, please let me know.
 » potions easyversion....dp method...isnt it wrong?...we need the max potions possible
 » 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
•  » » Good catch!The editorial has been updated with a (hopefully) correct proof now :)
•  » » » 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:)