Hello Codeforces!

On Feb/12/2020 17:35 (Moscow time) Educational Codeforces Round 82 (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 **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:

*Hi Codeforces!*

*This is not the last call for participation, but we’re almost there. We have extended the early bird discount deadline of Hello Muscat ICPC Programming Bootcamp until this Sunday, February 16th.* *Remember you can request a support letter to present to your university, employer or local companies to sponsor your participation and trip to the bootcamp.*

*We would also like to remind you that if your team is going to the ICPC World Finals in Moscow this June, you can fill out the form below to see if you are eligible for a full scholarship for our Bootcamp (flights not included), and we will contact you within three days to let you know about the results.*

**UPD:** There will be **7 problems** in the round

Congratulations to the winners:

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

1 | tmwilliamlin168 | 7 | 294 |

2 | Egor | 6 | 173 |

3 | ivan100sic | 6 | 174 |

4 | neal | 6 | 175 |

5 | 244mhq | 6 | 179 |

39 successful hacks and 147 unsuccessful hacks were made in total!

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

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

A | Mprimus | 0:01 |

B | icecuber | 0:04 |

C | MylnikovNikolay | 0:09 |

D | waynetuinfor | 0:11 |

E | Mehrdad_Sohrabi | 0:17 |

F | wucstdio | 1:10 |

G | arknave | 0:49 |

**UPD:** Editorial is out

second

minute

hour

day

week

fortnight

month

year

olympiad

lustrum

decade

century

millenium

myrioi

Centamillenium

megennium

decamegennium

centamegennium

gigennium

After this much time my cat can beat tourist

After this much time my program that receives TL1 will terminate.

Yellow people please don't spam !

OK, is it possible to achieve 1900 for me?

You could reach 2000 after this round. Set your dream high.

is it possible to achieve 1300 for me

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).It's time for me to become pupil. Goodbye, my specialist.

Your rating curve is so smooth lol

It's the result of which I'am solving 3/6 all the time. T-T

m=0; c=1400; y=m*x+c;

Codeforces Rounds are very good recently. All the best everyone.

Dear author of statement of problem B. Please learn what's the difference between weather and climate.

Would be better if D statement said "Your goal is to fill the bag

with boxescompletely."It took me some time to understand how the bag and the boxes are related at all.

How to solve D ...?

Process the exponent (i) from 0 to 62 (actually 60, but it doesn't matter)

If the i-th bit of n is set, then find the smallest existing box that is at least 2**i, then divide it by 2 until it is 2**i, creating two other boxes in each division. Then use a box of size 2**i.

Then use all k boxes of size 2**i to create k/2 boxes of size 2**(i+1)

SUM = sum of all Ai. So if SUM < n answer is 0. else SUM = n + reminder. now go from big powers to small. a = 2^k. if reminder>=a so reminder-=a else if n>=a so n-=a else cnt[k-1]+=2 and start iterate on k-1.

Greedy. First for each power of 2 count how many boxes with this number we have. Then start looking at the bits of n, starting from the lowest one. If this bit is 0, we just go to the next bit, and in the meanwhile try to merge the boxes with corresponding size (2^i) to "create" boxes with a higher power of 2. If current bit is 1, we use the box of size 2^i, if possible. If it is not possible, we take the "nearest" box with bigger size and divide it until we get a box of the right size.

You just need to construct all of the bits of number 'n' . Start from constructing lowest bit .for constructing ith bit first check if it can be constructed by numbers smaller than or equal to 2^i . Else you need to divide some number 2^j , j>i and j should be closest to i , see if this is possible .if no for some bit then -1 else answer is sum of number of divisions .

of course above is just rough idea but you can go through the submission and ask if you have some doubt .

submission 70903270

What's pretest 2 of prob/C

1 a

No. My program works for that input but still fails on pretest 2

I think you forgot to output "YES" before the answer.

Did you really missed "YES"?

YES

I think you should check your code in the test case if the string length = 1.

The memory limit on problem F is unnecessarily tight. There's no reason to MLE a solution that uses $$$\mathcal{O}(nmc)$$$ memory.

Unfortunately, we had to put tight memory limits to disallow solutions with dynamic connectivity offline approach.

By the way, which approach uses $$$O(nmc)$$$ memory and cannot be modified to use $$$O(nm)$$$ memory?

It is possible to optimize the memory, but depending on the implementation it can be quite tricky. Currently I'm repeatedly running into either MLE from initializing too many hash tables or TLE from using map.

I'm surprised offline dynamic connectivity is a concern. Shouldn't that just TLE with 2e6 since it's a $$$\log^2$$$ algorithm?

As far as I know, there is a way to write it in $$$O(q \log q)$$$ — but it still consumes $$$O(q \log q)$$$ memory.

I didn't know that. What's the $$$q \log q$$$ technique?

Check this post

https://codeforces.com/contest/1217/submission/60141647 O(Qlog^2) being around 2x faster than https://codeforces.com/contest/1217/submission/60143561 O(QlogQ). Ofc, my constant is shit but the constant in that log^2 is really small!

I see thanks. In that case I'd still expect the $$$q \log q$$$ dynamic connectivity solutions to TLE, which makes it fine to be more flexible with the memory limit.

Simple way to solve it in O(Q*logQ) or whatever but with O(N*logN) memory:

Solve for queries [0, N), [N, 2N), ... and so on, that's O(N*logN) memory and O(N*logN) complexity per batch with Q/N batches so it's actually O(Q*logN)

Why did you want to disallow dynamic connectivity? It's harder to implement than the solution that uses the constraints on $$$c_i$$$ and it's nicer imo.

I tried implementing dynamic connectivity during the contest and indeed it got MLE. I'm not sure if it would have passed time limit since it was really close tho.

Can Anyone Please Tell me what the mistake in my ....code... of problem D..

You should do (1LL<<smth) instead of (1<<smth) because it overflows.

I got a WA at this point too...

Me too....

Why does mine work then?

Now i got my mistake...I consider if any number x is divide by 2 then number become x/2. Then i consider only 1 frequency of x/2 But actually Now we have 2 frequemcy of x/2. I misunderstood the problem..

How to solve problem E？

Edu Round 81: copy ApIO 16

Edu Round 82: copy ApIO 17

Lets revise ApIO 18 for Edu Round 83.

Which problem from this round was copied?

F easier version of: ApIO'17 Rainbow

I don't get it... why do you pro guys always complicate stuffs as hell :-|

Got it, i'm now tring to solve ApIO18 (LOL

How to solve G? I tried something like centroid decomposition + convex hull trick, but I guess it's too slow.

not slow

nvm I'm retarded, I had stupid bug in my find centroid function.

It's centroid decomposition with convex hull trick. As TL is 6 seconds, it should pass.

I tried too, but I had an error in my code during contest that I couldn't fix in time. However, after fixing it it gave me WA, i think I'm bad implementing the dynamic convex hull trick.

What is the dp state of problem E?

For each possible split t1 + t2 of the string t, dp[i][j] = "minimum prefix of s such that it contains non-intersecting i-th prefix of t1 and j-th prefix of t2"

send your submitted code link

gotta say "please", at least...

Is there anything particular in this dp that you don't understand?

I am unable to code but understood what you are saying

Ok, here is my implementation of this dp: 71088000. I did not bother to optimize, so you can take a look at tmwilliamlin168's submission: 70868559, it's more elegant.

First try every split of the string t and then dp[Position of current symbol in the string s][length of the first subsequence] — maximum number of symbols in the second subsequence.

(Mine is kind of weird, maybe there is a better one)

Assume the first subsequence is of fixed length N. Then dp[i][j] = after taking the first j characters of string s, it is the largest length of second subsequence, given first subsequence has length i. If dp[|s|][N]=|s|-N, then we output YES. Now repeat for all possible N. If no such answer is found, output NO.

Submission: https://codeforces.com/contest/1303/submission/70902911

F is so cool, thanks!)

Can anyone explain what was wrong in my code? At my Codeblocks give my code correct output. But after submitted it gets WA. Why? I got 6 times WA on the contest, also 14 minutes have lost :(.

https://codeforces.com/contest/1303/submission/70855140 https://codeforces.com/contest/1303/submission/70857302 https://codeforces.com/contest/1303/submission/70858601 https://codeforces.com/contest/1303/submission/70859156 https://codeforces.com/contest/1303/submission/70860530

...

...

Well, variable 'n' has no certain value in your code.

here variable

nis not defined. Uses.size()instead.Can anyone tell me error in my soln of B. 70896681

i cant understands this, you can see my code

You need to check if the answer is no less than n, as in the following "else" statements. (Input: 10 3 4, Output 9, Answer 10)

Finally!!! i AC 4 problems on Div2!!! (LOL it's 1:00AM here, im going to sleep...

Imagine waking up and half of them had been

hacked, just kidding :PGood night.

my submission for c

please help why this is not working

conditions checked

if size =1 ans is abcd.....

if anyone has more than 2 neighbours answer doesn't exist

if there is no element with 1 neighbours then also answer doesn't exist

please help

If there is a cycle then there is no solution. Checking if there is someone with degree 1 is not enough.

these conditions ensure that

please give a test case that doesn't work on my code with above conditions.

will be very helpful

You're right. My bad.

Your code does not correctly check the degrees > 2. abacad gives YES.

Hack my D solution. 70893301 Please!!!

WA on pretest 5 for B

nvm, made silly mistake of using float instead of double

Better not to use floating point for integer arithmetic.

I was trying to find ceil(float(n)/g)

use (n+g-1)/g which do not need float

can someone find a bug in my code for C 70902882 what im trying to do is create a graph of the given password where to nodes are connected if they are adjacent in the password. then i search for a position to start from(a node that has only one edge going out of it) and do a dfs from there to find if there are loops in the graph. If there aren't I have a found a possible keyboard, if there are their are no possible keyboards

if(a.size()!=2){cout<<"NO\n";continue;} But it can be string like this "abcbdbeba", in set a will be 'a','c','d','e'

ignore previous post, sorry if(a.size()!=2){cout<<"NO\n";continue;} if your input just one char like "e" so size of set a will be zero, but you output NO.

size of of vector a can be 4 if there are two connected component in graph with more than 1 vertices. it can be any even number.

Can anyone explain how to approach problem C?

Represent the keyboard as a graph: letters are vertices and edge between vertices 'a' and 'b' means that 'a' and 'b' should stand next to each other in the keyboard. You can create this graph simply by iterating through the input string and adding an edge between each pair of adjacent letters.

The trick here is that the keyboard can satisfy the conditions iff it is a linear graph (maybe with some vertices with degree 0). The only thing you have to do is to check if the graph you have built is linear. The simplest way to do so is to make sure that, if all isolated vertices are removed, it is either empty or contains exactly two vertices with degree 1 (these will be the first and the last letters of the keyboard), and the rest of the vertices have degree two. If the graph is indeed such, you can output the keyboard by doing a dfs from one of the ends of this graph and then append all isolated vertices in the end.

You could also print the BFS tour instead of using DFS, I think it's an easier solution, though I also did yours.

Well, it does not matter as there is only one next generation vertex every time. In fact, I just did it manually in this case :)

What do you mean by "remove all isolated vertices?" Thanks

for example, you have ababab. All isolated vertices means cdef...z

↑ that is exactly what I meant, vertices with degree 0.

I have a $$$O(\frac{448}{bitset}\sum n^3)$$$ way to solve E. First if we split $$$t$$$ into to parts, there is an easy way (DP) to solve the problem in $$$O(n^3)$$$ for each test case with a fixed midlle position $$$k$$$ in $$$t$$$. As there are $$$O(n)$$$ middle positoins, the approach above is $$$O(n^4)$$$.

To optimise, let

`std::bitset<448>`

be the type of $$$dp[i][j]$$$. If $$$dp[i][j][k]=1$$$, then it means that it is possible to get two subsequences from $$$s$$$ where $$$s_1=t[0-i]$$$ and $$$s_2=t[k-j]$$$. We iterate all characters in string $$$s$$$. If $$$s_i=t_i$$$, then we can update $$$dp[i+1][j]$$$ by $$$dp[i][j]$$$. If $$$s_j=t_j$$$, then we can update $$$dp[i][j+1]$$$ by $$$dp[i][j]$$$. To check the answer, just check if there exist a $$$i$$$ such that $$$dp[i][n][i]=1$$$.code here

Actually, you can perform this approach without bitset. Observe we only need to hold the best possible length for the second part for any given length of the first part. Thus we only need dp[i][j]=best length of second part for each split, so O(n^3).

Submission: https://codeforces.com/contest/1303/submission/70902911

you are right. I only need the leftmost $$$1$$$ in $$$dp[i][j}$$$. sad

I don't understand the calculation for the 3rd example in problem B test case 1. Each cycle of weather takes 1000001 days, of which 1 day is good. As such one can repair 2 units on each cycle. The last two units can be repaired in 2 days, since we don't have to wait for the last cycle of weather to finish. This gives: 1000001 * ((1000000-2)/2) + 2 = 1000001 * 499999 + 2 = 499999499999 + 2 = 499999500001

The answer given in the problem statement is 499999500000 which is 1 less. How can one save a day without ending up with more bad pavement than good pavement?

You can have more bad pavements than good pavements during the days, it's only at the end that you can't.

In other words, one can lay an extra section of bad pavement in some earlier cycle, so avoiding having to lay it at the end. That makes sense, thanks.

it takes 500000 good days and 499999 period of bad days 1*500000 + 499999*1000000=499999500000

Screencast

how do people solve problems that fast QoQ

What is the binary search approach of problem B?

Check this 70858282

Previous contests of codeforces used to be much better. But these days contests have just become a waste of time. Most of the people are unable to reach the questions which are really interesting and actually need to be solved.Easy dp and graph problems need to be included in the contests.

[user:Um_nik]Yes, you should look into this.

totally agree with you bro !! Also , they make 100 announcements during the contests , they better pay more attention while making the questions!

In this contest problem C can solved with graph theory, E is easy DP so what's the problem?

Just to be correct: E is not

easy.adhvana told me it is very trivial and the only struggle was to implement it correctly and fast.

Can anyone please tell me the mistake in my solution for D? 70923522

Please help me on problem C, I don't know why my code runs into error in the test 2 ,I think the logic of the code is right. I use a pointer to record the position, and put ajacent keys into an array called res. Then I print the res and the other keys. Can anyone help me figure out the reason? Thank you very much! https://codeforces.com/contest/1303/submission/70923842

Check if "babacncd" works.

Thank you very much, I forgot this kind of cases, my code is ac

You're welcome.

I am unable to understand the solution to problem D, can someone point me to some article(tutorial/video) where i can understand how this bit wise solution solves?. Thanks a lot in advance.

Let $$$C[2^k]$$$ be the number of boxes with a size $$$2^k$$$. Let $$$Small[2^k]$$$ be the sum of box sizes smaller than or same to $$$2^k$$$ (i.e., $$$\sum_{i=1}^k 2^i \cdot C[2^i]$$$.) Iterate $$$i = 1$$$ to $$$maxbit$$$ of long long signed integer. If the $$$i$$$th bit of $$$N$$$(the bag size) is $$$1$$$, then we have to fill bags with boxes using their sizes are smaller than or same to $$$2^i$$$. It is possible when $$$Small[i] \geq 2^i$$$. But if not(i.e., $$$Small[i] < 2^i$$$), we have to divide a bigger box into the size $$$2^i$$$. Dividing procedure is quite implementive. I hope my submission would be helpful. 70933987

Thanks for your explanation, i need to ponder over it.

Problem G is exactly the same as a problem I set months ago,TSUM2Is it a coincidence?

The fastest system test ever

So is there a tutorial?

So...is there a tutorial?

My friends told me how to solve F and G but I can't understand them :C,I think I need the tutorial to help me :C

Can someone please explain to me why my code runs differently on codeforces from all other ides that I've tried. My code fails the first test case but if you run the code on any ide,It gives the correct output. Here's the link:https://codeforces.com/contest/1303/submission/70891793

It gets wrong answer on my computer, too. :(

The problem said that you shouldn't minus one on

`d.size()`

, the data type of`d.size()`

isunsigned integer, which means you can't get a negative number by doing any calculation. You'd better put it as`pt+1 == d.size()`

, which is equal to your original expression.Attention!

Your solution 70857539 for the problem 1303A significantly coincides with solutions hinatahentai69/70857303, 1412neerujjain/70857539. 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 received this message 3hr ago. I want to apologize about the submission as both of them were mine. I used 2 accounts to submit it. I wasn't aware of the consequences it could hold. I am really very sorry about the wrong doing and wont repeat the same thing again. Please don't block my account :(

If it's the first time you used two account to check your answer, I think it won't get your account banned . As it says in statement, 'In case of

repeatedviolations, your account may be blocked.'.However, you should trust the cheat detection system and don't do that again.

Give us the tutorial, plz!

waiting for the tutorial

Please Release the editorial.

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