By pikmike, history, 4 months ago, translation, In English

Hello Codeforces!

On Jul/29/2020 17:35 (Moscow time) Educational Codeforces Round 92 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hey Codeforces!

We hope you’ve been doing well these past couples of weeks.

This week, we wanted to share a blog post about two of our students. As you might know, Harbour.Space has a unique approach to education — besides classwork and exams, we encourage our students to develop their skills with hands-on projects or even create their startups, so that they’re ready for the workforce when they graduate.

That’s exactly what Jonathan and Khaled, two of our Data Science students, did.

After working hard on their Machine Learning-based startup, they were selected by the European Organization for Nuclear Research (CERN) for a 5 Week Student Entrepreneurship Programme, and are now preparing to travel to Geneva in October. We summarized the story of how they went from data scientists to startup founders in this article.

We hope it inspires you to pursue your passions, and work collaboratively to improve the world for those around you.

Good luck on your round, and see you next time!

Read article→
Rank Competitor Problems Solved Penalty
1 Um_nik 7 245
2 I_love_chickpea 7 255
3 kefaa2 7 267
4 Egor 7 293
5 Farhod_Farmon 7 364

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Joney 20:-2
2 applese 19:-1
3 FelixArg 7:-2
4 liouzhou_101 10:-10
116 successful hacks and 492 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A noimi 0:00
B noimi 0:05
C Ari 0:04
D HanaYukii 0:17
E kefaa2 0:22
F nitixkrai 0:23
G MyK_00L 1:05

UPD: Editorial is out

 
 
 
 
  • Vote: I like it
  • +413
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +165 Vote: I do not like it

Random Guy: *complains about previous contest in comments*

CF-Community: So,you have chosen death?!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -68 Vote: I do not like it

    That's why CF comment section and its community sucks

»
4 months ago, # |
  Vote: I like it +106 Vote: I do not like it

not gonna lie, this comment section is already sh*t.

»
4 months ago, # |
  Vote: I like it -66 Vote: I do not like it

If govt. was the CF community and the people who posted a comment were protesters.

»
4 months ago, # |
  Vote: I like it -74 Vote: I do not like it

What if someone says that this round is harder than the previous one? Would everyone quit giving it? That depends on us the participants how the round is. And this website is a source of giving us the idea in which topic you lag behind. So lets find and give every round a full shot as if its only created for you. Lets enjoy the process!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Simply,it's not for Russian 5th to 8th grade student anymore.

»
4 months ago, # |
  Vote: I like it -60 Vote: I do not like it

i hope to find nice problem , and have fun , because i haven't participate in any contest from along time

»
4 months ago, # |
Rev. 3   Vote: I like it -40 Vote: I do not like it

People in comment section are hiding own weakness by giving other blame.

»
4 months ago, # |
Rev. 3   Vote: I like it -98 Vote: I do not like it

mynameJEFF

»
4 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Is m2.codeforces.com not working?

»
4 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Summary of this blog comment section: The comment is hidden because of too negative feedback, click here to view it.

Downvote is coming :)

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Screenshot_20200729_205651_com.whatsapp2.jpg

»
4 months ago, # |
  Vote: I like it -33 Vote: I do not like it

My stupid WA on C took expert from me :'(

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    C: I wasn't able to figure out the solution. Help

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Notice that each good string either consists of all the same character or has even length and is alternating characters (e.g. 0101). Then you can just bruteforce the two alternating characters and the single characters.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't know why I get demotivated. Please help me with B and C after the contest

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

    In problem C you should make string like this 11111 eg make all digits same or 202020 make string of even length where used only two distinct digits and no adjacent digits same

  • »
    »
    4 months ago, # ^ |
    Rev. 9   Vote: I like it +1 Vote: I do not like it

    while doing paper work you observe that the only way to minimize the number of deletion and to make string good ..we have only three cases case 1->all character are same..(for that you just check the maximum frequency element and for number of deletion you just subtract with the length i.e number_of_deletion_required_to_make_all_character_string_equal =string.length()- max_frequency_element) case 2-> see the alternative character.. for that you have to find the a pair in [0 to 9] for which you make maximum length of of alternative character string .. observe that length greater than or equal to (>=)4 is beneficial for ous ..i simply mean this--> if (max_alt_len >= 4) { if (max_alt_len % 2 == 1) { max_alt_len = max_alt_len — 1; } alternate_deltion_requi = str.length() — max_alt_len; } case 3-> you have only 2 characters i.e number of deletion = string.length()-2; and then you have to take the minimum of all cases . please see the code for better understanding :) click here to see the implementation

»
4 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Tbh, E was easier than B

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share your approach?

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

      Basically, you have to find the number of pairs (x, y), 1 <= x < y <= min(m, d) such that (y — x) * (d — 1) = 0 (mod w). So, just make w = w / gcd(w, d — 1) and you get to: y — x = 0(mod w). Go through all differences d, such that d % w = 0, and you see that there are n — d possible pairs (x, x + d). From now on, it's obvious.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    I still don't understand how can they do the same mistake for 3 contests in quick succession. Really disappointed.

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

    Agree.(but someone working hard on B didn't even read the question of E)

»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

The order of problem B and C should be exchanged.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

In problem E, Basically we have to found the number of pairs such that

(x + d * y) % w == (y + d * x) % w

How will we reduce this expression?

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

    (y — x) * (d — 1) = 0 (mod w)

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

    Just reduce it to the no of i, j such that j > i and j — i is divisible by w / gcd(d — 1, w). You get a simple expression for the ans as Ans = sum_(k = 0 to (min(d, m)) — 1) floor(k / w') where w' = w / __gcd(d — 1, w) which can be obtained in O(1) by floor constraining.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if d == 0 -> answer = 0 else rearrange the expression to obtain (y-x)(d-1) == 0 mod w meaning the w divides this product, if g = gcd(w, d-1), then w/g must divide y-x also x < y < min(d, m), let L = min(d, m) and k = w/g and t = floor(L/k) then the answer is sum L — k*i where i*k <= L which is equal to L*t — k*t*(t+1)/2

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x + d*y = y + d*x mod w implies (d-1)*(y-x) = 0 mod w, let g = gcd(d-1, w), then y = x mod(g/w), y > x, x <= min(m, d), y <= min(m, d) counting this is a standard problem.....

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    $$$ (y-x)*(d-1)modW =0$$$
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve F?

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

    Let each interval be a vertex in a bipartite graph, where an edge indicates that two intervals intersect. We want to find the size of a maximum independent set in this graph. By Kőnig's theorem, this is equal to $$$n$$$ minus the size of a maximum matching in this graph. So, the problem reduces to finding a maximum matching in which we pair up red and blue intervals which intersect.

    The condition for two intervals $$$x$$$ and $$$y$$$ intersecting is that $$$L_x\leq R_y$$$ and $$$L_y\leq R_x$$$. Now, let's assume that in this condition, $$$x$$$ is always blue and $$$y$$$ is always red. If we preprocess the input by replacing each blue interval $$$[L, R]\to[L, -R]$$$ and each red interval $$$[L, R]\to[R, -L]$$$, then the condition becomes $$$L_x\leq L_y$$$ and $$$R_x\leq R_y$$$, which is much cleaner.

    From now on, we can think of each interval $$$[L, R]$$$ as being a point in the plane at coordinates $$$(L, R)$$$. To construct the maximum matching, we scan the points in order of increasing $$$L$$$. When we encounter a blue point, we add it to a multiset to be picked up later. When we encounter a red point, we can match it with any blue point from the multiset whose $$$R$$$ value is $$$\leq$$$ than that of the red point. Blue points with smaller $$$R$$$ values are "better", since they can be picked up by more red points. So, it makes sense to greedily get the "worst" point out of the way by choosing the valid blue point with largest possible $$$R$$$ value.

    Short code: 88388914

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

      WoW, Nice interval transformation trick!. Thank you :)) Btw, do you know some problems in which this trick can be applied?

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

        No idea. I think it only applies to situations involving red/blue intervals intersecting. The resulting bipartite graphs have the property that the vertices on the left can be reordered such that each vertex on the right connects to a contiguous window of vertices on the left (and vice versa). A similar type of graph appeared in 1348F - Phoenix and Memory.

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

    I have an immature idea of dp solution for problem F. First do coord compression. define dp[len][lastcolor] as the answer of segmets until length len and last color is lastcolor.

    when we go to a new length with color lastcolor, we want to know at which point prevlen we choose to start the last color range that we can get the max answer. so we need to update an array b[prevlen]. when a new seg [l, len] with color lastcolor added, b[1, l] will all plus one, while b[l+1, len] will not change. and dp[len][lastcolor] = max(b[]) to update b[] efficiently, Segment tree with lazy propagation will be used.

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D?

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D ?

»
4 months ago, # |
Rev. 4   Vote: I like it -17 Vote: I do not like it

Can someone please tell me why this solution is wrong for C :

void solve(){
    string s;
    cin>>s;
    int n=sz(s);
    int ans=2e5;
    for(char a='0';a<='9';a++)
        for(char b='0';b<='9';b++){
                int turn=0,cnt=0;
            for(auto x:s){
                if(x==a && turn==0){
                    turn=(turn+1)%2;
                    cnt++;
                }
                else if(x==b && turn==1){
                    turn=(turn+1)%2;
                    cnt++;
                }
            }
            if(cnt%2==1)
                cnt--;
            ans=min(ans,n-cnt);
        }
        cout<<ans;
}

UPD :

if(cnt%2==1 && a!=b) 
   cnt--;
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I see many people solved $$$C$$$ without $$$DP$$$, how to do it without $$$DP$$$ ?

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    the final string should be of the form AAAAAAAA....AA or ABABAB......AB. Iterate over all possible A and B

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

      Sire, would this work: str1= leftshift(s) and str2= rightshift(s2). Now we find the maximum number of equal characters in str1[i] and str2[i+2] and store it in a map. If the max number of equal chars is 0, then ans= s.size()-2, if max= s.size() ans= 0, else ans=s.size()-max. Please help me :(

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use the observation that in order to make a good string, either it has all the same characters such as "111111", or it has repeating pairs such as "121212". The minimum answer must be one of these two cases. There are 10 * 10 combinations that you need to check, each check takes O(N) time.

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

    The longest subsequence should be either xxxxxx or xyxyxy(even length). We can simply brute force for every 2 digits from 0 to 9 like 010101... or 020202 and find the length of the longest pattern present in the given string. And finally, take maximum of all of them. Complexity O(81*n).

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

      Can you clarify one thing pls! How many operations are allowed per second?? My knowledge was about 10^8 operation are allowed per second so considering that total operations in C will be 81*2*10^5. and the number of test cases will be 10^3 so per input, the operation should be > 10^8 so how come the solution is passing?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Read the question properly "It's guaranteed that the total length of strings doesn't exceed 2⋅(10^5)"

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        For all test cases It's guaranteed that the total length of strings doesn't exceed 2⋅105.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks . Also i think the time complexity of this approach is O(100*n)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly,I too got suprised by this.

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

    how to do it with dp?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's same solution except that I used dp to find longest subsequence of form xyxyxy..xy instead of simple greedy.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are only two form of the final string. aaaaa...(the length doesn't need to be even) or ababab...(the length must be even)

»
4 months ago, # |
  Vote: I like it +37 Vote: I do not like it

B was very uninteresting!! Rest problems were nice.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why? I thought it was fine for an educational round. Probably not too interesting for a regular round though.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    B was interesting, to me At least.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's for Russian 5th to 8th grade students , they think it's great , but not us.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice Contest.Thanks, CodeForces, for the contest...

Keep these good initiatives coming...

»
4 months ago, # |
  Vote: I like it +69 Vote: I do not like it

Whoever came up with input format for problem G, please don't do that again.

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

    Sorry, I realised that it would be better to give it as a weighted graph when the whole testset and all solutions were already prepared :(

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Spent all my time on B, and literally solved C one minute after the contest ended. I tried to solve C first, but my mind was so stuck on B , couldn't solve C unless I solved B. Took 1 hour to solve B. Gonna lose rating but enjoyed the contest.

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

    B took 1h, C took 7m for me :(

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      I submitted C just 1 min before the contest ended, and forgot one edge case when all are equal. Implemented it and the contest ended. By the way, you are in my friend list, saw you struggling with B, that's what gave me hope :p

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So why don't(or didn't?) you look at E?

      it took 1m for me.just simple maths

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        B took too long. I probably would've easily got it if I had more than 7m left after D.

»
4 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

[deleted]

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
ll rec(ll idx, ll moves, ll lmoves, vector<ll>& arr, vector<ll>& psum, vector< vector< vector<ll> > >& dp){
    if(moves == 0){
        return 0;
    }
    if(lmoves == 0){
        return psum[min(idx + moves,(ll)arr.size()-1)] - psum[idx];
    }
    if(dp[idx][moves][lmoves] != -1){
        return dp[idx][moves][lmoves];
    }
    ll ans = 0;
    if(idx + 1 < arr.size()){
        ll v1 = arr[idx+1] + rec(idx + 1,moves-1,lmoves,arr,psum,dp);
        ans = v1;
    }
    if(idx - 1 >= 0){
        ll v2 = arr[idx-1] + rec(idx - 1,moves-1,lmoves-1,arr,psum,dp);
        ans = max(ans,v2);
    }
    dp[idx][moves][lmoves] = ans;
    return ans;
}

How do I reduce space complexity of this DP solution for B ?

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

    Notice that the number of total moves left can be directly derived from the current index and the number of moves to the left. Just don't include the number of total moves left in the dp memo.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      int mx=0; vector<vector<vector>>dp; int rec(vector&a,int k,int z,int id,int f=1){

      if(k==0){
          return a[id];
      }
      if(dp[id][k][f]!=-1){
          return dp[id][k][f];
      }
      
      dp[id][k][f] = max(dp[id][k][f],a[id]+rec(a,k-1,z,id+1,0));
      if(f==0&&id>0&&z>0){
          dp[id][k][f] = max(dp[id][k][f],a[id]+rec(a,k-1,z-1,id-1,1));
      }
      mx = max(mx,dp[id][k][f]);
      return dp[id][k][f];

      } Can you please help me why it is giving MLE?The dp vector has id, k and flag f having size 2 for the 3rd dimension to check wheather i have taken left move in previous step or not.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler

        But it will give tle, as we are visiting states which are useless.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This code is not giving TLE.Also if I use without memoization it is giving correct answer on shorter test case but TLE on longer.

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

    moves = idx + 2 * lmoves

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks ! Got it Accepted !

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use map instead of 3d dp array it will be easy

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here, in this code how do you make sure that you don't go left twice or more times in a row?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm, that should be an issue here. I don't know why it passed all test cases.

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

      I believe that the case where we need to move left more than once consecutively won't arise.

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

      That was said in the problem statement, right?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (the answer is:not to use DP)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    see this comment

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

what's wrong with a solution for B that does the following:

take all M elements first and then for each i in m, remove the last element and add arr[i-1] then remove the new last element and add arr[i] and then arr[i-1] again and so on until we can't do any extra moves for K, and take the maximium answer.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you come up with this, I did brute force and it worked

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i just realized my mistake is that taking arr[i-1] and removing the last element only wouldnt work , i need to remove the last 2 elements and take arr[i] + arr[i-1].

      should work otherwise , but the logic behind it is that you should only go left for 1 element, you never go left for 2 different elements.

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

Problemset was better than previous contest. I enjoyed it :) . Today, B no. was interesting at first look. But most of us missed counter cases in first trial. C no. was easier than B.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I read the code of A. Why if( L * 2 <= R)? Why not use the LCM function? What is the key point of this problem?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    LCM(L,2*L) = 2*L and is the smallest LCM you can find in the interval

»
4 months ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Can anyone tell where I am wrong in C? I checked for max possible alternate (121212 type) and also for element with max frequency(eg 56555)

        string x;
    cin >> x;
            ll n=x.size();
    map<char, ll>m;
    map<ll, ll>odd;
    map<ll, ll>even;
    int flag = 1;
    for (int i = 0; i < x.size(); i++)
    {
       if (i % 2 == 0)
       {
         odd[x[i]]++;
       }
       else
       {
         even[x[i]]++;
       }
       m[x[i]]++;
       if (m[x[i]] == n)
       {
         cout << "0" << endl;
         flag = 0;
       }
    }
    ll maxele = 0;
    for (auto it = m.begin(); it != m.end(); it++)
    {
       maxele = max(it->second, maxele);
    }
    if (flag) {
       ll maxodd = 0, maxeven = 0;
       for (auto it = odd.begin(); it != odd.end(); it++)
       {
         maxodd = max(it->second, maxodd);
       }
       for (auto it = even.begin(); it != even.end(); it++)
       {
         maxeven = max(it->second, maxeven);
       }
       if (maxeven == n || maxodd == n)
       {
         cout << "0" << endl;
       }
       else
       {
         ll maxi = min(maxodd, maxeven) * 2;
         cout << min(x.size() - maxele, x.size() - maxi) << endl;
       }
    }
»
4 months ago, # |
  Vote: I like it +71 Vote: I do not like it

Problem B:

![ ](let-me-in.jpg)

»
4 months ago, # |
  Vote: I like it +106 Vote: I do not like it

Really, what goes through people's heads when they message others like this during the contest....

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

    is he a cm?

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

      Yes, and they've given enough contests that they should know better than to do this...

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

    Honestly participants shouldn't be allowed to send messages during contests.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell the logic behind D? I was trying to make the two ranges equal like assuming l1 < l2, r1 < l2, first make r2 = l2, and then try to increase it till r1, then decrease l2 to l1 and do this for all 'n' ranges....

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Best Educational Round EVER!!

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

Can anyone tell why this is giving TLE on test case 2 ( Problem B ) ? https://codeforces.com/contest/1389/submission/88360778 Thanks in advance

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Does D have a more elegant solution than lots of nested ifs?

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

    Maybe by using max and min functions cleverly.

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

      can You explain ??

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

        I can explain the three lines of the for loop. I think the rest should be obvious.

        We process pairs of segments one at a time.

        cur += max(0,l2-r1) Add the gap between the two segments to the current number of moves.

        f(r2-l1 - max(0,r1-l2)) Make the two segments of equal size. This requires $$$r_2 - l_1 - max(0, r_1 - l_2)$$$ moves and increases $$$I$$$ by this amount.

        ans = min(ans, cur+2*k) By using 2*k moves we can make $$$I$$$ the required size. Simply increase both segments by $$$k$$$.

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

      I see, you exploited the fact that n is limited by 10^5, so you can just check segments one by one in a loop. I went for O(1) per test case, though your solution less complicated.

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

What's wrong with my this solution for problem C ? Please provide any counter case .

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

I tried to solve problem B with 3d DP but I failed. The three states that I think needed are dp[number of moves done][whether the current element taken in forward move or backward][number of backward moves done] , also I used pair<int,int> dp to store the index where we are now. But still got the wrong answer, can anyone help me how to solve this problem B with DP using the states that I've used? Or if you have any 3d DP solution can you explain?

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

I am very demotivated... where is button to delete account?****

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

![ ](48ql4x.jpg)

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

Could Someone tell my mistake in B? This has happened to a lot of people in B (Test case 2 failed, 19th number differs). That very specific number. Some people figured it out. My submission is: 88310231

Thanks in advance!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try

    Test
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it. Thanks buddy!

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Even i have the same issue. Your text to link here... my submission. it is similar to yours. what is the issue with the 19th line?. please can u give a counter example

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          No idea. I fixed the above test case, my code had some issue. However my solution is still giving the exact same error as yours. Can't find the issue. Do let me know if you get the solution.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            12 11 5 1 2 9 8 1 1 1 1 1 1 9 9

            It fails here. The answer is 88. My answer is 44. Thank You

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

In D, why we converted al2,bl2 to 1,4 . we could have converted it to 2,4 in just one step making the intersection with al1,bl1 to be equal to 2. That would have given me the answer. Please help me if i am getting anything wrong??

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

B was like a hell... AGC B?

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

    No bro AGC(I hope u meant Atcoder Grand) is other level. Even last contest B was tougher than today's B.

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

Hints for B, please.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp[i][j][k] where i is current index, j is number of lefts and k is 0 or 1 depending on whether we reached i from left or right.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought of that approach but won't that give TLE ? $$$ 1 \leq i \leq n $$$ and $$$ 1\leq j \leq n-1$$$ right ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        j <= 5. See constraints of problem.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do bruteforce with any kind of optimizations

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For each value of left (0 <= left <= z) you can find the maximum score in $$$O(n)$$$ pretty easily. Then just take the max of all the scores.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can observe that for a given sequence, $$$1,5,4,3,2$$$

    You can go upto an index $$$i$$$ and take extra occurences of two adjacent elements.

    In this example, for instance you can go upto index 3 ( 0- indexing ) and take extra occurence of pair $$$(5,4)$$$. The number of extra occurences is $$$min(z,\;movesLeft/2)$$$

    Rest is a greedy approach and I leave that upto you.

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    You can solve problem B in O(K) without any DP.

    For each index i, calculate the maximum sum you can achieve finishing at that position. You do that by storing the current prefix sum and the largest pair of elements until the current position, and going back there as much as possible.

    Code: https://codeforces.com/contest/1389/submission/88377724

    void run_test() {
        int n, k, z; read(n, k, z);
        vi a(n); rep(i, n) read(a[i]);
        int ans = a[0];
        int mx = 0, sum = a[0];
        repa(i, 1, k+1) {
            int _z = z;
            sum += a[i];
            mx = max(mx, a[i-1] + a[i]);
            int left = k - i;
            int curr = sum;
    	int x = min(_z, left / 2);
            curr += mx * x, left -= 2 * x, _z -= x;
            if(left > 0 && _z > 0) curr += a[i-1];
            ans = max(ans, curr);
        }    
        println(ans);
    }
    
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ORZ

      Well it was kind of obvious it was greedy and because it was B. By the way is this a smurf account? :p

»
4 months ago, # |
  Vote: I like it -9 Vote: I do not like it

My first ever contest in codeforces.I solved A no. problem.C no. also seems doable.Anyway,it was fun.Looking forward to participate in future contest as well.

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

In problem C, I selected "two" most occurring digits present in String, let's call them A and B and their frequencies be F_A and F_B (F_A >= F_B) and I removed the rest of the integers, let's call Sum of these remove integers be X. Now in this New String I counted number of pairs of type AB and BA and at the end final result should be X + min( new_string_length - 2* max(#AB,#BA) , F_B), right ?

But I got the wrong answer on test 2. I am not able to figure out what is wrong in my approach. Please help.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dont select 2 most occuring digits you have to look for each and every pair

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

    For a string like, "0001112323" making it "2323" will be a better choice, although it's not the most frequent one.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      During the contest I thought that considering every pair and iterating over the string in the worst case will cost 100 x 2*10^5 ~ = O (10^7) and it won't pass but I guess C++ is fast enough to do these basic operations. Lesson learned if no of operations are approx 10^7 do implement brute force lol

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try the test case "111111111112222222222222343434"

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    959588831

    try this test case here the answer should be 5

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

This is so frustrating since I was so reluctant to solve C using brute force thinking that it will TLE anyway :(.

Ended up seeing there are no other methods than brute force...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is a little less of the brute force way :

    #include<bits/stdc++.h>
    using namespace std;
     
    int main(){
    	#ifndef ONLINE_JUDGE
    	freopen("input.txt","r",stdin);
    	freopen("output.txt","w",stdout);
    	#endif
     
    	int n,i,j,t,l,r;
    	cin>>t;
    	string s;
    	while(t--){
    		cin>>s;
    		map<char,int>mp;
    		n = s.size();
    		map<char,int>pos;
    		int ans = 1;
    		int mxMacho[10][10];
     
     
    		memset(mxMacho,0,sizeof(mxMacho));
     
    		for(i=0;i<s.size();i++){
    				mp[s[i]]++;
    				for(char j='0';j<='9';j++){
    					if(s[i]!=j && pos[j]!=0 && pos[s[i]]<pos[j]){
    						mxMacho[s[i]-'0'][j-'0']+=2;
    						ans = max(ans,mxMacho[s[i]-'0'][j-'0']);
    					}
    				}
    				pos[s[i]] = i+1;
     
    		}
    		
    		for(auto it:mp){
    			ans = max(ans,it.second);
    		}
     
    		cout<<n - ans<<endl;
     
     
    	}
    }
    
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Solution for D:

At first lets calculate how much more we need "intersection_length". Call it need. If (need <= 0) then print(0)

else

Lets for basic pair of segment calculate number of steps required that the segments touch each other.Call it cost.

And for basic pair of segment calculate number of steps required to make the segments are equal.Call it kol.

Then, fo basic segments maximal number of steps, that will gives us +1 to "intersection_length" in one step is kolcost. Call it add.

Now, lets iterate over i-th pair of segments, while need > 0 At first we need to make this segments contiguous, then add to answer cost. Now, let`s add to answer min(**kol**, need), and substract kol from need.

Also we need consider one case:

When need <= kol, and we already have identical segments, is can be better for us, if do next steps on current pair of segments. I.e if need <= kol, answer += min(need * 2, cost + need)

If need > 0 and we went through all the segments, Then each pair of segment(L, R) equal to L = min(l1, l2), R = max(l2, r2).(l1, l2, r1, r2 from text of D) Each that pair can add "intersection_length" only after two steps. Therefore, we need add to answer 2 * need.

С++ code

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you do provide the solve for c??thanks...

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

      For left rotation to be equal to right rotation, is equivalent to say that a string is equal to it's 2 times right rotation ( Or an even number of rotations ).

      Observing this we can say that, the string should have a cycle of length 2, i.e $$$x[i] = x[i\mod2]$$$ and $$$|x|$$$ is even.

      for example, 0101.., 12121212..., 131313131... ( Length should be even too. )

      So we can iterate over all digits $$$a$$$ and $$$b$$$ where $$$a,b \in [0,9]$$$ and check which sequence gives the shortest length.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank You...umm...I get that..I also deduced that during contest...but couldn't come up with a code..so..some help regarding code will be very much help..

»
4 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Can anyone tell why my soln for B fails???

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

main(){
    int t;cin>>t;
    while(t--){
        int n,k,z;cin>>n>>k>>z;
        int a[n];
        int maxpos=1;
        cin>>a[0];
        ll score=a[0],maxpair=-1;
        for(int i=1;i<n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=k;i++){
            if((a[i]+a[i-1]) >= maxpair){
                maxpos = i;
                maxpair = (a[i]+a[i-1]);
            }
        }
        for(int i=1;i<=maxpos;i++){
            score+= a[i];
            k--;
            if(k<=0) break;
        }
        int curr = maxpos;
        while(z>0 && k>0){
            if(curr == maxpos){
                curr--;
                score+= a[curr];
                z--;k--;
            }
            else{
                curr++;
                score+= a[curr];
                k--;
            }
        }
        curr++;
        while(k>0 && curr<n){
            score+= a[curr];
            curr++;
            k--;
        }
        cout<<score<<"\n";
    }
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    Hey your code looks similar to my code help me even

    void solve() { ll n,k,z; cin>>n>>k>>z; vector a(n); for(int i=0;i<n;i++){ cin>>a[i]; } ll hig = -1; ll ind = -1; for(ll i=0;i<k;i++){ if(a[i]+a[i+1]>hig){ hig = a[i]+a[i+1]; ind = i+1; } } ll score = a[0]; ll iter = 0; ll pos = 1; ll ba = 0; while(iter<k){ score += a[pos]; if(pos==ind&&ba<z){ pos--; ba++; iter++; } else{ pos++; iter++; } } cout<<score<<endl; }

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

      No one will bother to help you if you display such code. At least ensure you indent your code so that it makes sense to others.

»
4 months ago, # |
Rev. 6   Vote: I like it -12 Vote: I do not like it

Can anybody tell where is this approach failing in C question?

Your code here...

from collections import defaultdict as dd
for _ in range(int(input()):
    s=input().strip()
    d=dd(list);d1=dd(int)
    n=len(s)
    for i in range(n):
        d[s[i]]+=[i]
        d1[s[i]]+=1
    ans=max(d1.values())
    if(ans%2==1):ans-=1
    l=list(d.keys())
    for i in l:
        for j in l:
            if(i!=j):
                l1=d[i]+d[j]
                l1.sort()
                curr=i
                te=1
                p=l1.index(d[i][0])
                for k in l1[p+1:]:
                    if(s[k]==curr):continue
                    else:
                        te+=1
                        if(curr==i):curr=j
                        else:curr=i
                if(te%2==1):te-=1
                ans=max(ans,te)
                l1=[]
    print(n-ans)
                    
              
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain to me your approach? Can't really understand your code :P

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

      I just stored all the positions of different characters.then I iterate over all the possible characters as i and j.

      I merge the position array of both i and j characters and sort that merged array.I then picked the first position of character i and start traversing for maximum length of type="010101" and then checked if it is even or not and hence update the answer.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I posted a solution for C in the comments. Lmk if you have any questions

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

          Actually I did the same thing.

          FOR EG:----s=2333453345335 then dict will be

          d={2:[0],3:[1,2,3,6,7,10,11],4:[4,8],5:[5,9,12]}

          then traversing through all possible cases I merge two position array of i and j characters then sort it.

          lets say i=3 and j=4. So my l1(after merging them and sorting)=[1,2,3,4,7,8,10,11] and I start traversing from first position of i(i.e"3") then updated at k=4 and then further keep on updating the ans.

          I think there is any edge case missing in it. Can you please help me with that?

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Got it. I have WA just for this statement

            if(ans%2==1):ans-=1

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

Loved this round

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

Amazing round. Really enjoyed these problems. Thank you :D

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

Can someone please help me with B. My approach is --> find the prefix sum and the max adjacent sum till current index and then start from kth element and find the max answer. https://codeforces.com/contest/1389/submission/88373889

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

In problem D I thought by mistake that it's all the intersections between all pairs of segments (i.e. n**2 intersections) :<<< (At the end I noticed it and I just now, an hour after the contest was over, submitted the correct answer...). I should read more carefully. meh.

It made it much harder...
I was sure I was on the right path because there were all these nice formulas coming up. For example, if all segments in both sides are now the same (that's the first step) then you start building the intersections one at a time. You first add 1 in one of the segments in a, then add 1 in one of the segments in b, then another one in a... It creates the formula 0+1+1+2+2+3+3+4.... which at an even index 2*i, the sum is i**2, and at odd index 2*i+1, its 2(1+2+...)=i(i+1). So you can get the minimum i between the two options that achieves k.

That was just a taste as there are plenty more cases I had to think of etc...

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

Can anybody help in finding the issue in these submissions?

http://codeforces.com/contest/1389/submission/88337710 http://codeforces.com/contest/1389/submission/88373614 These are submissions for B and C, I have used the right logic as mentioned by others but can't find the issues.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why are you looking at x[i] and x[i+1]? Why would they be adjacent to one another? For example in this case:

    021203130414 You would miss 010101 which is the best option.

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

      Yes, you are right! Was thinking in that direction only but implemented it completely wrong. Thanks for your help!

»
4 months ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

My solution for E:

explanation-for-E

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
Solution for C
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess, it should be 45 combinations only.

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

      Not quite, 01010101 and 10101010 are different strings, so you would have to treat 0 as the first character in the 2-periodic sub-sequence for the first string, and 1 as the first character for the second string.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        TLDR:

        0101010 has both a 101010 and a 010101 type strings in it.

        DETAILED:

        Let us say the string we get after removing all other numbers but two be some 011100001001010.....

        Then for the above we want it to reduce to the form : 01010101... Note, that if the reduced string ends with 1 then the answer is: size(original string)-size(reduced string). Else, the answer is: size(original string)-{size(reduced string)-1}.

»
4 months ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

Hey I think there's a problem in the statement of Problem C After reading it i thought(probably most of the participants) that a string is good only if one left cyclic shift equals one right cyclic shift. This was a major ambiguity in the problem.Please, tell me what you all think ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let's say string t is good if its left cyclic shift is equal to its right cyclic shift.

    It's saying that the string's left cyclic shift is equal to the string's right cyclic shift. Along with the given examples, it seemed pretty clear to me.

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

      According to Problem statement left cyclic shift is - Let's call left cyclic shift of some string t1t2t3…tn−1tn as string t2t3…tn−1tnt1.

      According to which left shift is done only one time. Also assuming what i thought was correct, the given examples give same output.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, the cyclic shifts are only done once. It's just asking the minimum number of characters you need to remove so that t1t2t3…tn−1tn == t2t3…tn−1tnt1.

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

    the following must apply for even cases:

    s[0]=s[2]

    s[1]=s[3]

    s[2]=s[4]

    ...

    Basically, you understood it correct. What is the problem?

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

I don't understand why sometimes I get 'uninitialised value usage' error. Even if the code is correct for such submissions. And if I initialise he default value of a and b as 0 i get this output. And if the same code is modified by replacing cin by scanf and long long int by int I get Accepted. Can I know the reason? (for problem A)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    never use both "cin/cout" and "scanf/printf" whenever you have "ios_base::sync_with_stdio(false);cin.tie(nullptr);"

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you call sync_with_stdio(false) you can't use both scanf and cin as they're no longer synced (so in this case your scanf would read a large buffer from stdin and leaves nothing for cin to read).

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I heard that scanf, printf is faster than cin cout from stackoverflow. So is it better to use them, by removing 'ios_base::sync_with_stdio(false), cin.tie(nullptr);' ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Using 'ios_base::sync_with_stdio(false), cin.tie(nullptr);' and one method of input / output is much faster than removing that line and mixing methods. Just choose one of the methods and stick to it. Either use iostreams (cin / cout) everywhere or use stdio (scanf/printf) everywhere. I would be very surprised if there are any problems where the speed difference between the methods is enough to be an issue.

»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Is it possible to hack this solution of PROBLEM A --->Code

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, if 2*l <= r he gets a solution on first iteration, else the break part is called

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

In my submission for C, I counted all the occurrences of size 2 strings inside grid[10][10]and then went for the maximum one. What is the flaw in my logic? Link to Solution

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately I am having a hard time understanding your code but I also maintained a 2d grid, you can see my submission.

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

can any one please tell my why test case l=13,r=22 show output of -1 -1. in problem 1.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    l*2=26

    26 is bigger than r. The most optimal way to choose the 2 integers is to choose l and l*2. It can easily be proved this is the optimal solution as the LCM would be l*2. If you chose any integer, you will multiply its divisors that doesn't exist in the initial l which makes the solution worse.

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

Here's my recursive approach to B: https://codeforces.com/contest/1389/submission/88361912

It gives an obvious TLE. I was trying to memoize it but couldn't. Can I pass the constraints with memoization? And how to memoize it?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, In your recursion the only changing parameters are i,z and 'L'/'R'. So you could maintain a global array dp[k][z][2] and store the values to avoid recomputations.

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

Can somebody please tell me what does rt mean (during hacking)? For example: https://codeforces.com/contest/1389/submission/88344396

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

UPD: I already found why it's failing

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Looks like CF is making B harder than E.

»
4 months ago, # |
  Vote: I like it +49 Vote: I do not like it

XD

Screenshot-from-2020-07-30-00-29-05.png

»
4 months ago, # |
Rev. 7   Vote: I like it -6 Vote: I do not like it

.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I went for this approach since i thought $$$z$$$ upper bound is at least $$$5$$$, not at most $$$5$$$. I wasn't able to debug it, but it seems correct.

»
4 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

These users interview _krtky_ rahul16077 tempcfcfcf have cheated in this Contest to increase their ratings abruptly. Please look at my post: https://codeforces.com/blog/entry/80772 . Their gang is downvoting this post, but lets not let it happen

Also I would request MikeMirzayanov to ban these accounts permanently. Codeforces is an accountable platform, lets aim for the same

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

From when did the length of a segment became the difference of extreme ends?!

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

    It has always been. Try to draw a segment and measure his length.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For a segment [x,y] hasn't it been y-x+1 rather than y-x

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

        In some problems it is like "the segment is from house 5 to house 7", then it is three houses. But if it is from point 3 to point 5, then the distance is two.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is a difference int these "types of segments". (y-x) it is a length of segment on a line in geometry, when y-x+1 is like quantity of numbers between x and y(including x and y).

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I first implemented some "inclusive" logic, too. But the statement says we should treat the numbers like coordinates, ie distance from i to i is zero.

    However, after having changed it that way I forgot that such segments can have size of zero. And was hacked most likely due to division by zero :/

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yaa! I too noticed the different definition used but only after the contest ended.

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

I did B with brute approach.. But can someone explain in detail why is it working??

»
4 months ago, # |
Rev. 5   Vote: I like it +22 Vote: I do not like it

Is there any way to solve D if initially intervals could be arbitrary instead of all being the same? I initially misread the question and worked on this version of the problem for a good while before realising it, but the question was pretty interesting anyways.

The problem reduced to the following: There are $$$n$$$ stores selling candy. In order to purchase candy from store $$$i$$$, you initially have to pay $$$a_i$$$ dollars, after which you can buy upto $$$b_i$$$ candies at $$$1$$$ dollar per candy. There is also a supermarket, which has an unlimited stock of candies and sells them $$$2$$$ dollars each. You DO NOT have to pay an initial amount to buy candies from the supermarket. EDIT: As AnandOza pointed out below, you can only buy candies from the supermarket if you've paid membership (paid $$$a_i$$$) to ATLEAST one store.

What is the maximum number of candies you can buy if you initially have $$$c$$$ dollars?

My attempt
  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    There's a slight inaccuracy in your restatement. You can only buy from the supermarket if you have bought a membership (paid $$$a_i$$$) to at least one store.

    (It's also "what's the minimum cost to buy $$$k$$$ candies", but you can just binary search to transform between the two questions.)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that my approach for problem D can be easily modified for this version of task.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now I realize that it is most probably not true.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the knapsack approach you just don't buy excess candies

    When normal knapsack looks something like this

    for [val, weight] in items
        for i in K..0
            if(i+val <= K)
                DP[i+val] = min(DP[i+val], DP[i]+weight)
    

    Modifying it to something like this will do the work

    for [val, weight] in items
        for i in K..0
            if(i+val <= K)
                DP[i+val] = min(DP[i+val], DP[i]+weight)
            else
                excess = i+val-K
                DP[K] = min(DP[K], DP[i]+weight-excess)
    
»
4 months ago, # |
  Vote: I like it -7 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't know why it got downvotes it was really funny :XD

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

Can someone please explain the DP solution for B?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have not used dp in B. I solved it using sum array prefix. But in the contest due to the use of cerr it took a lot of time and I submitted now after contest. It is working like a charm. Here is my code.my code here

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same exact thing. But I was wondering about what the DP approach would be. I think I got it now though, thanks

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

    Let $$$i$$$ be the current position and $$$z$$$ be the remaining number of the left move. Then,
    $$$dp_{i,z} = a_i+max(dp_{i+1,z},dp_{i-1,z-1})$$$

    Also, you have to maintain a variable $$$n$$$ indicating the ending position. Initially, $$$n$$$ will be equal to $$$k$$$ and each time you make a left move, $$$n$$$ will be decremented by $$$2$$$.

    My submission

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Since editorials for these take a really long time to get released, video solutions to A-E and my idea for F are available for people who are interested.

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

    thx.F confused me a lot really.xD

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I think I over-complicated it quite a bit. You don't need flow at all I'm pretty sure, because of how things are set up, you can do a greedy on one side and use a segment tree for the other I think.

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

    always appreciate

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello, thanks for your video. For problem B, why we don't need movesLeft as part of the dp state?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    subscribed :-)

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

a[] = 1 2 5 6 b[] = 0 3 7

I want to find maximum length of alternating increasing sequence from arrays a and b. choose elements from a and b alternatively.

eg.) 1,3,5,7 or 0,2,3,5

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

" The penalty for each incorrect submission until the submission with a full solution is 10 minutes ", here what do we mean by "with a full solution" ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A 'correct' solution that passes pretests and doesn't get hacked, and you don't submit another solution to that same problem later.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it
  1. I found that b can be solved with simple greed. Therefore, the z constraint in the question is used to mislead the questioner, after all, greedy is much easier to write than dp. But many red user didn't use greed, and it seemed that they were also misled.
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I don't think it was misleading. The DP solution was pretty straight forward and easy to implement.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They can write dp better than you can greedy

»
4 months ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

Hey I have written a PYTHON code for problem B of this contest.I am getting runtime error in test case 3. I have no idea why. PLEASE PLEASE PLEASE help me. Here is the code:-- from collections import defaultdict t=int(input()) for _ in range(t): n,K,Z=map(int,input().split()) ar=list(map(int,input().split())) dp=defaultdict(lambda:-1) def score(i,k,z): if k==0: return 0 if dp[(i,z)]!=-1: return dp[(i,z)] if z==0: s=sum(ar[i+1:i+k+1]) dp[(i,z)]=s return s if k>=2: # here i have calculated two steps at a time in s1 s1=ar[i-1]+ar[i]+score(i,k-2,z-1) s3=ar[i+1]+score(i+1,k-1,z) s=max(s1,s3) dp[(i,z)]=s return s if k==1: s=max(ar[i-1],ar[i+1]) return s su=ar[0]+ar[1]+score(1,K-1,Z) print(su)

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

Hey I have written a PYTHON code for problem B of this contest.I am getting runtime error in test case 3. I have no idea why. PLEASE PLEASE PLEASE help me. Here is the code:-

content://com.mi.android.globalFileexplorer.myprovider/external_files/array%20walk

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

please upload the editorial, it will be helpful to beginner like me...

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

Could someone help me debug my code for problem B? https://ideone.com/b4oIM0 I iterate based on which pair of numbers we will repeat (we can repeat that pair from 0 to min(z, moves_remaining/2) times + potentially move left once more and then continue moving to the right. Thanks!

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

Hi can anyone please explain me 88310682 in this submission how have he not used moves in state and check the breaking condition on moves it it is not a part of the states in DP. Anyone please provide me reasoning for this.

Author of the code Ashishgup

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because for a particular state(indx,left,prev) , no of moves are same and can be calculated.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain a bit. If you want to say that in all the transition moves are same we are moving from moves to moves+1. So in the case of Knapsack we also moves from index to index+1 but there but why we take that as a state ?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no of moves is a dependent variable , you can ignore taking it into dp state whereas index in a knapsack problem is an independent variable . No of moves = { if prev == 1{ if left > 0 => idx-1+2*(left-1)+1 else => idx-1 } else { => idx-1+2*left}

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes it is a dependent variable we can also calculate moves with No of moves = { if prev == 1{ if left > 0 => idx-1+2*(left-1)+1 else => idx-1 } else { => idx-1+2*left}

          But the thing is here we are not calculating the moves instead we are passing it as a function argument. I am fine if we calculate moves with the help of the formula. But how by passing it as an argument it is not creating any issue can you please give me an insight.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            if we passed it as an argument, we kept track of moves and there is no need of the formulae , try solving without passing it. Dynamic programming is all about visualizing the scenario in your own way, it is not magic, try to run some steps by your hand . You'll get it.

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

when will the rating of participants be updated?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    According to my experience, I think it will be updated within an hour ,but can't say for sure!

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

So i tried explaining the Problem B here in this video in hindi. Hope it helps you. If u have any doubts let me know.

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

can someone please tell me what i m missing in my code for problem B My Submission For Problem B

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

CAN anyone please explain B?

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Editorial Please!

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

Are the system tests done? If not does anyone why it's taking too much time? It's already been 2hrs since open hacking phase is done.

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

Well, in my code for problem B I literally forgot to check the condition of not making two or more consecutive jumps to the left, but I got accepted. My dp is doing some weird magic :P

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

    Yeah me too. It got accepted because the value so obtained doesn't exceed the maximum value found by repeatedly cycling over the adjacent elements. Phew!

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

Can anyone explain to me why prob B wont run by bruteforce (extreme recursion without memoization) like at every index i you go to your left if you can and then take the maximum of all the steps that you have taken.

If we try to think about the time complexity of this approach, then if we consider the recursion tree there will be branching only at 5 levels at max as z <= 5, which means there will be atmax 32 branches and after that we will just go down one level untill we exhaust our k. so basically by this time complexity turns out to be O(32*n) = O(32*10^5), which i think should be acceptable.

link to my bruteforce submission that gives TLE

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

    I think the time constraints are a bit tight. I tried to do the same thing using recursion but got TLE and then I had to use the concept of prefix-sums to get AC. The main idea behind my code is that if we go decide to go left for some index (say i) then we would keep repeating the cycle of left, right, left, right.. until either the left moves are finished or we have completed all the k steps. So for each index i > 1, I update the answer with the maximum answer that is possible there if we go in a left, right cycle and then take the remaining steps in the right direction (for which I have used prefix sums). If we finish the moves before the left moves are finished for some index, then I simulate the process. The link to my submission: https://codeforces.com/contest/1389/submission/88343523

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

    n = 20, k = 19, z = 5 your function is called 18435 times, which is approximately equal to C(n,5)

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

    No, you don't just have 5 branches. Think about it like this. Since you are simulating all possible scenarios, it is safe to assume you are exploring all the positions from which you can go left. So, let's assume that we are using all the z moves to move left. So, this is equivalent to choosing z positions from k-2*z positions which takes O(n ^ z). Hence, the TLE.

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

    consider movement strings as $$$RRRRR...$$$ $$$k$$$ times Then the number of ways to introduce $$$z$$$ $$$L$$$ s in this string is $$$\binom{k}{z}$$$

    And number of total movements are $$$\binom{k}{0} + \binom{k}{1} + ... + \binom{k}{z}$$$

»
4 months ago, # |
Rev. 3   Vote: I like it -39 Vote: I do not like it

This is regarding the message I have received from the the system "Your solution 88353117 for the problem 1389C significantly coincides with solutions AGP/88353117, i-tick/88359037. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked." I have no idea how this has happened. I have written the code on my own. I don't even know who tf is "i-tick" . Someone please explain what is going on. How is this even possible? By the submission number we can easily see that he copied from me. i-tick why tf did you copy my code? I don't even use idone.com . One possibility however after a lot of brainstorming is that I always publish my code on github as soon as I solve the problem. Maybe this guy has copied my code from there. I can prove that I have written the code myself My code on github I will not do such a thing from next time. Can pikmike please tell me whether I can get my ratings back?

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

    Note that unintentional leakage is also a violation.

    Publishing it on Github during live contest is not even unintentional, it is intentional. You made a mistake, just accept it. What an annoying comment.

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

    Next time you'll stream live on twitch?

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

Can someone tell how to optimize problem B my solution getting tle https://codeforces.com/contest/1389/submission/88411647 how to reduce parameters.

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

please tell me why I am getting runtime error? for problem B, my submission https://codeforces.com/contest/1389/submission/88348466

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

Can anyone please tell me why 88328446 gave TLE in B as it only runs for 100000*2*6 tine which is ok enough for 2 sec. Thanks in advance.

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

difficulty:A<C<B<E<D<F<G

Problem D has too many details but other problems are good. :)