Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Edvard's blog

By Edvard, history, 4 years ago, translation, ,

Hello, Codeforces!

Today is the first day of the spring and it's great!

Educational Codeforces Round 9 will take place on 01 march 2016 at 18:00 MSK for the first and the second divisions. You can read about educational rounds here and here. I should again notice the high density of contests and championships.

<This time it wasn't changed>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks.

</This time it wasn't changed>

The problemset again was totally suggested by Codeforces users. The problem А again was suggested by user unprost (be ready to see a long problem statement). The problem D suggested by Denis Bezrukov pitfall. Alexey Chesnokov CleRIC sent the problem E a long ago. The problems B, C and F was suggested by Lewin Gan lewin.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

The problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by the same users who suggested them: unprost, Alexey Chesnokov CleRIC and Lewin Gan lewin. Thanks a lot to all of them!

I hope you will enjoy the problems!

Good luck and have fun!

UPD1: The first part of the contest is finished. You can hack solutions.

UPD2: There are some technical problems. The phase of open hacks will be opened later (several hours).

UPD4: The contest is finished. We will start system testing in a few minutes.

UPD5: TOP3 of hackers:

-Secta-31 hacks

halyavin23 hacks

• +193

 » 4 years ago, # |   +3 Thank you:)
 » 4 years ago, # |   +4 Hello spring and hello another amazing editorial. Good luck to everyone
 » 4 years ago, # |   +34 On one hand i also want to prepare some problems but on the other hand i don't want to miss any CF round...
 » 4 years ago, # |   -23 Looks like A,B will be very easy in this round :/ my guess only :p Dont take it serious guys :D
 » 4 years ago, # |   -25 Any mentor out there?Can anyone help?
 » 4 years ago, # |   -37 I think it would be better if it was rated ^_^
•  » » 4 years ago, # ^ |   +11 There'd be no difference between regular cf round and educational round if it was rated .
 » 4 years ago, # |   0 I'm running in the the contest and I don't know from which files to take the input and write the output at problem F because input.txt and output.txt don't work for me. I know the code is good because with cin and cout it ran until test 8 I think where I got th time limit exceeded. Please help me.
•  » » 4 years ago, # ^ |   +6 How would you pass 7 tests with reading from a wrong file? And how does passing 7 tests mean that your code is "good"? Read from the stdin, not from a file. Your program is too slow apparently.
•  » » » 4 years ago, # ^ |   0 I passed test 7 reading with cin. And i tried to read with fstream.
•  » » » » 4 years ago, # ^ |   0 It's guaranteed that printf() and scanf() are fast enough in C++. And note that maybe your algorithm is too slow.
•  » » » » » 4 years ago, # ^ |   0 Of course my algorith is too slow without scanf and printf and this is the point. It doesn't work when i try to read from input.txt
•  » » » » » » 4 years ago, # ^ |   +12 Ok.
 » 4 years ago, # |   +11 can E be solved without FFT?
•  » » 4 years ago, # ^ |   +6 I don't think so.
•  » » » 4 years ago, # ^ |   +8 aha, then it should be harder than F if the intended solution for F is bitset, IMHO.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +13 Of course it is not intended solution. I'm sorry for that, but I can't increase the size of input, it is already about 67MB. The right solution has complexity O(n 2 logn).
•  » » » » » 4 years ago, # ^ |   +18 It's also possible to get O(n^2)
•  » » » » » » 4 years ago, # ^ |   0 Wow, that's nice! You can sort all edges in O(n 2). I didn't notice it during the contest.
•  » » » » » » 4 years ago, # ^ |   0 Could you explain it?
•  » » » » » 4 years ago, # ^ |   0 Are you sure? The input size is O(n 2).
•  » » » » » » 4 years ago, # ^ |   0 Yes. As you can see a ij < 109 not a ij ≤ 109. It is by the reason of large input size.
•  » » » » » » » 4 years ago, # ^ |   0 I meant that your complexity can't be O(nlog 2(n)) because it's smaller than the input size. Maybe you meant O(n 2 log(n))?
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You are right. I fixed it.
•  » » » 4 years ago, # ^ |   +15 There seems to be bfs solution (let ): let's look for possible sums of k elements, we can get them by starting with k·a 0 and trying to find sums, rechable from this by not more than k replacements of a 0 with some a i. Basically, there is a graph with vertices and edges from each. It is even possible to optimize this solution with bit operations, because all edges are to vertices with sum different from current not more than by a n, so we can use some bit manipulation to find edges to yet not visited vertices in , which amortizes to , where w is amount of bits in processor word, i.e. w = 64.I hope explanation is relatively clear, you can look in my code (and try to hack it, I was too lasy to implement above optimisation after seeing that code works reasonably fast without it).
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Has anyone solved E with just FFT on complex? I get TL6 even with some optimizations.UPD: I did it, 4991 ms :)
•  » » » » 4 years ago, # ^ |   +16 You can raise polynomial P to the k-th power just by raising every value of FFT(P) to the k-th power.
•  » » » » » 4 years ago, # ^ |   +10 But if we raise double in 1000th power, there may be problems with precision?
•  » » » » » 4 years ago, # ^ |   0 I think you can't do that with doubles (too high degree k). But my third solution do that with NTT. Of course it works faster, but it is not correct of course. To make it correct we should get several random primes.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You do all FFTs on arrays of size 106. That's O(k·maxa·log(k·maxa)·log(k)). If you do FFT on arrays of size equal to the degree of polynoms then complexity will be O(maxa·log(maxa) + 2maxa·log(2maxa) + ... + k·maxa·log(k·maxa)) = O(k·maxa·log(k·maxa))
•  » » 4 years ago, # ^ |   +6 This solution seems to work without FFT: http://codeforces.com/contest/632/submission/16447568
 » 4 years ago, # |   +3 I still cannot hack solutions. What is going on? Can anyone hack now?
 » 4 years ago, # |   +11 UPD1: The first part of the contest is finished. You can hack solutions. How? :P Why doesn't the hacking phase start immediately after the contest is finished?
 » 4 years ago, # |   0 cannot hack
•  » » 4 years ago, # ^ |   0 It will be fixed soon.
•  » » » 4 years ago, # ^ |   0 thank you.
 » 4 years ago, # |   0 I can't hack solutions.is someone facing the same problem ?
•  » » 4 years ago, # ^ |   +3 See the UPD2.
 » 4 years ago, # |   0 where can I see editorial to these problems?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Contest is not over yet. Usually the editorial is published as soon as the hacking phase finishes.
 » 4 years ago, # |   +3 Oh, silly me, I thought in 632B - Alice, Bob, Two Teams Bob could take any segment...
 » 4 years ago, # |   +10 F: We can prove that if matrix is MAGIC, after removing all values which are maximum among the matrix elements, the remaining part of matrix is collection of MAGIC matrices.Then we can solve this problem by solving smaller problems recursively. The naive implementation of this idea took O(N^3) times, but good implementation make this algorithm O(N^2 log N).
•  » » 4 years ago, # ^ |   +20 If you do it in reverse order, starting with empty graph and adding edges in increasing order, then it'll work in O(n 2).
•  » » » 4 years ago, # ^ |   +10 Oh, your solution is much easier to implement. (But it requires O(N^2 log N) time since we sort the elements, I think.)
•  » » » » 4 years ago, # ^ |   +20 Yes. But edges can be sorted in O(n 2) if you notice that in magic matrix there are only O(n) different values. So it's not hard to improve it to O(n 2).
 » 4 years ago, # |   0 Can someone explain why am i getting runtime error in the 8th pretest of the 3rd question?Here is the code.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 comparison function should return false when both elements should be considered the samenow your function returns true so it breaks the sort function. To fix that just change <= to <
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Don't read this comment
•  » » » » 4 years ago, # ^ |   +6 Ignore the usual comparator, you are defining a new one. The function should work exactly as operator <. Can you say that A
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   -11 I get you now :)
•  » » » » » » 4 years ago, # ^ |   +6 I am telling you that sort uses < operator, not <= and in rivudas' case it happens that A
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   -14 ignore
•  » » » » » » » » 4 years ago, # ^ |   0 where's the < operator here? Yeah, precisely what I am trying to say is that it's an incorrectly defined cmp function :)
•  » » » » » » 4 years ago, # ^ |   +6 It's because the sort function assumes that when your comparison function returns false, if and only if a is strictly less than b. (In other words, a must be placed before b.)Let's say a = xyz and b = xyzxyz just as you said, the sort function tries cmp(a, b) and got true. That means a should be before b. But then if for some reason it calls the reflexive cmp(b, a) (or transitive like cmp(b, c) cmp(c, a)) and it got true again, there would be a contradiction, thus the runtime error.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Don't read
•  » » » » » » » » 4 years ago, # ^ |   0 Work sometimes doesn't mean work always. You cannot prove correctness by giving examples.And to be more specific why you case might work, STL sort is based on intro sort which uses different sorting algorithms depending on the contents and the size of the array. I made your example fail simply by increasing the size of the array.http://ideone.com/CQt5jE
•  » » » » » » » » » 4 years ago, # ^ |   0 Now its CLEAR!! Thanks, or I'd have lost a good night's sleep lol :)
 » 4 years ago, # |   +2 I've got an off-topic question : how do you suggest new problems ? I mean, to whom do you have to send them ? To GlebsHP?
•  » » 4 years ago, # ^ |   +13 "If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me"you can write to Edvard :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Oh sorry, I didn't read that well. Thank you ! :)
 » 4 years ago, # |   0 Edvard, do you know approximately when the hacking phase will be open?
•  » » 4 years ago, # ^ |   +6 It is already opened. Sorry for late answer.
 » 4 years ago, # |   0 "UPD2: There are some technical problems. The phase of open hacks will be opened later (several hours)."Nour_R when i decided to learn hacking :3 :3
 » 4 years ago, # |   0 How to solve problem E ?
 » 4 years ago, # |   +8 I found someone with amazing short (compare to other which use FFT) code to E:http://codeforces.com/contest/632/submission/16452555
 » 4 years ago, # |   +22 Problem C. C++ solutions using `bool comp(string& a,string& b){ return a+b
 » 4 years ago, # |   0 Hi, I want to know some idea about how to solve problem D :)
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I solved it this way:Remap all values from array co counts arr, where index is a value and value is a count of times the value presented in input. Only use numbers <= M (numbers > M won't be in any possible solution).Cycle from M to 1. This way we pick our L for test.Factorize our L in prime factors (using e.g. Eratosthenes sieve). From factorization generate all possible distinct delimiters (including non-prime ones, e.g. for 30 it would be 30, 15, 10, 6, 5, 3, 2, 1). Get sum of counts[delimiter].Pick the best sum.Can't say what exactly complexity this solution is, but something around O(500 * M), where 500 is max possible distinct delimiters of any number (it is somehow defendant on M too, 500 is my estimation for max value of 10^6).
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 It's actually less, maximum of divisors between 1 and 1 000 000 is actually only 240. 240·M is still very risky for 2 seconds, but the actual sum of delimiters is almost half that, , where σ0(x) is the divisor function.
•  » » » » 4 years ago, # ^ |   +16 And ln(1000000)*1000000=13815510... Coincidence? I think not.PS The reason behind this is that harmonic series diverge as ln(n).
•  » » » 4 years ago, # ^ |   0 I think I understand. It's somewhat easy I failed to think that because i misread the problem, thinking it was asking for a contiguous sub-sequence
•  » » » » 4 years ago, # ^ |   0 acc!!! I don't even needed to calculate the primes :) I used some kind of dynamic programming16463867
 » 4 years ago, # |   0 can anyone show some ideas about E? I see the post above mentioned FFT, I searched it but still no idea...
 » 4 years ago, # |   0 Could someone tell me why C problem,the sort should write return a+b
 » 4 years ago, # |   +13 What is "Unexpected verdict"? Hack #217732.
•  » » 4 years ago, # ^ |   +15 Another solution got "Unexpected verdict" on the same test (Hack #217738). So I guess one of incorrect author solutions was marked as correct by mistake.
•  » » » 4 years ago, # ^ |   0 Yes. You are right. You hacked my third solution with one (not random) module and binary exponentiation of DFT (not polynomials). Module is 998244353.
 » 4 years ago, # |   0 DP solution for problem E is awesome. I wonder how people think this way in contest time.Can anyone one please give some problem link that is solvable using this technique.
 » 4 years ago, # |   0 Thank you