Educational Codeforces Round 92 [Rated for Div. 2]
By awoo, history, 4 years 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 Neon 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 tribute_to_Ukraine_2022 7 255
3 244mhq 7 267
4 Egor 7 293
5 Farhod 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 244mhq 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

Comments Comments (282)
| Write comment?
»
4 years 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?!

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

    That's why CF comment section and its community sucks

    → Reply
»
4 years ago, # |
  Vote: I like it +106 Vote: I do not like it

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

→ Reply
»
4 years 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.

→ Reply
»
4 years 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!

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

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

    → Reply
»
4 years 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.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -98 Vote: I do not like it

mynameJEFF

→ Reply
»
4 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Is m2.codeforces.com not working?

→ Reply
»
4 years 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 :)

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Screenshot_20200729_205651_com.whatsapp2.jpg

→ Reply
»
4 years ago, # |
  Vote: I like it -33 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Tbh, E was easier than B

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

    Can you share your approach?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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)

    → Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

The order of problem B and C should be exchanged.

→ Reply
»
4 years 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?

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

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

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.....

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

How to solve F?

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D?

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve D ?

→ Reply
»
4 years 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--;
→ Reply
»
4 years 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$$$ ?

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Solution
    → Reply
  • »
    »
    4 years 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).

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

    how to do it with dp?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
  • »
    »
    4 years 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)

    → Reply
»
4 years ago, # |
  Vote: I like it +37 Vote: I do not like it

B was very uninteresting!! Rest problems were nice.

→ Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

Keep these good initiatives coming...

→ Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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 :(

    → Reply
»
4 years 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.

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

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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years 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 ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

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

    moves = idx + 2 * lmoves

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

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

    → Reply
  • »
    »
    4 years 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?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
    • »
      »
      »
      4 years 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.

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

      That was said in the problem statement, right?

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

    (the answer is:not to use DP)

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

    see this comment

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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.

→ Reply
»
4 years 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?

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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;
       }
    }
→ Reply
»
4 years ago, # |
  Vote: I like it +71 Vote: I do not like it

Problem B:

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

→ Reply
»
4 years 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....

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

    is he a cm?

    → Reply
    • »
      »
      »
      4 years 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...

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

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

    → Reply
  • »
    »
    4 years 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....

    → Reply
»
4 years ago, # |
  Vote: I like it -37 Vote: I do not like it

Best Educational Round EVER!!

→ Reply
»
4 years 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://mirror.codeforces.com/contest/1389/submission/88360778 Thanks in advance

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

    Your memset is going to take too long (10000 * 100005 * 6 * 2 * 4 bytes set to -1).

    → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

    Maybe by using max and min functions cleverly.

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

    https://mirror.codeforces.com/contest/1389/submission/88373980

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

      can You explain ??

      → Reply
      • »
        »
        »
        »
        4 years 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$$$.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          That's smart, thanks :) knew the logic but wasted too much time on ifelse :(

          → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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 .

→ Reply
»
4 years 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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

![ ](48ql4x.jpg)

→ Reply
»
4 years 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!

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

    Try

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

      Got it. Thanks buddy!

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B was like a hell... AGC B?

→ Reply
  • »
    »
    4 years 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.

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

Hints for B, please.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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 ?

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

        j <= 5. See constraints of problem.

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

    do bruteforce with any kind of optimizations

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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://mirror.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);
}
    → Reply
    • »
      »
      »
      4 years 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

      → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
  • »
    »
    4 years 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.

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

    Try the test case "111111111112222222222222343434"

    → Reply
»
4 years 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 kol — cost. 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

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

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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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";
    }
}
→ Reply
  • »
    »
    4 years 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; }

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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)
→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years 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://mirror.codeforces.com/contest/1389/submission/88373889

→ Reply
»
4 years 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...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help in finding the issue in these submissions?

http://mirror.codeforces.com/contest/1389/submission/88337710 http://mirror.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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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!

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

My solution for E:

explanation-for-E

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

    I guess, it should be 45 combinations only.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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}.

        → Reply
»
4 years 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 ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
  • »
    »
    4 years 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?

    → Reply
»
4 years 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)

→ Reply
  • »
    »
    4 years 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);"

    → Reply
  • »
    »
    4 years 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).

    → Reply
    • »
      »
      »
      4 years 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);' ?

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's my recursive approach to B: https://mirror.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?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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://mirror.codeforces.com/contest/1389/submission/88344396

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD: I already found why it's failing

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Looks like CF is making B harder than E.

→ Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

XD

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

→ Reply
»
4 years ago, # |
← Rev. 7   Vote: I like it -6 Vote: I do not like it

.

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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://mirror.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

→ Reply
»
4 years 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?!

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
      • »
        »
        »
        »
        4 years 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).

        → Reply
  • »
    »
    4 years 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 :/

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
»
4 years 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??

→ Reply
»
4 years 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
→ Reply
  • »
    »
    4 years 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.)

    → Reply
  • »
    »
    4 years 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.

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

      Now I realize that it is most probably not true.

      → Reply
  • »
    »
    4 years 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)
    → Reply
»
4 years 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.

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

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

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the DP solution for B?

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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

      → Reply
  • »
    »
    4 years 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

    → Reply
»
4 years 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.

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

    thx.F confused me a lot really.xD

    → Reply
    • »
      »
      »
      4 years 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.

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

    always appreciate

    → Reply
  • »
    »
    4 years 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?

    → Reply
»
4 years 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" ?

→ Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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.
→ Reply
  • »
    »
    4 years 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.

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

    They can write dp better than you can greedy

    → Reply
»
4 years 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)

→ Reply
»
4 years 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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years 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!

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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.

    → Reply
    • »
      »
      »
      4 years 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 ?

      → Reply
      • »
        »
        »
        »
        4 years 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}

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the rating of participants be updated?

→ Reply
  • »
    »
    4 years 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!

    → Reply
»
4 years 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

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Editorial Please!

→ Reply
»
4 years 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.

→ Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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!

    → Reply
»
4 years 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

→ Reply
  • »
    »
    4 years 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://mirror.codeforces.com/contest/1389/submission/88343523

    → Reply
  • »
    »
    4 years 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)

    → Reply
  • »
    »
    4 years 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.

    → Reply
  • »
    »
    4 years 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}$$$

    → Reply
»
4 years 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://mirror.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 awoo please tell me whether I can get my ratings back?

→ Reply
  • »
    »
    4 years 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.

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

    Next time you'll stream live on twitch?

    → Reply
»
4 years 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://mirror.codeforces.com/contest/1389/submission/88348466

→ Reply
»
4 years 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.

→ Reply
»
4 years 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. :)

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

    I still don't think that this contest's problems are too off or something, but I quit problem D because it's too complex...

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Problem D isn't too hard. Many people didn't try to iterate throw number of full segments we will pick. It's still not clear enough why shall we iterate throw them for me too. But as a problem it isn't too hard.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the tutorial be released ?

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

why so much time for editorial ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could anyone tell me the approach to solve the b question

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

    Just try agreeing with one thing "to maximize the sum, we have to use all the available 'left moves' on one number". Let's call that number a special number. Special number may or may not be the maximum number available in the array.How? Let's say you have enough 'k' to visit the max element in the array, then that max number is the special number and you can use all 'z' available on that.But what if you don't have enough 'k' to reach the max number? In that case you have to use all the 'z' available on some other number that gives the maximum sum.

    Now, you can just brute force assuming every number as a special number and finally print the max sum among all those sums.

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

MikeMirzayanov awoo I got a message about rules violation about copying someone's code or he could have copied mine. But The person is an Indian Guy and I don't even know him..I use ideone for compiling my code every now & then. I think it's a mistake i probably publicly used Ideone. But so far that could have been my best contest. Please consider this as a mistake ... Can I please get my rating delta back??

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

    Happened to me once, yes the reason is using ideone in public mode, but my rating wasn't taken back, i just go a warning mail that said 2 users copied my code

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What should i do ?? To have my rating back ?? How should I communicate the system gave me a message to post a comment in the comment section of this post Sportsman

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

        I'm sorry, I don't know. But I didn't find your submissions of the last contest. Did the message from the system mention that your rating would be taken back?

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

          They just skipped my all solutions & and the whole contest... As predictor i could have gain +80

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

            So... will you use ideone in public mode next time?

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

              Obviously no man !! :3 in our country there is a proverb nera beltolai ekbar e jai :3 You won't understand it's meaning sorry for that and I don't even know it's English form

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                I think the meaning is that of "Die dümmsten Bauern haben die dicksten Kartoffeln.", but not sure about it.

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

            That's sad, but it's okayy. This is not your last contest, many ahead. Cheeeers!!

            → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Couldn't solve Problem F and Problem G. Can somebody suggest the prerequisites or some blog for them? Thanks!

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

When will the editorials publish?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain to me why my code of B is Exceeding memory limit. https://mirror.codeforces.com/contest/1389/submission/88430205

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

    Pass vector v also by reference it is created everytime rec is called and hence MLE

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission:(problem B) https://mirror.codeforces.com/contest/1389/submission/88774335 what is the problem in my code.Please help

→ Reply