Hello Codeforces!

On Jan/26/2019 18:35 (Moscow time) Educational Codeforces Round 59 (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 extented ACM 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 and me.

Good luck to all participants!

**UPD:** You can discuss the problems after the contest on a local Discord server.

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

Hello Codeforces!

A quick reminder to check out the Hello Muscat Programming Bootcamp!

Every day, both the Hello Programming Bootcamp and the Moscow ICPC Workshop will be competing simultaneously, 4,000 kilometers from each other — our camp will take place in Oman, from March 9th to March 15th, 2019 — registration is still open for this unique opportunity, so be sure to give it a look, we would love to see you there with us!

And, don’t forget that Harbour.Space University’s opportunity for a fully funded Master’s in Robotics programme scholarship is still open! Head over to their website to see the details, and apply before the registration date closes.

Congratulations to the winners:

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

1 | V--gLaSsH0ldEr593--V | 7 | 198 |

2 | Radewoosh | 7 | 358 |

3 | Rzepa | 7 | 396 |

4 | eddy1021 | 6 | 170 |

5 | spacewanker | 6 | 175 |

Congratulations to the best hackers:

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

1 | _bacali | 39:-44 |

2 | Kiri8128 | 8 |

3 | tymo | 5:-1 |

4 | CoodeForces | 4 |

5 | Sevlll | 5:-4 |

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

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

A | V--gLaSsH0ldEr593--V | 0:01 |

B | neal | 0:02 |

C | neal | 0:05 |

D | V--gLaSsH0ldEr593--V | 0:10 |

E | DankShadow | 0:10 |

F | V--gLaSsH0ldEr593--V | 0:44 |

G | Kalam | 0:17 |

**UPD2**: The editorial is out

Clashes with Topcoder SRM. Please prepone it by 30 minutes.

Also clashes with CodeChef Lunchtime.

It's surprising that two contests promoting the same bootcamp are clashing.

clashing with codechef lunchtime please delay it.

Clashes with indian entertainments

Clashes with Educational 59

中国玩家修仙场：）

Clashes with CodeChef lunchtime. Please reschedule.

Happy Republic Day Indian Coders!

thanks!!

like who cares to be honest?

All Indians in this Codeforces Community! ;)

and who cares about them?

Codeforces ! and you don't have to!

i strongly believe they don't.

Please make contests at more diverse time frames -- times like 18:35 MSK are really unfriendly for students living around UTC +8.

nice meme bro

Hope that will be a lot of hack today xD

I try to hack the problem B&&D , but I failed

they have made good pretests today

They have made bad problems too

yeah that's for sure xD

Nice picture though~ :D Is that the campus?

Give me a purple name plz...

It shows the possibility of being a good hack :D, hope every one of us succeed!

Want to Be a Candidate Master... So everyone Good Luck && Higher rating... RP++

Clashes with clans

oh my the name hints it will have pointless math again. god, can't you keep these two things sepparate? is it so hard to understand that math has nothing to do with programming? it doesn't help you get better, it's just useless.

only people who want to feel better for themselves thinking they've actually accomplished something like math in programming.

so with this said let's hope for a math-free problem set.

if it doesn't have any math i will surely get out of expert. can't wait.

last minute smart move: i'm not going to take part in this contest because i know from experience it's going to be a lot of math. not worth taking the risk.

CodeForces OR CodeChef???

Both.

Fuck problem statements. I'm done.

I don't know why, but at last contests problems are easy or hard, there is no medium ones.

they are math problems which are useless. it makes them pointlessly harder, that's the reason why. don't bother...

For the question D, if i=1 and x=4 then [i/x] gives 0. This index does not belong to the matrix B What is to be done then ?

There is ceil function, so ceil(i/x) gives 1.

nice problems ^^ , how to solve E ?

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1500

Almost the same logic XD

What's the DP state though?

What is the solution for this one? The constraints here suggest that

n^{3}is possible.For the UVa problem in the link: Let's calculate

dp[l][r][len] — the most points we can gain if we do operations ons[l] tos[r]with the same. Letlencharacters ass[r] attached at the back of the stringpbe the leftmost index satisfings[p] =s[p+ 1] = ... =s[r] andqbe some indicies satisfings[q] =s[r] ands[q] ≠s[q+ 1].Then we can list the dp equations:

dp[l][r][len] =dp[l][p- 1][0] + (r-p+ 1 +len)^{2}— if we clean all blocks fromptor;dp[l][r][len] =dp[q+ 1][p- 1][0] +dp[l][q][r-p+len+ 1] — if we decide to clean blocks fromq+ 1 top- 1 first and the others at last.For today's E problem just substitute (

r-p+ 1 +len)^{2}with the most points we can gain from the string with same characters of lengthr-p+ 1 +len. This can be done by another simple dp.I know the constraints suggest a

O(n^{3}) solution, but maybe many states cannot be approached? I desire the proof too ><contest was so easy :D

How to solve D ?

Mine's using sliding window. Keep extend our window when the string in the next row is equal to the string in the current row. Keep track all size of the windows and find the GCD of all windows' size

Nice idea, but I think you should do the same thing on columns too.

Basically we need to check over all x such that x is factor of n,for a given x we need to check all the [n/x]*[n/x] sub-matrix whether they contains equal element or not, if a submatrix contain equals elements either all of them equal to 0 or 1 i.e sum is either 0 or x*x,we can easily check sum of a submarix with the help of 2d-prefix sum.

Thats O(n^2*sqrt(n)) in worst case?

Nope, a number can have max of n^1/3 factors.and for each factor we are doing only n^2/x^2 work so actual complexity would be near to n^2 with some constant.

n^2(1/1^2+1/2^2+1/3^2+...+1/n^2) < n^2*(pi^2/6)

https://en.wikipedia.org/wiki/Basel_problem

It is even less because you only check the devisors not every number.

if you just check from all the numbers from 1 to sqrt(n) for a divisor of n, then this is the complexity in the worst case.

Don't know if this is the indended solution, but I did this:

Convert hex to binary and store it into a matrix. Then you try each divisor of N as x in O(N*N). At most, N has 60 divisors (N = 5040). I've executed this solution with the worst case in codeforces custom test and it seems to pass, but who knows...

What is worst case in your opinion?

You are trying to hack me haha. Find it out yourself

I think that 5040 and whole plane in F will hack you, however im not doing it. If im not mistaken you gonna do ~25kk*60 operations.

I've tested that case during contest, nothing happened, no TLE. Was thinking in solving it with binary search but that failed so i resorted to this.

How is it not giving TLE when doing > 1.5*10^9 operations + big input?

You forgot that checking big x is not O(N*N). It is O(N*N/(X*X)). So the solutuon is way faster.

Upd: I'm sorry I haven't checked your submission. Yes, your solution runs in O(N*N*Number of divisors)

My code checks every x in O(n*n)

So how is it doing 1.5*10^9 operations in time limit?

I've seen an O(n) simple loop when N = 10^9 and it executed in 0.7s. It seems I do a ton of operations but most of them are just comparisons

For that to work, the time limit of the problem should have been 1 sec. The solution having complexity O(N*N*60) gives 1578ms and the one with prefix sums (optimised) gives 400ms.

The problem setter could have given it some thought and made it a better problem.

Mine runs in 0.7s

https://codeforces.com/contest/1107/submission/49014233

How to solve D?

Find all divisors of n. Then for each divisor, divide the matrix into the dXd submatrices and check all the submatrix has similar elements (1 or 0). Find the maximum divisor that satisfies this.

I have used binary search to find maximum divisor which satisfies x-compression,but it fails on test 4,can u explain why?

if linear search is used to find maximum divisor then it gives AC.

Binary search wouldn't work as it is not a monotonous sequence.

The answer to this is 3, and both 2 and 4 don't satisfy as an answer.Eg:

OK Thanks

hahau

I also did the same, but here our assumption for binary search to work is that if the current_divisor is not answer then the answer is less than the current_divisor but this is false answer can be greater than current_divisor.

## if this is the case then the case 1 given should give ans "2"..2 x 2 matrix is having all equal elemts and 2 divides 8 too...so why the ans is 1?CAN U EXPLAIN THIS??

Consider first two submatrices starting from the first row:

11

11

and

10

10

Here the second submatrix doesn't have similar elements (combination of 0 and 1). So 2- compression isn't possible

means we have to check all possible sequencely (n/x)*(n/x) matrix ??..i thought the first one accrdng to ur ans...i am confuse in submatrices...which sub matrices we have to take??

Yes, you have to check all sequential submatrices.

thanks.

what was the state for the DP in problem E?

I think, (sum_of_current_length, left_index, right_index), but I'm little scary about time limit of my solution

Is D solved in O(no.of divisors*n*(n/4))

It's

My algorithm solves it in O(n^2). Idea: count the prefix sums on the matrix in O(n^2). Then, for all divisors (div) split the matrix in small squares of length div and check if it each of them has sum div**2 or 0. Each iteration works in (n / div) ** 2, but we should take into consideration that however many divisors of n there are, the resulting number of iterations must converge at appr. 1.5 * n^2 (n^2/1 + n^2/4 + n^2/9 + ...), therefore the time complexity is O(n^2). Correct me if I am wrong.

mine is O(n*n*sqrt(n))

I have a much neater solution.

Find all lengths of consecutive segments with same character. (like 0001111110 then you count 3,6,1)

Do this for both vertical and horizontal.

Answer is the gcd of all the lengths.

O(N^2), because you can just determine whether a segment of this length exists, and so gcd would be called N times at most.

Sorry, I'm dumb, and you're smart, so I don't know why this works. Could you explain? orz

To me, G seemed like a divide-and-conquer after assigning profit to each element as a-c[i]. However, I got WA on test case 7. E seemed like some kind of dp-transitions — can someone provide a hint?

Deleted

I think it's a very bad contests experience. The description is long and difficult to understand. Boring problems and difficulties of code. Some data area is not reasonable enough.

lengthy code? for which problem?

For me D was very long (though my implementation was sub-par).

See my implementation if you want short and easy to understand code.

I don't actually understand why are people so angry about the statements. There are two main mistakes in our statements, one is not telling about 1-indexation in D and another one is writing that paragraph about skipping hits in C too ambiguous. Can you point out any other mistakes in the statements?

for B. k"th was too ambiguous. i misunderstood that kth root of x instead of kth number which is kth number of set.

root of all numbers in set are equal to x

Sorry, but I don't understand why did it cause so much abmiguity. There is no definition of some

k-th root in the statement, only digital root ofx, which, obviously, does not depend on any numberk. Hence the phrase "k-th root" is something absolutely undefined.Did anyone solve D using Python? Pretty sure I had the right idea but I got TLE on test 4 and I'm wondering if it is because of python's I/O slowness

I used

`sys.stdin.readlines()`

The trick is to use PyPy and read the input with sys.stdin.read(), this will read the entire input as a string. From my testing all other ways of reading input is significantly slower.

Here is my solution running in 1123 ms. The main thing slowing the code down is that I'm calling a function to calculate gcd. By inlining the gcd call my solution runs in 826 ms.

EDIT: If I additionally add a check for if the gcd hits 1, and then print 1 and exit, it runs in 390 ms.

EDIT2: Played around with it a bit more, was able to get it down to 343 ms by pretty much removing the gcd calls.

@pajenegod you are the saviour of all (slow) Python user! I salute you

Thanks a lot man, will try asap :)

You're the boss! (with nearly the same code as in my last python3 submission of the contest)

I looked at the input reading in your code. You are currently using sys.stdin.readlines(). I've been a much bigger fan of sys.stdin.read().splitlines(). It might be quicker, but more importantly removes all '\n'. So I pretty much never use sys.stdin.readlines().

Switching to sys.stdin.read().splitlines() makes one of your solutions go from 1699 ms to 1434 ms. Then I tried to switch from PyPy3 to PyPy2. It went from 1434 ms to 1075 ms. So there's still a lot of things you can do to speed up your solution without modifying anything in the algorithmic part. Don't know how used you are to python 2 but it is usually noticeable faster than python 3.

Python2 is pretty similar to python3 code wise with some exceptions. A small tip is to start out your python 2 code with

and most things will be like how it is in python3.

At my job we use Python2 but I've personally taken the habit to use Python3 because of the fact python2 won't be maintained anymore in 2020. So yeah I know the basic differences between the two languages but I didn't know python2 was

thatmuch faster under these circumstances. Also thanks a lot for the advice man! I'll use these tips from now on on codeforces :)EDIT: I was also using python3 to be able to use math.gcd in this case, but I did a bit of google search and found out gcd was in the

`fractions`

module of python2. Then I read your submission based on my code and I saw you used xrange, I know the trick but did not even think about it... So you're right, there's definitely more I can do to grind some more precious milliseconds!In D, I got WA on test 4, my idea is in each column and each row, I find optimal result (array ln[5204] and ld[5204]). after that, i general all to get answer of this problem, here is my code https://codeforces.com/contest/1107/submission/49020250 sbd help me,pls

You can try to input 12 rows of 0FC(000011111100). The answer is 2 but your output is 1.

I think it's safer to calculate the GCD of lengths of those substrings.

got it! i don't know how to do till see your test, thank you so much.

Deleted

D was a nice problem.

Problem B marks the saddest Google search I have ever done.

u found it on google?

If you search for digital roots, you will find the property that dr(x+9) = dr(x), and hence the solution. Hard to guess the property by oneself.(only for me :|)

thanks

Oct Long18 MINDSUM — Editorial.

Are you that bad at math that you can't figure out that on your own? Sum of digits mod 9 = number mod 9 is elementary mathematics, dude.

That's what I felt after I looked it up. It was very stupid of me.

me: brute forcing 1 to 100 :P

me too :P

how to solve G with binary search?

You can see that each problem worths a — c.

Let's fix gap value. That is, for each i from 1 to n — 1, binary search to find l and r satisfying l <= i <= r, and all x and y satisfying l <= x <= i <= y <= r the subsegment from x to y have the gap value equal to (di — di+1)^2. Now the only thing you have to do is find the maximum subsegment containing i in l...r. It's can be done with a segment tree storing maximum prefix and maximum suffix (very similar technique to GSS1 spoj)

Can anyone please tell me what is wrong with this solution for problem D.

this is my code. i don't understand output is why like that https://codeforces.com/contest/1107/submission/49007458

AFAIK you must not mix cin/cout and scanf/printf if you use fast I/O. Your solution passes if the corresponding command is removed.

Can anyone solve Problem E

Vasya and Binary Stringexplain his/her approach ?whats the ans for C for this test case? 6 3 14 18 9 19 2 15 cccccc

ans how ?

Just make a vector and push_back values as long as it's the same letter then sort the vector and get the largest possible values

i think you also misunderstand the problem.. your ans for test 5 = 68, same with me, check again the problem page, they add explanation and example, the consecutive count will not reset after skip character,

for example: 4 2 1 1 1 1 aaaa

you cant pick 1,2,4 because you press 3 button 'a' in a row

Me ?

edit: nevermind not me

Ya exactly i got 68...

Now i get the problem... Thanks for pointing that out

i assumed for problem C, that if i skip some button, the "consecutive count" for current character will reset.. checking test 5 and re-read problem statement, they add this

Note that if you skip the hit then the counter of consecutive presses the button won't reset.but its ok i just solved the different problem with dp, i think :D

My initial submissions on problem C were giving wrong answer on sample test 1, eventhough on local, hackerrank and hackerearth compilers I was getting answer as 54 for that. Eventhough that solution was wrong but can someone explain why this happened? https://codeforces.com/contest/1107/submission/49004601

When you do k1 = se.size() — k, it gives you error. Since s.size() is an unsigned value, k gets typecasted to unsigned and gives error.

Why does it run on online compilers like hackerrank and hackerearth ide

cpp not greedy only where algorthims, cf'think is totally wrong contest greedy from a to d, why?!

Can anyone explain why this code(in Problem C) is accepted without runtime error?49024911

The core section is:

String in C++ has a null character on the end of it.

Thank you!

How to solve E problems pls?

Tried to make a nice solution of E which should be pretty readable and self-explanatory.

(Instead of using DP-states involving triple indices I just play around with strings and do recursion).

EDIT: fixed the link

49025933 49025845 49026055 49026124

If you look at this submissions you can see there

this submissions were hacked, and I think this should be considered as cheating.

UPD:Now all of his submissions are hacked (also the submissions for problems A and B)I was about to comment the exact same thing. Fake account

This is Educational round who cares about get successful hacks?

I know it can't increase your rating, but it can help you to be in hacking leaders table

So an hack in an Educational can't increase your position in standings?

Yeah but there is a separate leaderboard for hacking

Technically if you hack someone rank higher than you, your rank might go up

It was a great contest,so what about D statement, I didnot understand it, help me pls

I didn't receive an Email to remind me of this round this time, weird

Seems like most people who solved problem E 1107E - Vasya and Binary String did it in . Does anyone know if a faster algorithm is possible?

Why can't I see my rating change?

Because system testing is not over. After three hours you can see the change.

Can anyone please explain the logic to solve E?

anyone knows why this outputs 1 in testcase 4 in problem D

https://codeforces.com/contest/1107/submission/49044759

Is system Testing done?? If not why is taking so much time? If yes why is there no rating change still?

System testing is over. Waiting for rating change

Ideally, How long does it take for the ratings to update in contests like these ?

Get a good night sleep and wakeup, It will be updated.

The predictor does not work well with me

Same for me and i checked for many people it's giving wrong ratings change!!

same

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).I still can't see the difference between the normal round and the educational round... My guess is the difference in problem style. Am I right?

The rank list mechanism is different. The educational round is more focused on concepts and logic whereas normal round is more focused on the right/optimal way of implementation of your logic.

The hacking mechanism is also different.

Aha I got it. Thank you very much!

It is really not a good time for programmers in China, you have to drink a lot of coffee to keep yourself from sleeping:(

In question 'D' I am getting "Denial of judgement" "crashed" at test case 59. can anyone explain why does this happen .

Here is my solution-https://codeforces.com/contest/1107/submission/49348206