By awoo, history, 3 years ago, translation,

Hello Codeforces!

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:

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_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 244mhq 0:22
F nitixkrai 0:23
G MyK_00L 1:05

UPD: Editorial is out

• +413

| Write comment?
 » 2 years ago, # |   +165 Random Guy: *complains about previous contest in comments*CF-Community: So,you have chosen death?!
•  » » 2 years ago, # ^ |   -68 That's why CF comment section and its community sucks
 » 2 years ago, # |   +106 not gonna lie, this comment section is already sh*t.
 » 2 years ago, # |   -66 If govt. was the CF community and the people who posted a comment were protesters.
 » 2 years ago, # |   -74 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!
•  » » 2 years ago, # ^ |   0 Simply,it's not for Russian 5th to 8th grade student anymore.
 » 2 years ago, # | ← Rev. 3 →   -40 People in comment section are hiding own weakness by giving other blame.
 » 2 years ago, # | ← Rev. 3 →   -98 mynameJEFF
•  » » 2 years ago, # ^ |   -56 Random Guy: * copies https://codeforces.com/blog/entry/80723?#comment-670498 *CF-Community: So, you have chosen death?!
•  » » » 2 years ago, # ^ |   -26 This is the first time William has got a downvote dominating comment. just so that you don't feel bad William my comment got deleted.
•  » » » 2 years ago, # ^ |   -30 tmw i love you but this was contribution farmingmy date request is still active
 » 2 years ago, # |   -36 Is m2.codeforces.com not working?
 » 2 years ago, # |   -17 Summary of this blog comment section: The comment is hidden because of too negative feedback, click here to view it.Downvote is coming :)
 » 2 years ago, # |   +12
 » 2 years ago, # |   -33 My stupid WA on C took expert from me :'(
•  » » 2 years ago, # ^ | ← Rev. 3 →   -8 C: I wasn't able to figure out the solution. Help
•  » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   +2 I don't know why I get demotivated. Please help me with B and C after the contest
•  » » 2 years ago, # ^ |   +3 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
•  » » 2 years ago, # ^ | ← Rev. 9 →   +1 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
 » 2 years ago, # |   +51 Tbh, E was easier than B
•  » » 2 years ago, # ^ |   0 Can you share your approach?
•  » » » 2 years ago, # ^ |   +27 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.
•  » » 2 years ago, # ^ |   -30 I still don't understand how can they do the same mistake for 3 contests in quick succession. Really disappointed.
•  » » 2 years ago, # ^ |   +9 Agree.(but someone working hard on B didn't even read the question of E)
 » 2 years ago, # |   +49 The order of problem B and C should be exchanged.
 » 2 years ago, # |   +2 In problem E, Basically we have to found the number of pairs such that(x + d * y) % w == (y + d * x) % wHow will we reduce this expression?
•  » » 2 years ago, # ^ |   +25 (y — x) * (d — 1) = 0 (mod w)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 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
•  » » 2 years ago, # ^ |   0 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.....
•  » » 2 years ago, # ^ |   0 $(y-x)*(d-1)modW =0$
 » 2 years ago, # | ← Rev. 2 →   0 How to solve F?
•  » » 2 years ago, # ^ |   +78 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
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 WoW, Nice interval transformation trick!. Thank you :)) Btw, do you know some problems in which this trick can be applied?
•  » » » » 2 years ago, # ^ |   +3 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.
•  » » » » » 2 years ago, # ^ |   0 Many thanks :v
•  » » 2 years ago, # ^ |   +21 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.
•  » » » 2 years ago, # ^ |   +8 My implementation of this idea:https://codeforces.com/contest/1389/submission/88398726
 » 2 years ago, # |   -6 How to solve D?
 » 2 years ago, # |   -6 How to solve D ?
 » 2 years ago, # | ← Rev. 4 →   -17 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<
•  » » 2 years ago, # ^ |   0 when both characters a and b are same you don't need to check cnt%2 == 1(example: 000)
•  » » » 2 years ago, # ^ |   +5 Ahh yes didn't notice that thank you very much !
•  » » 2 years ago, # ^ |   0 a == b -> not minus if (cnt%2==1)
•  » » » 2 years ago, # ^ |   0 Thank you sir !
•  » » 2 years ago, # ^ |   0 If all characters of the answer string are same then length can be odd.
•  » » » 2 years ago, # ^ |   0 Just fixed that , thanks !
•  » » 2 years ago, # ^ |   0 check for a==b then length can be odd
•  » » 2 years ago, # ^ |   0 You don't need to decrement cnt if cnt%2==1, when it comes to a==b
 » 2 years ago, # |   +1 I see many people solved $C$ without $DP$, how to do it without $DP$ ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 the final string should be of the form AAAAAAAA....AA or ABABAB......AB. Iterate over all possible A and B
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +3 SolutionOnce you realise a good string can either be: $a^n$ or $(ab)^n$ where $a, b$ are different digits you can easily find for each digit $d$ number of steps to reach $d^k$, and then iterate through all pairs $c, d$ of different digits and greedily find longest subsequence which is of form $(cd)^k$. You can use standard greedy algorithm for finding subsequence which is: jump to first occurrence of $c$, then to first occurrence of $d$ after it, then to first occurrence of $c$ after and so on.
•  » » 2 years ago, # ^ |   0 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).
•  » » » 2 years ago, # ^ |   +5 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?
•  » » » » 2 years ago, # ^ |   0 For all test cases It's guaranteed that the total length of strings doesn't exceed 2⋅105.
•  » » 2 years ago, # ^ |   +1 how to do it with dp?
•  » » » 2 years ago, # ^ |   0 It's same solution except that I used dp to find longest subsequence of form xyxyxy..xy instead of simple greedy.
•  » » 2 years ago, # ^ |   0 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)
 » 2 years ago, # |   +37 B was very uninteresting!! Rest problems were nice.
•  » » 2 years ago, # ^ |   0 Why? I thought it was fine for an educational round. Probably not too interesting for a regular round though.
•  » » 2 years ago, # ^ |   0 It's for Russian 5th to 8th grade students , they think it's great , but not us.
 » 2 years ago, # |   +6 Nice Contest.Thanks, CodeForces, for the contest... Keep these good initiatives coming...
 » 2 years ago, # |   +69 Whoever came up with input format for problem G, please don't do that again.
•  » » 2 years ago, # ^ |   +36 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 :(
 » 2 years ago, # |   +6 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.
•  » » 2 years ago, # ^ |   +14 B took 1h, C took 7m for me :(
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +6 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
•  » » » 2 years ago, # ^ |   0 So why don't(or didn't?) you look at E?it took 1m for me.just simple maths
•  » » » » 2 years ago, # ^ |   0 B took too long. I probably would've easily got it if I had more than 7m left after D.
 » 2 years ago, # |   0 ll rec(ll idx, ll moves, ll lmoves, vector& arr, vector& psum, vector< vector< vector > >& 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 ?
•  » » 2 years ago, # ^ |   +6 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.
•  » » » 2 years ago, # ^ |   0 int mx=0; 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.
•  » » » » 2 years ago, # ^ |   0 Spoilermap,int>mp; int get_max(int i,int k,int z,int done_left=0){ array temp {i,k,z,done_left}; if(!k) return v[i]; if(mp.count(temp)) return mp[temp]; mp[temp] = max(mp[temp], v[i] + get_max(i+1,k-1,z,0)); if(!done_left and i>0 and z>0) mp[temp] = max(mp[temp], v[i] + get_max(i-1,k-1,z-1,1)); mx = max(mx, mp[temp]); return mp[temp]; } But it will give tle, as we are visiting states which are useless.
•  » » 2 years ago, # ^ |   +3 moves = idx + 2 * lmoves
•  » » » 2 years ago, # ^ |   0 Thanks ! Got it Accepted !
•  » » 2 years ago, # ^ |   0 use map instead of 3d dp array it will be easy
•  » » 2 years ago, # ^ |   0 Here, in this code how do you make sure that you don't go left twice or more times in a row?
•  » » » 2 years ago, # ^ |   0 Hmm, that should be an issue here. I don't know why it passed all test cases.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 I believe that the case where we need to move left more than once consecutively won't arise.
•  » » » » 2 years ago, # ^ |   +4 Agree.So maybe that condition was redundant.
•  » » » 2 years ago, # ^ |   +5 That was said in the problem statement, right?
•  » » 2 years ago, # ^ |   0 (the answer is:not to use DP)
•  » » 2 years ago, # ^ |   0 see this comment
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 how did you come up with this, I did brute force and it worked
•  » » » 2 years ago, # ^ |   0 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.
•  » » » » 2 years ago, # ^ |   +3 got it accepted , a very stupid mistake.
•  » » » » » 2 years ago, # ^ |   +3 congrachulashunz | (• ◡•)| (❍ᴥ❍ʋ) https://codeforces.com/contest/1389/submission/88318523 have a look at this
•  » » » » » 2 years ago, # ^ |   0 I tried the same idea during contest, but could not pass test case 2. Can you share your accepted submission link?
•  » » » » » » 2 years ago, # ^ |   0 Test case 2 was giving me a lot of turment......
 » 2 years ago, # |   +4 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.
 » 2 years ago, # |   -8 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?
•  » » 2 years ago, # ^ |   0 LCM(L,2*L) = 2*L and is the smallest LCM you can find in the interval
 » 2 years ago, # | ← Rev. 2 →   -28 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(); mapm; mapodd; mapeven; 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; } } 
•  » » 2 years ago, # ^ |   +10 try 121231212
 » 2 years ago, # |   +71 Problem B:![ ]()
 » 2 years ago, # |   +106 Really, what goes through people's heads when they message others like this during the contest....
•  » » 2 years ago, # ^ |   +11 is he a cm?
•  » » » 2 years ago, # ^ |   +29 Yes, and they've given enough contests that they should know better than to do this...
•  » » 2 years ago, # ^ |   +18 Honestly participants shouldn't be allowed to send messages during contests.
•  » » 2 years ago, # ^ |   0 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....
 » 2 years ago, # |   -37 Best Educational Round EVER!!
 » 2 years ago, # |   0 Can anyone tell why this is giving TLE on test case 2 ( Problem B ) ? https://codeforces.com/contest/1389/submission/88360778 Thanks in advance
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Your memset is going to take too long (10000 * 100005 * 6 * 2 * 4 bytes set to -1).
•  » » » 2 years ago, # ^ |   0 It was the only error :|. Thanks by the way.
 » 2 years ago, # |   +18 Does D have a more elegant solution than lots of nested ifs?
•  » » 2 years ago, # ^ |   +12 Maybe by using max and min functions cleverly.
•  » » 2 years ago, # ^ |   +3
•  » » » 2 years ago, # ^ |   +8 can You explain ??
•  » » » » 2 years ago, # ^ |   +3 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$.
•  » » » » » 2 years ago, # ^ | ← Rev. 4 →   0 That's smart, thanks :) knew the logic but wasted too much time on ifelse :(
•  » » » 2 years ago, # ^ |   +3 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.
 » 2 years ago, # |   0 What's wrong with my this solution for problem C ? Please provide any counter case .
•  » » 2 years ago, # ^ |   0 12312
•  » » 2 years ago, # ^ |   +8 Test112121The correct answer is 1
 » 2 years ago, # | ← Rev. 2 →   0 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 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?
•  » » 2 years ago, # ^ |   0 size of dp is just too big as k
•  » » » 2 years ago, # ^ |   0 my dp is defiened as dp[k][2][z]
•  » » » » 2 years ago, # ^ |   +2
 » 2 years ago, # |   0 I am very demotivated... where is button to delete account?****
 » 2 years ago, # |   -24 ![ ]()
•  » » 2 years ago, # ^ |   -16 I have seen this meme in every contest comments. Stop it!
•  » » » 2 years ago, # ^ |   +56 ![ ]()
 » 2 years ago, # |   0 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: 88310231Thanks in advance!
•  » » 2 years ago, # ^ |   0 Try Test1 7 5 2 1 2 3 100 100 5 6 
•  » » » 2 years ago, # ^ |   0 Got it. Thanks buddy!
•  » » » » 2 years ago, # ^ |   0 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
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » 2 years ago, # ^ |   0 12 11 5 1 2 9 8 1 1 1 1 1 1 9 9It fails here. The answer is 88. My answer is 44. Thank You
 » 2 years ago, # |   0 B was like a hell... AGC B?
•  » » 2 years ago, # ^ |   +16 No bro AGC(I hope u meant Atcoder Grand) is other level. Even last contest B was tougher than today's B.
 » 2 years ago, # |   +3 Hints for B, please.
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 I thought of that approach but won't that give TLE ? $1 \leq i \leq n$ and $1\leq j \leq n-1$ right ?
•  » » » » 2 years ago, # ^ |   0 j <= 5. See constraints of problem.
•  » » 2 years ago, # ^ |   0 do bruteforce with any kind of optimizations
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 4 →   +1 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. 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); } 
• »
»
»
2 years ago, # ^ |
0

### ORZ

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

•  » » » » 2 years ago, # ^ |   +8 when you put "R" in orz, it doesn't mean what you want to mean.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 dont select 2 most occuring digits you have to look for each and every pair
•  » » 2 years ago, # ^ |   +3 For a string like, "0001112323" making it "2323" will be a better choice, although it's not the most frequent one.
•  » » 2 years ago, # ^ |   0 Try the test case "111111111112222222222222343434"
 » 2 years ago, # |   +11 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, lets 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
•  » » 2 years ago, # ^ |   0 Can you do provide the solve for c??thanks...
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # |   -18 Can anyone tell why my soln for B fails??? #include using namespace std; typedef long long ll; typedef vector vi; typedef pair ii; typedef vector 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>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
•  » » 2 years ago, # ^ |   -23 Hey your code looks similar to my code help me evenvoid solve() { ll n,k,z; cin>>n>>k>>z; vector a(n); for(int i=0;i>a[i]; } ll hig = -1; ll ind = -1; for(ll i=0;ihig){ hig = a[i]+a[i+1]; ind = i+1; } } ll score = a[0]; ll iter = 0; ll pos = 1; ll ba = 0; while(iter
•  » » » 2 years ago, # ^ |   +4 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.
•  » » » » 2 years ago, # ^ |   +3 How about they debug for 2 hours before asking.
•  » » » » » 2 years ago, # ^ |   0 See my last blog entry, I got bashed by a red coder.
 » 2 years ago, # | ← Rev. 6 →   -12 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) 
•  » » 2 years ago, # ^ |   0 Can you explain to me your approach? Can't really understand your code :P
•  » » » 2 years ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » 2 years ago, # ^ |   0 I posted a solution for C in the comments. Lmk if you have any questions
 » 2 years ago, # |   0 Amazing round. Really enjoyed these problems. Thank you :D
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   0 I modified your code, and get Accepted.Your algorithm is correct, but some boundary conditions are not noticed https://codeforces.com/contest/1389/submission/88399836
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 88423909 this is my submission for b. can u help me with this? i am getting wrong answer for test case 2. i don't know what logic i am missing :/
 » 2 years ago, # | ← Rev. 2 →   0 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...
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   +3 Yes, you are right! Was thinking in that direction only but implemented it completely wrong. Thanks for your help!
 » 2 years ago, # | ← Rev. 2 →   +17 My solution for E:
 » 2 years ago, # | ← Rev. 3 →   0 Solution for CFor a string to be good, the string must have a period of 2 (i.e. 01010101..., 26262626..., etc). The string must also end in the last character of the periodic sequence (i.e. "262626" is good, but "26262" is not.)To find the minimum number of character removals needed, we need to find the longest sub-sequence of s with a period of 2. We can brute force this by iterating through every pair of integers from 0-9 (100 total combinations) and finding the length of the 2-periodic sub-sequence, then updating a max counter after every iteration. The answer will simply be n-|longest sub-sequence|.Some things to be careful about: - The longest string can be 1-periodic as well. You can easily compute the longest 1-periodic sub-sequence by taking a count of all the numbers in the string. - A good 2-periodic sub-sequence must always have an even length. This can be easily proven.Total Complexity: O(100*n)Solution: 88325135
•  » » 2 years ago, # ^ |   0 I guess, it should be 45 combinations only.
•  » » » 2 years ago, # ^ |   +3 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.
•  » » » » 2 years ago, # ^ |   0 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}.
 » 2 years ago, # | ← Rev. 3 →   -16 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 ?
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 2 years ago, # ^ |   0 okk i get it now
 » 2 years ago, # | ← Rev. 2 →   0 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)
•  » » 2 years ago, # ^ |   0 never use both "cin/cout" and "scanf/printf" whenever you have "ios_base::sync_with_stdio(false);cin.tie(nullptr);"
•  » » 2 years ago, # ^ |   0 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).
•  » » » 2 years ago, # ^ |   0 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);' ?
•  » » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   -13 Is it possible to hack this solution of PROBLEM A --->Code
•  » » 2 years ago, # ^ |   0 No, if 2*l <= r he gets a solution on first iteration, else the break part is called
 » 2 years ago, # |   0 can any one please tell my why test case l=13,r=22 show output of -1 -1. in problem 1.
•  » » 2 years ago, # ^ |   0 l*2=2626 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.
 » 2 years ago, # |   0 Here's my recursive approach to B: https://codeforces.com/contest/1389/submission/88361912It 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?
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   0 Can somebody please tell me what does rt mean (during hacking)? For example: https://codeforces.com/contest/1389/submission/88344396
•  » » 2 years ago, # ^ |   0 I think it means runtime.
 » 2 years ago, # | ← Rev. 2 →   0 UPD: I already found why it's failing
 » 2 years ago, # |   +2 Looks like CF is making B harder than E.
 » 2 years ago, # |   +49 XD
 » 2 years ago, # | ← Rev. 7 →   -6 .
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 .
 » 2 years ago, # | ← Rev. 2 →   +14 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 happenAlso I would request MikeMirzayanov to ban these accounts permanently. Codeforces is an accountable platform, lets aim for the same
 » 2 years ago, # |   0 From when did the length of a segment became the difference of extreme ends?!
•  » » 2 years ago, # ^ |   +5 It has always been. Try to draw a segment and measure his length.
•  » » » 2 years ago, # ^ |   0 For a segment [x,y] hasn't it been y-x+1 rather than y-x
•  » » » » 2 years ago, # ^ |   +9 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.
•  » » » » 2 years ago, # ^ |   0 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).
•  » » 2 years ago, # ^ |   0 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 :/
•  » » » 2 years ago, # ^ |   0 Yaa! I too noticed the different definition used but only after the contest ended.
 » 2 years ago, # |   0 I did B with brute approach.. But can someone explain in detail why is it working??
 » 2 years ago, # | ← Rev. 5 →   +22 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 attemptI initially tried doing some sort of knapsack dp where the $value_i$ = $b_i$ and $weight_i$ = $a_i + b_i$, but then the fact that optimal solution might have one store only partially bought out was causing me trouble.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +5 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.)
•  » » » 2 years ago, # ^ |   0 Yes, you are right. Thanks for pointing the error out.
•  » » 2 years ago, # ^ |   0 I think that my approach for problem D can be easily modified for this version of task.
•  » » » 2 years ago, # ^ |   0 Now I realize that it is most probably not true.
•  » » 2 years ago, # ^ |   0 In the knapsack approach you just don't buy excess candiesWhen 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) 
 » 2 years ago, # |   -7 The comment is hidden because of too negative feedback, click here to view it.
•  » » 2 years ago, # ^ |   0 Don't know why it got downvotes it was really funny :XD
 » 2 years ago, # |   0 Can someone please explain the DP solution for B?
•  » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   0 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
•  » » 2 years ago, # ^ | ← Rev. 3 →   +5 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
 » 2 years ago, # |   +11 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.
•  » » 2 years ago, # ^ |   +10 thx.F confused me a lot really.xD
•  » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +10 always appreciate
•  » » 2 years ago, # ^ |   0 Hello, thanks for your video. For problem B, why we don't need movesLeft as part of the dp state?
 » 2 years ago, # |   0 " 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" ?
•  » » 2 years ago, # ^ |   0 A 'correct' solution that passes pretests and doesn't get hacked, and you don't submit another solution to that same problem later.
 » 2 years ago, # |   -8 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.
•  » » 2 years ago, # ^ |   +3 I don't think it was misleading. The DP solution was pretty straight forward and easy to implement.
•  » » 2 years ago, # ^ |   0 They can write dp better than you can greedy
 » 2 years ago, # | ← Rev. 2 →   -26 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) `
 » 2 years ago, # |   0 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
 » 2 years ago, # |   0 please upload the editorial, it will be helpful to beginner like me...
•  » » 2 years ago, # ^ |   +1 +1
 » 2 years ago, # |   0 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!
 » 2 years ago, # | ← Rev. 2 →   0 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
•  » » 2 years ago, # ^ |   0 because for a particular state(indx,left,prev) , no of moves are same and can be calculated.
•  » » » 2 years ago, # ^ |   0 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 ?
•  » » » » 2 years ago, # ^ |   0 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}
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   0 when will the rating of participants be updated?
•  » » 2 years ago, # ^ |   0 According to my experience, I think it will be updated within an hour ,but can't say for sure!
 » 2 years ago, # |   0 can someone please tell me what i m missing in my code for problem B My Submission For Problem B
 » 2 years ago, # |   +2 Editorial Please!
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 done.
•  » » 2 years ago, # ^ |   0 Yes, system tests are done. but i don't know why its taking time to update ratings.
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   +3 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!
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ |   +3 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 n = 20, k = 19, z = 5 your function is called 18435 times, which is approximately equal to C(n,5)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 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}$
•  » » » 2 years ago, # ^ |   0 Got it Thanks
 » 2 years ago, # | ← Rev. 3 →   -39 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 awoo please tell me whether I can get my ratings back?
•  » » 2 years ago, # ^ |   +25 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.
•  » » 2 years ago, # ^ |   +12 Next time you'll stream live on twitch?
 » 2 years ago, # |   0 please tell me why I am getting runtime error? for problem B, my submission https://codeforces.com/contest/1389/submission/88348466
 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 what about number of test cases??
 » 2 years ago, # |   +6 difficulty:A
•  » » 2 years ago, # ^ |   0 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...
•  » » 2 years ago, # ^ |   -6 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.
 » 2 years ago, # |   +1 When will the tutorial be released ?
 » 2 years ago, # |   +1 why so much time for editorial ?
 » 2 years ago, # |   0 could anyone tell me the approach to solve the b question
•  » » 2 years ago, # ^ |   +1 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.
 » 2 years ago, # | ← Rev. 3 →   0 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??
•  » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » 2 years ago, # ^ |   0 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?
•  » » » » » 2 years ago, # ^ |   0 They just skipped my all solutions & and the whole contest... As predictor i could have gain +80
•  » » » » » » 2 years ago, # ^ |   +6 So... will you use ideone in public mode next time?
•  » » » » » » » 2 years ago, # ^ |   0 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
•  » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I think the meaning is that of "Die dümmsten Bauern haben die dicksten Kartoffeln.", but not sure about it.
•  » » » » » » 2 years ago, # ^ |   +6 That's sad, but it's okayy. This is not your last contest, many ahead. Cheeeers!!
 » 2 years ago, # | ← Rev. 2 →   0 Couldn't solve Problem F and Problem G. Can somebody suggest the prerequisites or some blog for them? Thanks!
 » 2 years ago, # |   +2 When will the editorials publish?
 » 2 years ago, # |   0 Can someone please explain to me why my code of B is Exceeding memory limit. https://codeforces.com/contest/1389/submission/88430205
•  » » 2 years ago, # ^ |   +2 Pass vector v also by reference it is created everytime rec is called and hence MLE
 » 2 years ago, # |   0 Auto comment: topic has been updated by awoo (previous revision, new revision, compare).