errorgorn's blog

By errorgorn, history, 3 weeks 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
  • +191
  • Vote: I do not like it

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

ERRORGORN OFZ

»
3 weeks 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 weeks ago, # |
  Vote: I like it +92 Vote: I do not like it

When the problemsetters have plans for the night: lol
Source: 1526B - I Hate 1111

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

speedforces :)

  • »
    »
    3 weeks 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 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      He is talking about how fast the editorial came.

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

I seriously hate 1111 after this contest.

  • »
    »
    3 weeks 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 weeks 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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        good job :)

      • »
        »
        »
        »
        3 weeks 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

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

          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

          Logic
        • »
          »
          »
          »
          »
          38 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          bro please give me itterative dp solution if possible

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

    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.

»
3 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is going to take a lot of time.

      • »
        »
        »
        »
        3 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +98 Vote: I do not like it
All numbers other than 11 and 111 are useless.

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

i've never seen so many memes in 1 editorial

»
3 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    +1

  • »
    »
    3 weeks 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 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Why not?

    • »
      »
      »
      3 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the early tutorial!

»
3 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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!

      Code
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        seems fine to me is it giving WA or TLE?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          WA, if I remove (x — 111*i)%11 == 0) condition from the if statement, it gives AC. Why so though?

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But you are using or condition it should not have happen may be a bug!!

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

      Understood, thanks guys

  • »
    »
    2 weeks 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 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

will this be the fastest editorial of all time?

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

    Yes.. It depends.. That is why we have to store those values in dp array.You can see this here-> 117723683

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

Well put-together editorial!

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

Thanks for B.

»
3 weeks 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 weeks 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.

    • »
      »
      »
      2 weeks 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 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Vote if you hate 1111 too :(

»
3 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
3 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      3 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      Then what should I use instead of map because sum will be in very high range.

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

    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

»
3 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is exactly what I thought during the contest.

  • »
    »
    3 weeks 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 weeks 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 weeks 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 weeks 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$$$

          ...

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

            ok thanks

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

            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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Got the exact same relation during contest after multiple attempts.

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

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?

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

Oh no

»
3 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Love the way "You write editorial".

»
3 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
        Rev. 2   Vote: I like it -6 Vote: I do not like it

        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.

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

How to solve C using dp ,please explain.

  • »
    »
    2 weeks 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 :))))

    • »
      »
      »
      2 weeks 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?

      • »
        »
        »
        »
        2 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    3 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
3 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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.

      • »
        »
        »
        »
        2 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

Great round, Thank you :)

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

memesforces.

»
3 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

//Snowflakes are fluttering and the north wind screams //The world is vast

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

segment tree in Div2 C seriously?

  • »
    »
    3 weeks 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 weeks 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 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really enjoyed going through the hints before the actual solutions, it was a nice touch!

»
3 weeks 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 weeks 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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

Thanks a lot

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

C1 Portions easy version: how to solve this question using top down dp .Please, Provide code also

»
3 weeks 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 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

I loved I Hate 1111

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

111

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

can someone please explain the dp approach of c1

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

Can anyone share DP solution for problem 3?

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

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.

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

Code Golf for Question B 117721466

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

can anyone share solution of problem c using dp( by o(n2) approach ),shown in first method in editorial ???

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

    Can AnyOne Help me with this TLE.??

    • »
      »
      »
      3 weeks 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 weeks 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 weeks 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 weeks 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 - 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.

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

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

Thank u

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

117723739 Can someone please help. I am new on codeforces. Why my code isn't working for PROBLEM B

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

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

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

Good contest ! But problem B could have been better . Too much observations for a B problem !

»
3 weeks 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

  • »
    »
    2 weeks 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 weeks 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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

could anyone explain the proof of problem-c greedy?

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

Can anyone tell why problemset name is changed to bugabooset?

»
2 weeks 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?

  • »
    »
    2 weeks 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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Now I see it. They even bolded it.

»
2 weeks 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.

  • »
    »
    2 weeks 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.

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

Sorry...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the python code ?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just done up-solving and am so mad at myself for not giving this wonderful contest :)

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

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

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?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how we can prove that every no. grater than 1111 can be formed by only using 111 and 11?

please help !

Thanks in advance: )

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1526B - I Hate 1111 Can someone give the solution code using method 1 in the B problem?

»
2 weeks 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}$$$

  • »
    »
    2 days 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?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, even I thought it should be dp[i][health points till now] but couldn't implement due to high constraints on health.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what's wrong with my Dp solution of c1: code : https://codeforces.com/contest/1526/submission/117828172

»
2 weeks 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?

»
2 weeks 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.

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 weeks 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.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); can anyone explain what these means?

»
2 weeks 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?

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

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 <iostream>
#include <algorithm>
#include <cmath>
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;
	}

}
»
2 weeks 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 :)

»
2 weeks 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!!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 weeks 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.

  • »
    »
    2 weeks 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

    • »
      »
      »
      2 weeks 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)

      • »
        »
        »
        »
        2 weeks 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.

»
13 days 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 ?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody share the solution of easy version of potion with dp?

»
13 days 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.

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

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.

Solution : https://codeforces.com/contest/1526/submission/118239202

»
9 days 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

»
4 days 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.

  • »
    »
    4 days 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 :)

    • »
      »
      »
      4 days 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:)