Hello Codeforces!

On Oct/11/2020 12:05 (Moscow time) Educational Codeforces Round 96 (Rated for Div. 2) will start. **Note that the start time is unusual**.

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 Adilbek adedalic Dalabaev, Alex fcspartakm Frolov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: The editorial is here.

Congratulations to the winners:

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

1 | WZYYN | 7 | 186 |

2 | 137_345_2814 | 7 | 194 |

3 | jiangly | 7 | 200 |

4 | LayCurse | 7 | 203 |

5 | dreamoon_love_AA | 7 | 258 |

Congratulations to the best hackers:

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

1 | ViciousCoder | 100:-9 |

2 | ManasG | 45:-13 |

3 | Valera_Grinenko | 57:-40 |

4 | RetiredRadwan | 36:-3 |

5 | fstzyh | 38:-9 |

858 successful hacks and 2258 unsuccessful hacks were made in total!

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

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

A | sevlll | 0:01 |

B | jkchen | 0:03 |

C | alireza_kaviani | 0:03 |

D | jkchen | 0:12 |

E | MagicSpark | 0:05 |

F | LayCurse | 0:36 |

G | MagicSpark | 0:36 |

This

unusual timemakes meunusual:(4AM for me :(

That's sad! Don't Sleep ;)

23 minutes to the contest.. Time to wake up bro

Good morning!

Wholesome-forces

3:30 PM here.....good time for me tho

notice the unusual timegetting usualwhich can be a good thing for many (and a very bad thing for some)

Btw, not sure where to write this, I just noticed there is a testing round just before this contest. Personally I am already tired to do a contest for 2 hours, so i don't really want to do a testing round just before that. I am happy to do a testing round any other time actually.

why unusual time for ECF...2AM

Hmmm.... from Edu 46, every Announcement blog was authored by pikmike and he was always included in the problemsetters' tab. Did he get angry from all the downvotes from last round? The last round was pretty great problem-wise, learnt a lot, especially from problem G.

Note that the start time is unusual, is getting usual to us :)

No vovuh , Roms , Neon and awoo! Are they okay?

vovuh, Neon and pikmike are participating officially in the contest this edu is based on.

my hope to return a cm

Normally unusual timings is due to a live contest happening at the same time. Is there any reason this time?

what happened to my rating graph its weird... how to solve it?? please look my profile?? @admin anyone can help??

Lunchtime for me :(

Where do you live and what time will be in your country at the contest?

India. Its 2:35 pm, in afternoon

ECF and opencup are at the same time, not cool

I will be doing online class and contest together. Shouldn't miss a single contest in this quarantine <3

do you have classes on sundays?

Yes, we have class everyday except friday in Bangladesh.

on Sunday? strange

devilbro yup brother. We have prayer on friday . So that day is off day.

in all muslim countries friday = sunday

Friday is special day for Muslim. We are majority Muslim in our country. So government make Friday off day for us. Such as Sunday is Holiday in your country.

The timing is great for me. Thanks :)

Can anybody explain me what does solution hacking means? Thanks in advance.

Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

Great start time for chinese participants:D

Same here in Korea.

it's

18:05(UTC+9)For Japanese too. :) (start at 18:05)

Recently many contests were held at 23:35(UTC+9), in which is difficult for me to participate.

2 days Back to Back Contests

10 October 2020 HHKB Programming Contest 2020 Codeforces Global Round 11

11 October 2020 Educational Codeforces Round 96 AtCoder Regular Contest 105

Great for learning

I think there should be more contests of this Asian timezone. Maybe there should be two types of contests for Europeans and Asians.

200% agree

11 minutes left time to be ready : )

Will BledDest be conducting the future rounds as well ? He's been conducting the last 2 EDU rounds too.

He has actually been conducting the last 79 edus.

Sorry I meant if you will be away like this contest.

Please, less ad-hoc.

please graphforces

C and D without educational worth.

C is just "try it, should work...somehow", D is kind of edgecase hunting.

Nah, C was kinda cute. To minimise the end value, we had to keep as many smaller digits as possible was my conjecture (which I indeed took a few minutes to prove after a guess submission). The solution (I think) was to take the biggest two values and perform the ceiling operation and then continue. D was quite great too if we (at least I) didn't misinterpret what the problem statement. I thought E could be something to do with segment trees and inversions but that didn't end so well for me implementation-wise.

I looked at your submission for C and it was kinda hilarious to see your struggle in comments. Well done though!

In C , For any value of n , i always got answer as 2. It was more observation based ig

I just recalled those two problems, and still, I think I did not learned anything from them.

In C you see the intended solution by coincidence, or you do not. If you do not come up with the idea to simply add the two biggest values you'll get stuck at this problem. Or find some other algo which coincidently works, too, like mine. But for somebody who did not solve C the thing you get is "There is nothing you can do. Solve more problems, mayby then someday you'll get the intuition to have the right idea at the right time."

And problem D is basically the same. You find the right pattern by blindly trying some pattern. Or you do not find it. I found the three points given as hints in the tutorial within like 10 minutes. But still did not found a way to make it a working algo for like an hour. And afterwards, just like in C, absolutely no knowledge of what I could have done differently or better.

That might be nice riddles, but from my point of view no problems to educate anything.

scoring?

all problems have equal weightage in educational round!

is there penalty on correct resubmission in educational round?

I am eagerly waiting to see the test case no:2 of problem D,,,huh.

Idea behind E?

Counting Reverse pairs (Inversions)

Contest Finished.

Can we discuss the problem before system judge?

I have not too much ideas about F&G

How to solve D?

Transform the string to an array of integers. Now traverse from left to right. When you meet one, you should delete some thing larger than 1 in the right. When you meet something that is not one, you just delete it.

95246189 same approach, but got wrong answer on pretest 2. Can you give me a sample test for which my code fails.

You should look at the verdict. It tells that you got WA on test 21 of test case 2.

I had kind of same approach but not able to figure out which test case it fails : https://codeforces.com/contest/1430/submission/95251105

It says test-525 of test-case-2, how do I figure out now where did it fail ?

I have wa on 525 test case too. https://codeforces.com/contest/1430/submission/95253889

You should have clearly mentioned about deleting the first right element greater than 1. Man, I was deleting the maximum one the right :(

How to solve D????

111011 -> [3, 1, 2]

delete -> minus 1

remove prefix -> delete first number

Then try best to maximize the operation

I used same logic but got WA Submission link : https://codeforces.com/contest/1430/submission/95229144

but when i removed lowerbound and submitted again with same logic it was accepted.

So please can you tell me what the issue is ?

two pointer concept.

Maintain an array of lengths of consecutive elements. If the first prefix length is greater than 1 (>1), then we can remove that prefix and increase the number of operations. Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it. If such length is not found, remove the last length from the array (maintain 2 pointers one left and one right and reduce the right pointer).

Example :- 1 5 10111

After 1st operation -> 011

After 2nd operation -> 1

Thus 3 operations are required.

A counter example as to why we should reduce from the first large prefix instead of the largest one is here

Now if the prefix length is equal to 1 (==1), then search for the first length in the array that is greater than 1 and reduce it.

Please tell me wouldn't that make the complexity n*n. It tried the same thing but got tle on test 4.

Just keep pointer to last element that is greater than 1 and shift it right if necessary (do not search for it from the start every time).

You don't have to search starting from the first element always. Suppose your at 2nd element in [1,2,2,3]. Now, after reducing that, you only need to move forward in the array because the previous entries will be <=1. This can be done using a variable to store the current reducing index and incrementing it accordingly.

Thanks :)

How can we know that the next value is >= 2?

Example: [1, 2, 1, 3], if you are at the second element

then you will decrement the 2nd element and it will be [1, 1, 1, 3] now if you increment it by one it will be on the 3rd element which is 1. But reducing 1 isn't correct, the correct one is to reduce 3.

So how to increment it?

Please I am stuck here for several hours.

Suppose your pointer was on the 2nd element, now you have to increase until it becomes >=2. If it is not possible, then u just reach the end of the array.

I used the sae concept but getting WA on 252nd test : https://codeforces.com/contest/1430/submission/95251105

How do I figure out a test where it fails ?

Try reading the comments to find any test cases that your solution may fail. I don't think there is a way to access that particular test.

I got it. When the current value if "1", I was trying to make up for it by using the element which is the largest in range (i+1,N) which is not always optimal , better option is to use the element closest to the current index (on its right) . Thanks!

Not largest, any number which is greater than 1 in range (i+1,N) is my approach. What's wrong in that?

Choosing any number in range (i+1,N) is not optimal , its better to always choose the first number greater than "1" in range (i+1,N) . Why ? Because, you are at index "4", and a[4]=1 , also, a[5]=1,a[6]=1,a[7]=3,a[8]=1,a[9]=1,a[10]=5 .

Now, you have only two options, either select from a[7] or a[10] , but the best choice is to select from a[7] , because soon you are going to reach a[7] , and its all potential value will be destroyed , once it is destroyed by prefix technique ,so better completely use a[7] before destroying it.

Oh yes, I got it. Thanks

Why is it necessary to find the first greater than 1 segment ... If I find the largest segment everytime and reduce it.. won't it work ?

No. Check this out => Comment

In case of prefix length = 1, instead of looking for the first length > 1, I looked for the largest length substring of the same value and reduced it's length by one but I got WA using this approach. Can you help me? My submission

Problems just awesome in this contest.

Yes,brother.thanks.

How to solve E?

Have an vector of stack of size 26 where u push each character to respective bucket initially. Now we know that the first character has to reach the end. But the important thing to notice is that only the last occurence of the first character is required to reach end to save operations, that is why we maintain a stack to get last occurence.

Now if we know that the last occurence of ith character is at position j, we also need to know how many of the characters from j to n-1 have already been push to right and for that we use segment Tree/BIT.

So at each postion ans += n — 1 — (no. of char in [j,n-1] already pushed) — lastest position of that char

Heres my Submission

Could you explain why do we need to know the number of char already pushed? And how about handling the chars that has index larger than n/2?

That is because set of character after the last character given in the input are already in reverse and we dont need to consider them. It would be better to explain with an example.

Lets say we have the string: icpcsguru

First move: We move the i at postion 0 to the end and get cpcsgurui. moves=9-1-0=8

Second move: We move the c at position 3 to end(after u) -> cpsguruci. moves=9-1-3=5

Third move: This is the important one. Here we move the p at position 2 but the moves wont be 9-1-2, instead it would be 9-1-2-1=5.

This is because the c ahead of p is already moved to end and this is exactly why we need a range query from j to n-1 to get how many are moved to end.

Oh I see it now. You were like try to bubble the chars from the left to right, one by one. Thanks.

Very nice solution . I have written the solution code based on the approach told by you . My submission : https://codeforces.com/contest/1430/submission/95353036

Why did you not bold 'prefix' in D :(

delete the maximum lengthprefixconsisting of the same characters...Ah, damn it... This is where most of us went wrong. Most of us did indeed solve a different version of this problem correctly.

I tried for over 1.5 hrs but couldn't come up with a solution for the "different version" of the problem.

wait, I missed that too... :(

I misread B and thought that only adjacent swaps were allowed.

(Sorry for the edits)

Helps for Problem D please

precompute an array of sizes of chunks of 0s and 1s for [0, 0, 0, 1, 1, 0, 1, 0, 1, 1] -> [3, 2, 1, 1, 1, 2] now in each step first chunk would be removed anyway but we need to remove 1 other element before that, choose the chunk either after it or itself that has size > 1, if theres no such chunk remove the last element

Since we never delete a chunk of size 1 from middle, it is ensured that two chunks are never merged. Hence we will always get the optimal answer.

I used nearly the same approach. But when there is no chunk of size >1 then I just add (remaining unprocessed elements+1)/2 Here is my submission.

I actually did this exact thing .. You would see if you go through my last two submissions .. I now want to figure out where it went wrong

Upd : I got the bug .. actually I thought to use the first non one value and hence used a priority queue to keep the minimum next indices avalaible for operation only to realize now that we get a maxheap as a default.. my bad.. Got the same code accepted Now. Thanks for replying and help anyways :)

What on earth is Test Case 2 for D ?

UPD : my greedy fails for 5 10111, ans should be 3, not 2. Optimal way is to take 5th character first.

Damn, it seemed so obvious, the guy who set this problem is pure EVIL!

Exactly...Here is my approach.....

If prefix has more than 2 same characters then 1 operation consists of removing the first character and then the remaining prefix...this way we delete the minimum we can after every operation. Also if s[i]!=s[i+1] then we jump to s[i+2] after deleting si and s(i+1). This can be proved to be true by some casework...but I dont know why this greedy approach is failing.

well i understood why this approach is wrong in last second consider 101111

according to ur algorithm answer is 2 ! where u can get answer 3 by erasing 3 on first operation and erasing 2 on second operation and then erase 1

so 3 operations in total

My solution gives 3. Can you please have a look at it?

I stress-tested my solution and got some tests where my code fails:

Spoilerthere were few more tests, but I think it's enough

My solution idea is same but it fails on test-525 . Can anybody tell me which test if fails ?

1 7 0100010

You can try this case, my solution was giving wrong answer on this case. May be you might get your mistake. The correct answer is 4.

I figure what's wrong when my first submission

I maintain two index, the head and the index of number bigger than 1.

It's important to notice that the second index must >= the first index.

this contest actually had a really good combination of problems ! neither too easy , nor extremely tedious . Thanks BledDest for the contest

What hurts more?

aBREAKUP

bGETTING TLE ON TESE CASE 41 DURING THE CONTEST

If you use O(n^2), you will surely get TLE. I also copied code from GFG though and get TLE on test cae 41 :P https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

What's the point of getting a positive rating when the code and logic aren't yours in the contest!?

You guys are copying? ://

Getting TLE on test case 41 while simultaneoulsy on call with GF with she breaking up wid ya at the same exact moment or vice versa whatever minimizes your mood. My guess is you probably got lucky with both events not happening at the same time....If even luck did not favor you on that...then oh boy.... that oughta hurt (In Matthew Mccounaughey's voice)...good luck xD.

This is what happens when you are already overthinking and you start to overthink your overthinking. PS: You are funny!

Yeah I am watching Sherlock these days, and my tone..be it in any chat..whatsapp,CF,CC,CSGO,twitch,among us(xD)... etc sounds so deductive and caseworkey lol. Thanks btw.

cringe ngl

please tell me why my answer for B is false this is my answer:

## include<bits/stdc++.h>

using namespace std;

int main(){

}

I think if n=1 then your a[n-2] will become a[-1]. Maybe that might be the mistake. You should only write a[n-1] as the answer because a[n-2] is already zero.

n cannot be 1 according to given constraint in problem. (1<=k<n ..)

try using long long instead of int, integer overflow takes place if you take int.

Is there a greedy approach for D ?

Used two pointer concept and it passed!

why my solution got accepted after changing int to long long https://codeforces.com/contest/1430/submission/95208979

overflow may take place when int is used

lol he already knows that xDDD...I guess he is asking there is no reason to overflow here and yet it is getting WA'ed.

yes exactly xD

are you using multiple accounts? because you do not have a submission using int, nor did you get a wrong answer on this problem.

please click on show unoficially you will see it xDD.

use this

`#define int long long`

would be life savingthanks very much :)codingkshatriya

Anyone can tell how to solve F & G ?

F is DP

$$$dp[i][j]$$$ = minimum cost (in bullets) to beat $$$i$$$ rounds (and start the next round) with $$$j$$$ bullets remaining in your magazine.

Note that since $$$j \leq 10^9$$$ you should use a map/associative array for that dimension.

The initial state is $$$dp[0][k] = 0$$$. Each state can be the parent of up to two states, one with $$$j < k$$$ (no reload after round) and one with $$$j = k$$$ (reload after round; only transition to this state if you have enough time). A state may also "dead-end" if it is impossible to beat the current round from it; if all states dead-end the answer is $$$-1$$$.

This fits in $$$O(n^2)$$$ or $$$O(n^2 \log)$$$ as the number of states increase by at most one each round (the $$$j = k$$$ state may create a new $$$j < k$$$ state, while the $$$j<k$$$ states only "move" about or merge into the $$$j=k$$$ state)

Can anyone tell me why this O(nlogn) solution for E gives TLE at test 41 solution link

vector insert is O(n)

Okay. Thanks!!

D was EVIL :(

DEVIL indeed!Is there any other way to solve E without using fenwick tree/ segment tree ?

count inversions any other way (merge sort , set -order_of_key)

use pbds if you are using c++, 95257988

codingkshatriya can you explain the logic of E.

For each position, we know what caharacter should come there, we have the initial string, so each time it is optimal to move that character which comes first, for example cdad, first position should be occupied by d, there are 2 d's but it's optimal to move the d in the second position to first, but string changes when we do that, it becomes dcad, if you notice all elements before the moved position, their index increments.So we can store the positions of all characters and every time we just have to know the changed position, which is just the number of elements greater than the current position that have been already moved, we can solve it using pbds ordered_set

It can be done without segment/fenwick trees. Because its a character string, we can keep prefix/suffix frequency arrays for both initial and reverse strings and maintain the answer. You can look at my code for reference.

adderall Very easy solution: https://codeforces.com/contest/1430/submission/95314914

hi, can anyone tell me, what is hacking? and did it give score also?

not in educational and div.3 rounds.

Does that mean an

unsuccessfull hackwould have no effect on yourfinal score?In Educational and Div.3 rounds neither successful nor unsuccessful hack gives you extra points. But in regular Div.2 and Div.1 you get +100 points for each successful and -50 for unsuccessful hack.

Once the 2-hour problem solving round is over, participants have the option, to see the solutions submitted by other participants and try to generate possible inputs, upon which these solutions might end up giving incorrect outputs. This is what hacking means. All of this has to be done in a 12-hour hacking phase just after the contest. Once this 12-hour phase is over, solutions are re-judged based on all the hacks generated. Hope this helps!

Can C be solved using heap? This solution gave TLE but I just to know if there is any way to optimise it or if it can't be solved using a heap. This solution without heap worked correctly.

I would give u a better approach .. Just use the max 2 possible values each time and then work yourself on a case or two. You would get to know that you would always end up at 2

The second link is using the solution that you mentioned. But I never thought about it always ending at 2. In the cases that I tried it ended at 2 but I thought that it would increase for bigger cases. I just want to know if it can be done using a heap.

https://codeforces.com/contest/1430/submission/95294366 This solution uses heap taking the largest two elements every time and insert their ceil back into the heap for total of n-1 times .

Thanks, I solved it using heap yesterday.

i believe x[2:] is costly operation(tell if i am wrong) and yes the approach is right here

Yes! i used a priority queue and got AC

I solved it after I read your solution. My mistake was using a heap but not using the heap functions. I was using list operations and performing multiple heapify. Using heappush and heappush performs heapify on its own. Thanks a lot!

First I convert 1000111000 to [1,3,3,3] then if the chuck is greater than one than i add one to my ans , if the chuck is equal to one than i remove one from the biggest chuck remaining , 95255021 can someone point out what's wrong with the approach

An example test case is -> 1 13 1010010101111

Your approach gives 6 while the answer should be 7

The problem is that we should not remove from the biggest chunk because we may exhaust it early. The ideal way is to remove from the first chunk which is greater than 1. That way we can optimally utilize the chunks. In the example, it exhausts (1111) which could have been used for 6th element while we could have reduced the (00) for the 1st element.

thanks man. should have seen this. at this rate someday my rating will be lesser than the number of contests I participated.

Prob C hurts me a lot. I even don't have time to catch up Prob D.

Dude I overcomplicated my C because I thought the solution to C should not be so obvious. Now I see that a brainless greedy works. -_-

I also overcomplicated C .... took 1 hour.

but what hurting me more is TLE on testcase 41 for problem E.

so sad

My screencast of getting 7th place [assuming I don't FST], along with solutions to all problems is being uploaded to my youtube channel. Youtube should finish processing it in 20-30 minutes or so. If you want to see it as soon as they finish processing, you can turn on notifications. Good morning and thanks to the authors for the cool problems! :)

I love the "Good morning everybody" you do at the beginning of your videos!

Sorry for asking, but what's FST?

failed system tests

Thanks!

ur solution for E was just awsome or maybe how u teach.

Nice Problemset. Was E a standard question of Fenwick Tree ?

https://www.geeksforgeeks.org/number-swaps-sort-adjacent-swapping-allowed/

Why is this brute force wrong? (PROBLEM A)

It is not wrong in a mathematical sense. It is just to slow.

when there's 1000 cases of n = 4, you will get TLE

No I didn't get a TLE on this, I got hacked instead.

Yeah, you can get hacked if someone puts those test cases.

I got hacked on that. Feels really sad.

For some reason, I'm really bad at educational rounds...

My last four ed-rounds

And this one will be even worse (expected -64)

The problem for loosing rating in this contest has huge role of your mindset saying that "I will loose rating from previous pattern ,making you feel pressure and under pressure u don't do well". Thinking it to be any normal contest and being cool , you might have performed better.

Sweet

Slightly over an hour since the end of the contest and already 500hacks.

I'm not complaining though as it may seem. Just noticing a funny fact

yeah most of them are for problem A, people have forgotten to break their nested "for loops" (those who have used this looping concept). most hacks for TLE in that

Anyone else used Dp for problem A? XD

I did the recursive sol exactly as yours

I thought about something like this initially. But decided that it is quicker and less error-prone to write brute-force that should converge quickly

A lot of successful hacking attempts for A & B. It's sad.

My solutions got hacked in both. So sad.

Do you have any reasons why we got tle in B Especially java users? while looping backwards*.

Trying to figure out the same as it happened to me too :(

for java users B — Arrays.sort() was the issue

But many has used that method. Just the difference I found is that the accepted one is one in which they are looping from i=0 to k .

Idea is correct. but Whoever has used Arrays.sort() in java then you can hack that solution by $$$TLE$$$. Arrays.sort() is O(n^2) in worst case. google for that particular testcase and you can hack all java solution which uses Arrays.sort();

Thanks ..I came across this after reading your comment.

Does anybody have proof for the fenwick tree solution of E. Why wouldn't there be a case where we need lesser number of moves than taking it to the last possible position.

So, here is my solution : First take the reverse of the given string and try to get all characters into position starting from the last.

Some sort of proof for this : It is always optimal to choose the rightmost matching character in the original string to swap and get to the final intended position. Assume it takes X moves for rightmost character to get into final position. Now any other character Y will take X + dist(rightmost character, Y).

Now, on why it is better to start fixing from the end of the string : When we try to fix some position before fixing the positions to the right of it, then this character might get displaced once again when some other to the left of the fixed character needs to go to the right of it.

is it necessary to move from right to left

i reversed the string and tried moving from left to right

getting wrong answer on test 41.

It should work. The logic may slightly change though like you must take the leftmost matching character instead of the rightmost etc.,

Hi thanks for the reply, actually i was using int instead of long long.

I want to know D's solution, shouldn't it be traversal string simulation operation? I have seen a lot of AC codes, they all have found a certain pattern, can someone tell me this pattern?

Let's say there are various segments of same elements, so one thing that you can see clearly is that you don't want to merge two segments, right? Now if the segment at front has size 2 or greater you can simply delete one of its element and then delete this segment. But what if our segment at front has size 1. In the first operation you want to delete a number other than this segment, so you can do it by deleting from any segment after this and size greater than 1. It will basically create a suffix with ones only and you just want to find the size of this suffix. the answer will be number of segments initially — (suffix length/2).

mafailure Can you please explain the solution w.r.t to 1000100 ?

If I first take i = 7 string becomes 00010,

Now if I take i = 1 string becomes 10

Now if I take i = 1 string is empty

ans is 3, but it should be 4, can you help me with that?

make a vector of lengths, in this case it will be v={1,3,1,2};

now first length is 1 so we need a length>2 ahead in the vector or the last length==2 if any of the condition met then we can reduce that length by 1

if both these conditions are false then we have to forget about a length

for clarity see this https://codeforces.com/contest/1430/submission/95243326

what do you mean by "last length is 2" ?

if we encounter with length==1 then we need a length of 3 or more or the last length 2 or more

so in 1000100 I can take i = 7 right? since last length is 2

hmm

but that would leaves us with string 00010, now when i just take i = 1, string becomes 10, and now the answer is only 3, but when I take i = 2 in the first operation it can become 4, so how does it work ?

here our vector of length will be v={3,1,1} now first length is 3 so it is safe then we have 1 and none of the condition are met so we have to drop the last length that is so ans will be 2.. idk what do u mean by i

pinged in DM

Not noticing the unusual time made me miss the contest.

10 downvotes for expressing my mistake and feeling sad for missing a contest, ouch.

Can someone explain the "flow" solution for G?

I only know the bitmask dp solution.

Can you explain what the bitmask dp solution?

Yes.

You can find that the number you use can be convert into $$$0,1,2,3...k,(k\leq n)$$$.Then you can add node in increasing order of $$$a_i$$$.When adding a node you must check whether this node can be added.

The time complexity is $$$O(n*3^n)$$$,but in fact the states are much less.

This is the code during the contest: https://codeforces.com/contest/1430/submission/95237357

However because of its huge constant, it's hacked after the contest by the test:

18 0(time: 3000ms+)

But we can reduce the enumeration of the maximum $$$a_i$$$.Then it can pass.

Ac Code:https://codeforces.com/contest/1430/submission/95257898 (331ms)

In fact, problem e is not difficult, but I don't have enough time to complete it. The slow hand speed is also one of my flaws. .

My solution is a perfect

O(N) solution. But it got hacked for TLE.Problem Aof this Educational round 96. 1430A - Number of ApartmentsKindly look for yourself and tell me why this happened@ BledDest adedalic fcspartakm Submission : 95203970python is too slow, change to c++

Bro I submitted in PYPY3, that's supposed to be faster than Python. And since the complexity is correct there shouldn't be any problem in the language right? Like the setters should make sure it gets submitted in all languages if the required complexity is fulfilled

Your code is taking 1247 ms for t = 1000 and n = 1000 for every t. Try it in Custom invocation.

Exactly my point , given the complexity is correct which is O(N),It's showing TLE ie time taken is above 1 sec.Which shouldn't happen for the given values.You should calculate dp once for the max value of n = 1000. But you do calculate it every time.

Yes, I thought about ,but considering the situation for T = 1000 and N = 1000 , it should be quite evident that O(N) should work

This solution is O(tN) at best and on each iteration it creates at least six three-element dictionaries. Six million three-element dictionaries are not free

Dictionary with 3 elements can be considered as constant, it occupies O(1) complexity , how does it matter??

Hey, You can check out my

PYTHON TEMPLATEfor making your Python code run faster.Also, I have been a Python Coder for quite some time now, but sometimes even I have to submit a program in C++.

Mentioned below are some areas for which you should

notchoose Python as a language to code your solution :(1) Recursion with a depth > 1000.

(2) If you need to apply lower_bound or upper_bound on a set as Python doesn't support it.

(3) String problems with the length of string > 1e5 and your solution is supposed to have a time complexity of nlogn.

Hope this helps you.

I was a Python coder myself. Normally PyPy is faster, but once I submitted a problem in PyPy and it got TLE (the same code was later accepted in Python3). So I had to decide which to use where.

Even though a solution is O(n) and optimal does not guarantees an AC in every language. Internally Python is slower than C++ and a more efficient solution in Python

mayget TLE whereas a less optimal solutionmayget an AC in C++. Even though there is a time relaxation in the background for some languages, that is not enough to get an AC.Therefore sometimes it is written that_ a solution is not guaranteed in every language_.

Can somebody prove problem D solution ?

In problem D :

Why is it "always" optimal to pick just next chunk with more than one value and not any other chunk with more than one value , whenever we encounter 1 ?

If you don't choose, the just next valid chunk will be erased at some step, thus not better than the solution.

Thanks. This makes sense.

Can somebody prove the solution to D ?

If someone has got a little free time, can they mind explaining to me dp approach for solving problem A. Thanks.

A dp solution for such a problem would be based on the observation that if we got a solution for some n, then we can simply construct a solution for n+3, n+5 and n+7, each by adding that number to the set of numbers in the soluttion.

So start at zero and go up to n. Foreach number if there is a solution, construct the next three soulutions and store them.

This will finish after n loops with solutions to all numbers in range 0 to n.

where are the editorials?

How to solve D using Binary Search ? It has BinarySearch tag.

Is there a way for java users to solve problem B, because I used Arrays.sort() and got hacked. Collections.sort() is even slower. If we use a priority queue then it has insertion and deletion time complexity of NLog(n) and is a min-heap so it will only work for some cases. So what is the alternative??

Use mergesort Or sort Array of Object instead of Array of Primitives. Arrays.sort() uses quicksort for which worst case time complexity can be O(n^2) (only in case of primitve data type).

HarnoorSta7 has already pointed out. So, we got a TLE because Arrays.sort(int[]) uses quicksort which can have a worst case complexity of O(n^2) when the array is almost sorted. Now Collections.sort(List) is indeed slow because of non-primitives but it is still O(nlog(n)) in worst case because it uses Tim-sort instead of quick sort. So, I think it would not be a TLE if we used Collections.sort(List) in this question.

Thanks for the link. Java was a lie for me. All the java accepted solutions I saw are using Arrays.sort() for int. Let's see how many java users survive for question B after final testing is completed.RIP java users!!

To avoid worst case of Arrays.sort() function for primitive data types which is O(n^2), first shuffle randomly the elements in the array then use Arrays.sort() function. The function which I use to sort the array is-

static void sort(int[] A){

Can somebody please tell me why my solution on problem A doesn't get TLE on a test with 1000 of 1's in input? This is kind of a max text and it's not even close to TLE (around 300ms).

But if I have 1 as n, my fors don't break at all.

When u get the answer and b = false, the both loops will break coz of "&& B" in loops.

Yes, but if the answer is -1 it wont

You 're right, My apologies I was wrong. Hope you get the correct answer soon.

When used "long long" instead of "int" in same code got TLE and don't know why. 95291943

I'm almost sure the intended solution for problem G doesn't involve Simplex, but if you know this method and you prove (or assume :P) that the coefficients found by the algorithm are all integers, you can get a really quick accepted.

Also, this solution should work fast enough even if $$$n<=100$$$ and $$$m<=n*(n-1)/2$$$

95241114 Why is this solution showing unsuccessful hacking attempt even though it shows compilation error in online IDEs?

just so you know, in hell exists a special place for A-problem hackers!

Nd there are some dumb people like you whose A-problem gets hacked...lol

It saying the green pupil. just so you know it is infinity number of the way to hack every problem A solution.

95295302 Can someone tell me how to optimize it to have an AC. This gives TLE. I saw solutions of other people with the exact same method having AC. Please help! Thanks!

The problem is Arrays.sort() I think. It uses quick sort, whose worst-case time complexity is O(n^2). Try using Collections.sort() instead.

After reading the first 2 problems, I am pretty sure the problem setter was watching the water jug scene of Die Hard 2 while writing these problems.

Can someone plz help me why my solution shows TLE for the Barrels problem of today's div 2 B Here's the link-https://codeforces.com/contest/1430/submission/95296320

Probably Arrays.sort(arr); is the problem there.

But i saw others code and they have done the same.The only difference between them and mine code is that they used a for loop to count the summation and I used a while loop. Can u plz tell why it's happening.

https://codeforces.com/blog/entry/83538?#comment-709446

Its a specific hack for the java sorting function. It makes it really slow, something like O(n2) if Im not wrong.

https://pt.wikipedia.org/wiki/Quicksort

Yeah, it says that the worst case for Quicksort (java's sort) is O(n2)

Ok..Thanks for your kind response.Will definitely look into it

The worst case can be converted to average case if we shuffle the array before sort. All arrangements will have equal probability and worst case will be as rare as any other case. This might be helpful.

Me after using x / 2 + x % 2 in rounding up in the questions

Please, can someone proof C solution? Thanks.

We just need to proof that an answer less or equal to 1 cant exist. If (a+b)/2 rounded up is 1, then 1 <= a+b <= 2. Its impossible to get a+b <= 2 if n>=2, so the minimum possible answer is 2.

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

As last contest. This way is really better. Thanks for improve CF continually.

Can I ask a question? What does it mean to remove cheaters? According to my understanding, cheaters should be counted as zero points and kept in the rating change list.

wait removing cheaters ? are you removing them manually or what ?

No idea why my submission for Problem B gives TLE (got hacked in the hacking phase)

Can someone please check?

Please upload the editorial..

In Problem A I used two pointer method.Like this

But still got WA .Why?

That loop stops to early

`while(j<k)`

It should be something like

`while(i*3+j*5<mx)`

because there is no reason why j must be smaller than k.And that is, because it is basically no two pointer problem, but a brute force.

editorial?

Where are the editorials?

Editorials Please BledDest

When will the tutorials be published?

Are some test cases intentionally left out for such contests?

Is there an available editorial?

Is it possible to get all the test Cases for the problem from Somewhere. My Solution for D fails on 149th input of test case 2. If not it would be great if someone provides some good cases for checking the fault in my code . I have tried all the cases given in the comment section and all the outputs(from my code) have matched with their expected output.

yes , is there some way to download all test cases ?

It's a bit hacky, but you can sniff the test case by hardcoding something like

`if (test_case==149)`

and print it out in a submission.It was a Cool Idea , I got the failing testCase and my error as well. Thanks a lot

Why editorial is not published yet?Look Carefully, it's thereVery happy to get First-AC at problem E&G.

Problem E was awesome.