errorgorn's blog

By errorgorn, history, 3 years ago, In English

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
  • Vote: I like it
  • +199
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

ERRORGORN OFZ

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I wish they were BUGABOO's so that I can solve them.

QUESTIONS are really hard to ANSWER :")

»
3 years ago, # |
  Vote: I like it +92 Vote: I do not like it

When the problemsetters have plans for the night: lol
Source: 1526B - Я ненавижу 1111

»
3 years ago, # |
  Vote: I like it -34 Vote: I do not like it

speedforces :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    It was more about how fast you come to solution and not how fast you type. Code for first 4 tasks were short.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      He is talking about how fast the editorial came.

»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I seriously hate 1111 after this contest.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I even tried Dynamic programming for multiple times. But the constrain of 10^9 killed me badly :(

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        good job :)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Did not see solution to A.

Edit: Which is a shame because I solved B and and both C correctly.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually I thought about that, but was not able to aproximate the probability that it works.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is going to take a lot of time.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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...,n

        Consider 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it +98 Vote: I do not like it
All numbers other than 11 and 111 are useless.

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

despite bricking the round, i enjoyed it. thanks for the amazing round!

»
3 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Thanks the authurs for nice bugaboos statements and detail + quick solutions for those bugaboos

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i've never seen so many memes in 1 editorial

»
3 years ago, # |
  Vote: I like it -24 Vote: I do not like it

i know everyone will downvote this but problem 2 is such a bad problem. CP problems should never be based one single tricky clue

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Why not?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it -11 Vote: I do not like it

      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 problems

      Anyways that’s just my opinion. Feel free to ignore

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Your opinion based only on solution in editorial? There are more others solutions with easy logic.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone explain why in 2nd problem only 11 and 111 are useful. Thanks :|

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

will this be the fastest editorial of all time?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

I used random shuffle until the array is good :( (problem A)

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Pls tell me how to improve my skills! I couldn't solve any problems in this contest. :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    first have decent knowledge of known algorithms, mathematics, number theory and probability. Then solve past problems. The last one is necessary

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Well put-together editorial!

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for B.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain what is wrong in my solution for problem C1 div2(https://codeforces.com/contest/1526/submission/117651697)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    Spoiler
    Solution

    I hope you understand this simple issue with your code.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 !!

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Vote if you hate 1111 too :(

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C1 was easier than B for me even though I wasn't able to solve both

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like 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 <bits/stdc++.h>
using namespace std;
#define ll long long int
 
vector<ll> v;
ll n;
map<pair<ll,ll>,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<n;i++)
	{
	    ll x;
	    cin>>x;
	    v.push_back(x);
	}
	cout<<max(fun(0,0)-1,0ll);
	return 0;
}

Thanks in Advance :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Put the code in the spoiler tag, it's annoying

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What is spoiler tag? I don't know can you tell me about this?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how your solution works?

    I mean the idea behind this solution. Thanks.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          $$$(x*11 + 1*111) = 1 \mod 11$$$

          $$$(x*11 + 2*111) = 2 \mod 11$$$

          $$$(x*11 + 3*111) = 3 \mod 11$$$

          ...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    is  this true for any eqn like ax + by = n
    if x<y 
    (a+b*k)*x + bd = n
    if n>= bd*y then we can write ax + by =n
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternate solution to A: You can just sort the array and swap all elements by 1 on right except first and last elements

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Spoiler

Oh no

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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<int> v(n);
	vector<int> ne;
	int ans=0;
	int count = 0;
	for(int i=0;i<n;i++){
		cin>>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<len;i++){
		count -=ne[i];
		if(count>=0){
			ans++;
		}else{
			break;
		}
	}
	cout<<ans<<endl;
  return 0;
}
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 case

    1 -2 1000

    if 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Love the way "You write editorial".

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

wtf is Chicken McNugget and why on earth should one even know this sht????

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using dp ,please explain.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :))))

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
Rev. 11   Vote: I like it -31 Vote: I do not like it

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

`[contest:723][problem:B]

»
3 years ago, # |
Rev. 5   Vote: I like it +5 Vote: I do not like it

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 % 11

Then we can check if x - a2*111 is non-negative and divisible by 11.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Actually you only need to check if it is non-negative.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can anyone plz elaborate why 11*10 + 1 ensures that we can take value of a2 as x % 11 ?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Anton lived today, but I'll get him next time for sure.

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Thanks for providing method 2 with Chicken McNugget Theorem in solution B.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I used multiset in C1 and C2 instead of priority queue

code
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Priority queue works faster than multiset, except for that they don't differ.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      and, priority queues don't have iterators afaik

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I used segment tree with min() merge function! Your solution is much nicer though.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please can you explain the segment tree aproach?The editorial was a bit difficult for me to understand.Thanks in advance.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot .I think I got the basic idea.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have some questions regarding the proof of D.

  1. What is D1 and D2 ?
  1. Could you pls elaborate the equation and the next line "upto a contradiction"
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

memesforces.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone provide code/ intuition for the Merge Sort approach for bugaboo D?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain question B in very simple language to someone who suck at Cp..

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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").

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C1 easy version: how ro solve this provlem using 1D dp

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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]

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain a bit more why are you defining dp[i] as the "Maximum Health"?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        submission.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

segment tree in Div2 C seriously?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 ).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      However, using a range add range max lazy propagation segment tree, we can check if a certain potion can be drunk without dying

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There is a little difference of alphabet between D and editorial. It looks like DNAs initially and you modified it for your outstanding coordinator.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 + b

now 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/117617666

Hope it helps ;)

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Is the name Anton came from Silicon Valley series?

 Silicon Valley

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nope, its name of coordinator that reject a lot of problems

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain how they got the intuition for placing the same letters together in D?

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B was really nice and loved the editorial and the way solutions are given to the problems. Kudos to writers and testers!!

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I loved I Hate 1111

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 = 23

Here 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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share DP solution for problem 3?

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Code Golf for Question B 117721466

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why tag dp for problem B ? is there a dp soln too?

»
3 years ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

//PROBLEM C EASY VERSION

//GOT TLE USING MAP **** //USE MAP BECAUSE I WANT TO STORE ARRAY ELEMENTS WHICH IS NOT POSSIBLE IN 2D DP

map<pair<int, int>, int> dp;

//USE MAP PAIR FOR INDEX AND SUM OF ELEMENTS OF ARRAY

// AND STORE THE COUNT OF POTIONS

int 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<<helper(arr, 0, 0, 0,n);

} signed main(){

solve();

}

//PLEASE HELP TO OPTIMIZE THIS CODE USING TOP DOWN DP **** //THEN I TRY THIS SOLUTION BY BUT THIS GIVES WRONG ANSWER **** // I DON'T KNOW HOW TO STORE LARGE VALUES IN 2D DP ****

int dp[2001][2001];

int helper(int arr[], int i, int sum,int cnt,int n){

if(i == n){
    return cnt;
}


if(dp[i][sum] != -1){

    return dp[i][sum];
}

if((sum + arr[i]) < 0){

    return helper(arr,i+1,sum,cnt,n);

}
int inc = helper(arr, i+1, sum + arr[i], cnt+1,n);

int exc = helper(arr, i+1,sum, cnt,n);

return dp[i][sum] = max(inc,exc);

} void solve(){

r(n);
memset(dp,-1,sizeof(dp));

int arr[n];

for(int i = 0;i < n; i++)cin>>arr[i];

cout<<helper(arr, 0, 0, 0,n);

} signed main(){

fast; 

solve();

// r(t); while(t--){    solve();nl;}

}

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can AnyOne Help me with this TLE.??

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems like you can use a vector, instead of using a map. So something like — vector<vector<long long>> cache(n+1, vector<int>(n+1, -1)).

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

after reading each problem in this round i felt like "no one come up with this problem before, really?", especially for problem E

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's not a good or bad, it's just a fact :)

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +27 Vote: I do not like it

      yea the way i usually set problems is taking existing problems and twisting them.

      B: I looked at 1517A - Сумма 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.

»
3 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Problem B be like: Read the name of the problem ;) Sometimes, Name also tells the intuition behind the problem. ;)

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Another approach for B, as 111=11*10+1

if the below condition satisfies, its YES

11*a+1*b=n and a>=b*10;

code : https://codeforces.com/contest/1526/submission/117686801

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why problemset name is changed to bugabooset?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is WLOG here, in the proof of D.

Since D1+D2≥0, either D1≥0 or D2≥0. WLOG, D1≥0.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Sorry...

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1526B - Я ненавижу 1111 Can someone give the solution code using method 1 in the B problem?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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}$$$

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can someone please give a easy mathematical proof for problem d.For me the proof given is a bit difficult to understand.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    Codeforces-Round-723-Div-2-Editorial-Codeforces-Google-Chrome-30-05-2021-19-18-51-2

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      THANK YOU VERY MUCH NOW I UNDERSTOOD.THANKS A LOT AGAIN

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C1. Potions (Easy Version) be solved using Top-Down DP?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone who understood C2 using DP / SegTree given in editorial ? .... , It will be great help if it can explained in simpler words...Anyone?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have O(1) general solution for problem B (div2). Please find submission at: https://codeforces.com/contest/1526/submission/118087579

I have tried to capture the logic in the image attached. Here

Please let me know if you find error in the solution. Thanks!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! can someone please explain the logic of problem D, please? I'm not able to approach the problem right.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's $$$O(24Nlog(N))$$$ where $$$N$$$ is the length of the input string.

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

what is the intuition behind problem D's solution or how did people came up their idea ?

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

potions easyversion....dp method...isnt it wrong?...we need the max potions possible

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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<pb<pc" was our assumption, so there's not a range for "a", in my opinion.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Good catch!

    The editorial has been updated with a (hopefully) correct proof now :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain c2 greedy 1 solution. i couldnt understand the editorial

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why sorting (in decending) not working in problem C.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because you can't change the order of potions.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the solution for problem E, the last step is calculating screenshot

However, in the solution(python), it says k-cnt+n-1 choose n

My result is also n+k-cnt-1, and my submission is accepted https://codeforces.com/contest/1526/submission/122438057

Is there a typo, or I missed something?

Thank you!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why it is enough to brute force just 20 times and how to prove that all values greater than 1099 are always true