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

UPD3: Editorial is ready.

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

UPD5: TOP3 of hackers:

-Secta- — 31 hacks

khadaev — 27 hacks

halyavin — 23 hacks

Thank you:)

Hello spring and hello another amazing editorial. Good luck to everyone

On one hand i also want to prepare some problems but on the other hand i don't want to miss any CF round...

Looks like A,B will be very easy in this round :/ my guess only :p Dont take it serious guys :D

Any mentor out there?

Can anyone help?

I think it would be better if it was rated ^_^

There'd be no difference between regular cf round and educational round if it was rated .

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.

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.

I passed test 7 reading with cin. And i tried to read with fstream.

It's guaranteed that printf() and scanf() are fast enough in C++. And note that maybe your algorithm is too slow.

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

Ok.

can E be solved without FFT?

I don't think so.

aha, then it should be harder than F if the intended solution for F is bitset, IMHO.

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).It's also possible to get O(n^2)

Wow, that's nice! You can sort all edges in

O(n^{2}). I didn't notice it during the contest.Could you explain it?

Are you sure? The input size is

O(n^{2}).Yes. As you can see

a_{ ij}< 10^{9}nota_{ ij}≤ 10^{9}. It is by the reason of large input size.I meant that your complexity can't be

O(nlog^{2}(n)) because it's smaller than the input size. Maybe you meantO(n^{2}log(n))?You are right. I fixed it.

There seems to be bfs solution (let ): let's look for possible sums of

kelements, we can get them by starting withk·a_{0}and trying to find sums, rechable from this by not more thankreplacements ofa_{0}with somea_{ 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 , wherewis 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).

Has anyone solved E with just FFT on complex? I get TL6 even with some optimizations.

UPD: I did it, 4991 ms :)

You can raise polynomial

Pto thek-th power just by raising every value ofFFT(P) to thek-th power.But if we raise double in 1000th power, there may be problems with precision?

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.You do all FFTs on arrays of size 10

^{6}. That'sO(k·maxa·log(k·maxa)·log(k)). If you do FFT on arrays of size equal to the degree of polynoms then complexity will beO(maxa·log(maxa) + 2maxa·log(2maxa) + ... +k·maxa·log(k·maxa)) =O(k·maxa·log(k·maxa))This solution seems to work without FFT: http://codeforces.com/contest/632/submission/16447568

I still cannot hack solutions. What is going on? Can anyone hack now?

How? :P Why doesn't the hacking phase start immediately after the contest is finished?

cannot hack

It will be fixed soon.

thank you.

I can't hack solutions.

is someone facing the same problem ?

See the UPD2.

where can I see editorial to these problems?

Contest is not over yet. Usually the editorial is published as soon as the hacking phase finishes.

Oh, silly me, I thought in 632B - Alice, Bob, Two Teams Bob could take any segment...

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

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}).Oh, your solution is much easier to implement. (But it requires O(N^2 log N) time since we sort the elements, I think.)

Yes. But edges can be sorted in

O(n^{2}) if you notice that in magic matrix there are onlyO(n) different values. So it's not hard to improve it toO(n^{2}).Can someone explain why am i getting runtime error in the 8th pretest of the 3rd question?

Here is the code.

comparison function should return false when both elements should be considered the same

now your function returns true so it breaks the sort function. To fix that just change

`<=`

to`<`

Don't read this comment

Ignore the usual comparator, you are defining a new one. The function should work exactly as operator <. Can you say that A<B and B<A are both possible at the same time?

I get you now :)

I am telling you that sort uses < operator, not <= and in rivudas' case it happens that A<B and B<A at the same time (

a=xyz and b=xyzxyzxyz) :)ignore

Yeah, precisely what I am trying to say is that it's an incorrectly defined cmp function :)

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.Don't read

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

Now its CLEAR!! Thanks, or I'd have lost a good night's sleep lol :)

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?

"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

Oh sorry, I didn't read that well. Thank you ! :)

Edvard, do you know approximately when the hacking phase will be open?

It is already opened. Sorry for late answer.

"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

How to solve problem E ?

I found someone with amazing short (compare to other which use FFT) code to E:

http://codeforces.com/contest/632/submission/16452555

Problem C. C++ solutions using

`bool comp(string& a,string& b){ return a+b<b+a;}`

seems ~2-3 times slower than solutions using the same in dynamic languages: Python, Perl. That's interesting.Hi, I want to know some idea about how to solve problem D :)

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

It's actually less, maximum of divisors between 1 and 1 000 000 is actually only 240. 240·

Mis still very risky for 2 seconds, but the actual sum of delimiters is almost half that, , where σ_{0}(x) is the divisor function.And ln(1000000)*1000000=13815510... Coincidence? I think not.

PS The reason behind this is that harmonic series diverge as ln(n).

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

acc!!! I don't even needed to calculate the primes :) I used some kind of dynamic programming

16463867

can anyone show some ideas about E? I see the post above mentioned FFT, I searched it but still no idea...

Could someone tell me why C problem,the sort should write return a+b<b+a; I couldn't understand very well.

What is "Unexpected verdict"? Hack #217732.

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.

Yes. You are right. You hacked my third solution with one (not random) module and binary exponentiation of DFT (not polynomials). Module is 998244353.

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.

Thank you