Good day, friends)

Soon is coming regular Codeforces round #166 for Div.2 participants. Traditionally the others can take part out of the competition.

And again the problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Nikolay Kuznetsov (NALP), Rakhov Artem (RAD) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

**UPD**: Score distribution will be not standard a little bit — **500, 1000, 1500, 2000, 3000**.

We wish everyone good luck, successful hacks and high rating)

**UPD2**: the contest is over, we hope you enjoy it)

Congratulations to winners:

1) sunzhouyi

2) xyz111

3) nanoha

4) wyx528

5) GuyUpLion

**UPD3**: the editorial is published, you can find it here

This group always offers good problems...!!!

MikeMirzayanov's contribution is +210 O_O

Keep getting negative votes and your contribution will reach his (by absolute value) sooner than you can possibly imagine.

No one will win JKeeJ1e30

Такие все шутники) но иногда приятно) ставлю плюс)

its time

Hi authors, Problem C div2 says that any alternative solution is accepted. So this answer for test: 11 3 11122233123 shouldn't be accepted?

It should, but you should have printed the blank spaces between each number...

if we divided in three group it will be:

all 3 of the sequence is not an arithmetic progression

for all who had WA #8 in problem D,I think the test case is

abaab 01 2

and what do you say abt TLE + memory limit exceeded for D.

The problems were excellent! The problem-setters deserve a round of applause.

Nice problem set, the writers managed to come up with balanced problems, got 4 out 5.

waiting for rating update .....

In problem D, I use 2 hash value with int always get wrong answer on test 41, and my answer always is 241238 (the right is 398680), and I use long long with same hash numbers get accepted. Why there is so big difference between them ? Many helps !

I just exchanjed power of prime number from 31 to 29 and 37, then got accept.

You guys use hash without handling conflict, and still got ACCEPTED! How unfair... I found a nice c++ solution(3100030) in my room that use

`set<string>`

, and the worst time complexity is O(n^3 log(n)), still very nice, though.My first attempt was a Python solution using a Trie, which is O(n^2). It got TLE, saddly. Then I was forced to translate the Python script into C++.

I used suffix array with time complexity O(nlog^2n) in building the array and O(nlogn) for the rest.3108063 This is totally unfair that even solution with time complexity O(n^3logn) can be accepted. The test case should be bigger, say string of length 1000,000.

When the data scale is too large, we will lost some interesting solutions. It's also unfair for some dynamic languages since a loop with 1000000 times may cost about 1 sec. So I think 10^3 or 10^5 is fine.

After participating in some contests here, now, I confess that I'm not clever enough as I thought I am :( I'm not sure if continue to participate will make it better; I even can not get to 1700 :(

Any friend has an idea about why I'm not successful here as much as my successful in business software development (I am Microsoft Visual C# MVP 2011)?!

I just like to know if I should continue or break to study more and then come back.

Thanks in advance!

You can come back any time. But we are sad to see you gone...

andcompete in contests.Remember… practice makes perfect.

+1.

thanks expert!

In your opinion, how much IQ has effect in results in percent?

It is a wonderful place to get knowledge and I don't have a great result but I am trying to be better day by day here.

Anyone willing to share an idea for problem E?

My idea was based on this observation:

Suppose that y=x+k

What we really care for is the difference between a pair of numbers (the k).

(because we can get (a+1,b+1) and (a-1,b-1) from (a,b) )

The first horse does not change the difference

The second horse divides the difference (k) by two

The third horse gets two pairs with differences = k1,k2 and gives a pair with difference=k1+k2

(The rest is simple NT -divisibility, gcd,etc.- )

I thought with the same idea in the contest but actually first horse give (a+1,b+1) form (a,b) but don't give (a-1,b-1)

(a, b) -> (b, 2 * b — a) -> (a, 2 * b — a) -> (2 * a — 2, 2 * b — 2) -> (a — 1, b — 1)

Thanks to the creators , for making the catching stuff in the questions

BOLD, it really helped!!Unfortunately I missed the contest.. Was celebrating my birthday

yaar aaj tu Div 1 me pahuch jata :( btw hbd :)

HBD :)

its showing me blue color but with old rating :( :( yyyyyyyyyy so ?

It's showing me blue but with older rating 1448 :( why ???

Could someone explain Div2.E problem body? As I understand:

But it surely isn't correct understanding.

Actually, it is the correct understanding.

Anyone willing to share an idea for problem D without hash? Thanks a lot.

prefixs + substrings + set = 3103424

thankyou

please explain how could this pass?

you have 2 "for" and inside them you have "substr" which has complexity O(j-i) so your total complexity is O(N^3)

You are right, but it has a low constant, so 2 "for" and "substr" inside them take only 350 ms on a string with length=1500.

Also working with set we have total complexity O(N^3*ln(n)), because comparing the string takes O(N). But it is also with low constant and is unattainable, because not all substrings are comparable in full length.

Four of the winners took part in Codeforces contest for the first time,the rest one only took part twice....

I'm sure they are multiple accounts

I'm sure they aren't muliple accounts

Absolutely agree,in most contests there are about 2-3 unrated winners,maybe I'm mistaken but I think they are multiple accounts

One question: the limit for the Div2 B were n,m <= 500, but what is the point to have such limits, when the max size of test file for hacking is just 256 KB? I mean there were a lot of solutions that could be hacked using a matrix of size 500 x 500, but it wasn't possible because the system won't accept files that big. Many solutions were done in O(n*m*nextPrime(x)) and I think this wasn't the complexity intended to solve this problem. An acceptable one would be done in O(n*m*log(closestprime(x)).

you have to write code to generate test-cases you want ,not the test-case itself

nextPrime(x) factor is extremely small ~ O(log x), so it's just looking for 20 consecutive bytes of memory. Bad binary search could be slower.