Hello Codeforces!

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

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

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

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

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

Good luck to all the participants!

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

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

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Um_nik | 7 | 245 |

2 | I_love_chickpea | 7 | 255 |

3 | kefaa2 | 7 | 267 |

4 | Egor | 7 | 293 |

5 | Farhod_Farmon | 7 | 364 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | Joney | 20:-2 |

2 | applese | 19:-1 |

3 | FelixArg | 7:-2 |

4 | liouzhou_101 | 10:-10 |

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

Problem | Competitor | Penalty |
---|---|---|

A | noimi | 0:00 |

B | noimi | 0:05 |

C | Ari | 0:04 |

D | HanaYukii | 0:17 |

E | kefaa2 | 0:22 |

F | nitixkrai | 0:23 |

G | MyK_00L | 1:05 |

**UPD:** Editorial is out

Random Guy: *complains about previous contest in comments*

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

That's why CF comment section and its community sucks

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

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

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!Simply,it's not for Russian 5th to 8th grade student anymore.

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

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

Random Guy:

complains about previous contest in commentsCF-Community: So,you have chosen death?!

Random Guy: * copies https://codeforces.com/blog/entry/80723?#comment-670498 *

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

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.

tmw i love you but this was contribution farming

my date request is still active

Is m2.codeforces.com not working?

Yes,it is working

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

Downvote is coming :)

Logic?

This was true atleast for me...

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

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

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.

Thanks, I get it now

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

In problem C you should make string like this

`11111`

eg make all digits same or`202020`

make string ofevenlength where used only two distinct digits and no adjacent digits samewhile 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 implementationTbh, E was easier than B

Can you share your approach?

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.

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

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

The order of problem B and C should be exchanged.

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?

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

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.

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

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

How to solve F?

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

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

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.

Many thanks :v

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.

My implementation of this idea:

https://codeforces.com/contest/1389/submission/88398726

How to solve D?

How to solve D ?

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

UPD :

when both characters a and b are same you don't need to check cnt%2 == 1(example: 000)

Ahh yes didn't notice that thank you very much !

I wondered what edge case I was missing. So this was it. Thanks for sharing

this mistake cost me 2 WAs but finally caught it by testing new samples.

a == b -> not minus if (cnt%2==1)

Thank you sir !

If all characters of the answer string are same then length can be odd.

Just fixed that , thanks !

check for a==b then length can be odd

You don't need to decrement cnt if cnt%2==1, when it comes to a==b

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

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

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

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.

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.

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

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?

Read the question properly

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

ok! , then it should work, thanx!

For all test cases

It's guaranteed that the total length of strings doesn't exceed 2⋅105.Thanks . Also i think the time complexity of this approach is O(100*n)

Exactly,I too got suprised by this.

how to do it with dp?

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

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)

B was very uninteresting!! Rest problems were nice.

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

B was interesting, to me At least.

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

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

Keep these good initiatives coming...

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

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

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.

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

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

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

it took 1m for me.just simple maths

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

[deleted]

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

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.

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

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

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

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

moves = idx + 2 * lmoves

Thanks ! Got it Accepted !

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

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

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

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

Agree.

So maybe that condition was redundant.

That was said in the problem statement, right?

(the answer is:not to use DP)

see this comment

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.

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

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.

got it accepted , a very stupid mistake.

congrachulashunz | (• ◡•)| (❍ᴥ❍ʋ)

https://codeforces.com/contest/1389/submission/88318523 have a look at this

could you explain your method, not able to understand

I tried the same idea during contest, but could not pass test case 2. Can you share your accepted submission link?

Test case 2 was giving me a lot of turment......

Could you share your solution?

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.

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?

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

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)

try 121231212

Problem B:![ ]()

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

is he a cm?

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

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

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

Best Educational Round EVER!!

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

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

It was the only error :|. Thanks by the way.

Why this code gives TLE? https://ideone.com/wXdX3A

Can you please explain how does your code takes care of no consecutive left moves?

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

Maybe by using max and min functions cleverly.

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

can You explain ??

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$$$.That's smart,

thanks:) knew the logic but wasted too much time on ifelse :(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.

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

12312

Test1

12121

The correct answer is 1

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?

size of dp is just too big as k<n and n<=3*10^5

my dp is defiened as dp[k][2][z]

Your text to link here...

88377395 Here is my submission it passed the 1st case but not the 2nd one, can anyone point out what is the logical error in my code?

I don't think you need state [k] as it always decreases (left or right move).[z] and [i](the current index) are enough states.

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

![ ]()

I have seen this meme in every contest comments. Stop 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!

Try

TestGot it. Thanks buddy!

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

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.

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

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

B was like a hell... AGC B?

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

Hints for B, please.

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.

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

j <= 5. See constraints of problem.

do bruteforce with any kind of optimizations

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.

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.

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

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

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

## ORZ

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

when you put "R" in orz, it doesn't mean what you want to mean.

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

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.

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

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

Thank you.

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

Try the test case "111111111112222222222222343434"

959588831

try this test case here the answer should be 5

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

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

Here is a little less of the brute force way :

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

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

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.

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

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

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

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.

How about they debug for 2 hours before asking.

See my last blog entry, I got bashed by a red coder.

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

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

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.

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

Actually I did the same thing.

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

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

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

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

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

Got it. I have WA just for this statement

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

Loved this round

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

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

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

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

In

problem DI thought by mistake that it'sall 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...

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.

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.

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

My solution for E:

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

I guess, it should be 45 combinations only.

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.

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

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

oneleft cyclic shift equalsoneright cyclic shift. This was a major ambiguity in the problem.Please, tell me what you all think ?Let's say string

tis good ifitsleft cyclic shift is equal toitsright 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.

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.

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.

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?

okk i get it now

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)

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

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

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);' ?

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.

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

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

In my submission for C, I counted all the occurrences of size 2 strings inside

`grid[10][10]`

and then went for the maximum one. What is the flaw in my logic? Link to SolutionUnfortunately I am having a hard time understanding your code but I also maintained a 2d grid, you can see my submission.

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

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.

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

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

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.

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

I think it means runtime.

UPD: I already found why it's failingLooks like CF is making B harder than E.

XD

Why so many downvotes? Is there some glitch with the logic?My O(n) solution for

`B`

using prefix sums:Let's iterate on the number of lefts (call it $$$p$$$) that you take, from $$$0$$$ to $$$z$$$ making sure that $$$k\geq2\times p$$$.

It can easily be proved that $$$ans$$$ is the maximum of $$$\mbox{pre}[k-2\times p]+\mbox{maxAdjacentPairSum}[k-2\times p]\times p$$$. As taking each left reduces your ending position by $$$2$$$ (as compared to when you did not take left). So you'll finally end up at $$$k-2p$$$. Greedily choose the best lefts that you can take.

Here $$$\mbox{pre}[i]$$$ denotes the prefix sum till $$$i$$$, and $$$\mbox{maxAdjacentPairSum}[i]$$$ denotes max value of $$$a[j]+a[j+1]$$$ for all $$$0\leq j\leq i$$$.

88364085

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.

.

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

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

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

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

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

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.

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

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

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

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

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.

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

Yes, you are right. Thanks for pointing the error out.

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

Now I realize that it is most probably not true.

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

When normal knapsack looks something like this

Modifying it to something like this will do the work

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

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

Can someone please explain the DP solution for B?

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

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

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

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.

thx.F confused me a lot really.xD

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.

always appreciate

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

subscribed :-)

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

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

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

" 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" ?

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

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

They can write dp better than you can greedy

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

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

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

+1

This can help you.

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!

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

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

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 ?

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}

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.

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.

when will the rating of participants be updated?

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

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

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

CAN anyone please explain B?

Editorial Please!

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.

done.

Yes, system tests are done. but i don't know why its taking time to update ratings.

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

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!

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

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

n = 20, k = 19, z = 5 your function is called

18435times, which is approximately equal to C(n,5)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.

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

Got it Thanks

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

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.

Next time you'll stream live on twitch?

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

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

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.

what about number of test cases??