Soon (on March 16, 19:30 MSK) you are lucky to participate in Codeforces Round #236 for both divisions.

Problems have been prepared by me. It’s my first round for both divisions and I hope not last. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Ilya Los (IlyaLos) and Ignatyev Alexander (ai9128429340875) for testing of problems, Mary Belova(Delinur) for translating the problems, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

**UPD**: Scoring system:

Div. 2: **500 — 1000 — 1500 — 2000 — 2500**

Div. 1: **500 — 1000 — 1500 — 1500 — 2000**

**UPD**:

Contest finished, congratulation for winners!

Div.2 :

Div. 1:

- 1 sillycross
- 2 KADR
- 2 vepifanov
- 4 Endagorion
- 5 glassices
- 6 cgy4ever
- 7 rowdark
- 8 snuke
- 9 ftiasch
- 10 fsouza

**UPD**:

**UPD**:

Round Statistics from DmitriyH.

Please don't click on "Rev" because I wrote something bad :(

BEG y'all for some mercy on not so many downvotes, OK?!

why you wrote something bad rather than writing something good like scoring system please don't click on "Rev" before the start of the contest I wrote Scoring System

funny :p

Why this entry does not appear in the home page ?

Stop downvoting, it wasn't on the home page indeed at that point.

wish all participants a very happy Holi :)

Happy Holi bro..

your first both divisions contest after many Div2 contests :)

I wish it will be a good contest as always !!

:|

Everything is funny for the first time!

Since next Div.1 contest is on March 22, this contest is "Good Bye 1392" contest for Iranian Div.1 contestants. Nowruz 1393 is on March 20 so Div.2 contestants have one more contest in 1392 :) Happy Nowruz

I wish it will be a great contest as always !!

I guess, first time DIV2 contest takes a contest-id less than the corresponding DIV1.

true that. it maybe because of the statement of the last contest's problem B

The overall feeling is that tasks are tend to be a bit artificial, especially B.

And for E, I can't understand the statement.

Thank you gridnevvvit! I believe your next round will be better. :)

I feel that problem C just came out of nowhere...

It was horrible Adiv2, but this is the first contest when I'm not sure in my B,C ideas at all) Smth new for me, thanks.

So am I.

What is the solution for C ?

Is it just me or sometimes constraints on Codeforces are unnecessarily tight? For example today, I resubmitted B because I thought 5000 * sqrt(10 ^ 9) modulo operations won't pass in 1 second. Some time ago I got TLE for 5000 * 5000 in 2 seconds, although that was the expected complexity. Just because I also had 5000 * 5000 memory. Well today, after resubmitting I tried to hack such a solution and it fit into the limit, in something like 0.95.

So why make n = 5000 when you want n ^ 2? Why make n = 5000 today? The only way in which 5000 instead of 1000 (for example) affects the contest is that some sloppy implementations may TLE and others may not, depending on some non-algorithmic issues (cache breaking, input/output speed, speed of used operations, etc).

This was a good contest, congrats to the authors. They're not the target of this post, I'm just saying that generally we could avoid such issues if we just stick to reasonable limits, which don't cause doubts about TLE, be it for submitting or hacking.

Actually there is a faster way then sqrt(10^9)...

What is the faster way?

It's probably O(number of primes < sqrt(10^9))? (if we don't count Pollard's Rho algorithm here)

sqrt(10^9) — something finite

number of primes — infinite

=>

(numbers of primes < sqrt(10^9)) = 0

O(0) is pretty fast :P.

Btw pi(n) = O(n / ln n), where pi(n) if of course number of primes numbers less than n.

Well I know there's a faster way, do you think I resubmitted the same thing? But the optimization brings 0 additional value to the problem. So why think about if it's necessary or not? Why guess if it's needed or not when hacking?

You are using map which is red-black tree. Any number x has not got more then one prime divisor bigger then sqrt(x).

Agreed. 5000 * sqrt(10 ^ 9) failed. That makes me frustrated.

I think precalculate the prime that smaller than sqrt(1000000000) would be better. You can do it in O(n) time. That won't cause a Tle.

I've tried to hack a solution with 2 * 5000 * sqrt(10^9) operations and his solution took 0.998s... (I don't know how it is even possible to do more than 300,000,000 operations in less than 1s). As you say, I think it should have been n <= 1000 if this kind of solution was considered as OK or n <= 10000 if not. Nevermind, goodbye red :D

Totally depends on the operations. 3e8 array indices would probably be too slow, but if everything fits into the registers, you can get close to 2e9 cycles per second or so (= frequency of your processor).

My accepted D1-A solution is as follows:

For each step, create edge (u, v) with the smallest deg[u]^2 + deg[v]^2.

It does not care about p, 2n + p, nor 2k + p. What is the intended solution, then?

If you solve p = 0 then you can add any p edges and the solution will be ok. To solve p = 0 you can make a cycle out of N — 1 nodes, tie the N-th one to them and add 2 more edges somewhere. There are other ways, of course.

I didnt really understand the problem and just generate the pattern for C div2...

and got AC :v

look at this solution for the same problem :P

fuuuu, pascal

tourist usually code in Pascal. That is not make any problem to him to be the first

And what?

The condition is equivalent to saying that removing any vertex should delete at least two edges. So if for every vertex you can pick 2 edges touching it (each edge can be picked by at most 1 vertex), you're ok.

I just connected i to (i+1)%n and (i+2)%n, and added p random additional edges.

I was creating edge for min(degree[i]+degree[j]).

I simply "distributed" 2*n+p edges in the manner hinted in sample solution

1-2,2-3,3-4,4-5 .....,1-3,2-4,3-5,4-6 ....,1-4,2-5,3-7 ...

till the count becomes 2*n + p .. didnt care for the subgraph conditions

I was reducing the code written in 3 minutes (deleting vectors,pairs), until it became my solution)

Another Tricky Contest but there could be a lot more hacking attemps!

Where can I check the editorial and the testcases?

http://codeforces.ru/contest/402/submission/6035354 http://codeforces.ru/contest/402/submission/6035395

Great!

i dont know whats the funniest of the following:

The last point is just to not affect rating if the pretests failed .

Adding comments makes it difficult for system to skip the solution automatically.

oh. so ur saying that if two

exactly identicalsolutions are submitted, system skips the second one automatically?i dont think this should happen. what if both codes are copied from some old blog post or any other

publicsite?They actually have cheated in this way during the contests 225, 226, 227, 234 and 235, so this means that their strategy is not this bad...

Sooo when will ratings be updated ???

updated.

Time limit in problem B is too strict. I've got TLE and got AC (after contest) by a small optimization. I think that either TL must be adjusted to 2s-3s or biggest test (test with biggest run time) should be in pretests.

same happened to my code..

Time limit for D : Upgrading Array was too strict.. I got TLE but when I changed some variables from long long int to int, my code got Accepted..

What's wrong in my solution of Pro.B Div2? Anyone can help? Submission:6037256

So complicated way. Why dont you just find the first element of the corresponding element of array and count it? And the constraint is so small only about 1000 first element was able to counted.

If there are some element had been in the right order in sequence for a first element most, so its the most probable sequence. Then find differences with corresponding element in array. Just it

Here my solution : 6037944

Thanks.

Putting an advanced topic in a C problem even it's a direct one wasn't a smart idea i think !

Whats wrong with my idea, can anybody tell me? I have confusion with "//*******************" marked lines. http://pastebin.com/vi446T5f

Div2 D,div1 B

Actually it is quite funny mistake :D In those two lines

the iteration at which j==i (the first iteration of the loop) ... the value of Div[i] becomes 1 ... So it is not the correct value for the rest of iterations when j<i

Here is a link of accepted solution after fixing Submisson

I seriously can't understand E. If the edge (

x,y) is of different colour than (p,q), thenxandylie in a different tree thanpandq, so condition 2 is impossible. No?waiting eagerly for

Round Statisticswhich DmitriyH usually posts!EDIT: its now available here, and i got my wish of my name being published! :)

I am stuck on 402D/403B. I tried several approached but I keep getting TLE. I think I am missing something here. Can someone please have a look :

Using Sieve factorization (TLE at #18) : http://codeforces.com/contest/402/submission/6050051

Using Normal factorization (TLE at #42) : http://codeforces.com/contest/402/submission/6046374

Just add this line to your first solution and it becomes fast:

I tested it here: http://codeforces.com/contest/402/submission/6050585

Thanks a lot pllk !

DIV 2 problem B. I tried searching for the most common number in the array Ai-i*k(*Ai is the input, as long as the this number is positive) and the answer should be n-(the amount of times this number appears) but for some reason i cant pass test 8. is my idea wrong? Java submission: 6050363

I want to know the problem C why the tree can't have the height of 0

hi, someone can explain solution for problem E div2/C div1?

Just for the strongly connected components A^k means The path length between two points for K

I was trying to find a twist in the logic of problem c (searching for graph) but the logic seems straight forward i.e removing edges from the smallest sub graph of i.e sizes 1 , 2, 3.... going up the subgraph until all the extra edges are removed seem to work. I am suspecting the logic cannot be that simple. Do you think this is really the logic?

For example: for 12 nodes and 0 interestingness

total edges in complete graph = 66, total edges in the solution = 2*12 = 24

total edges to remove = 42

here is how i remove it

nodes ->

12 11 10 9 8 7 6 5 4 3 2 1

edges in subgraph->

11+ 10 + 9 +8+ 7 +6+ 5 +4 +3 +2+ 1+ 0 (for eg. for graph of size 3 total edges 2 + 1 + 0)

after removing the edges

edges in subgraph-> 11 + 10 + 3 + 0 + 0 + 0 + 0 +0 + 0 +0 + 0 + 0

Nice One for Div 2. Thank you for arranging that. Hope You will arrange some more next time. Plz post the tutorial.

There were many chances to hack, but I couldn't do at all =(

Congratulations! codeforces, I appreciate everything that you have done for us. we're gonna have to work together in codeforce!

Hii,

in Editorial of Prblem C, Searching for Graph, Contest #236 they have talked about some

0-intersecting graphs... i dont have any idea and i am unable to find this on internet, so can anyone please give me some link, from where i can gather some information about this topic.thank you

Laman graph is a

`-3`

-interesting graph.My solution of Problem D is receiving Denial of judgement error. Could anyone please explain to me what is the problem?

The Submissions Ids are

http://codeforces.com/contest/402/submission/16409847 http://codeforces.com/contest/402/submission/16409976 http://codeforces.com/contest/402/submission/16420324

Someone please tell me what should be the countermeasure. Thanks in advance.