gridnevvvit's blog

Codeforces Round #236
By gridnevvvit, 11 years ago, translation, In English

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 (aiMR) 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 :

  1. vladb
  2. iceiceice
  3. LoneFox
  4. ofpsxx
  5. adsz

Div. 1:

UPD:

Editorial.

UPD:

Round Statistics from DmitriyH.

  • Vote: I like it
  • +140
  • Vote: I do not like it

Comments Comments (71)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +225 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it -57 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it -60 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    funny :p

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this entry does not appear in the home page ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

wish all participants a very happy Holi :)

→ Reply
»
11 years ago, # |
  Vote: I like it +41 Vote: I do not like it

your first both divisions contest after many Div2 contests :)

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it -43 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    :|
    Everything is funny for the first time!

    → Reply
»
11 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

What is the solution for C ?

→ Reply
»
11 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the faster way?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    and got AC :v

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    look at this solution for the same problem :P

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

            int cn; cin >> cn;
	for(int ci = 0; ci < cn; ci++) {
		int n,p; cin >> n >> p;
		int cnt = 0;
		for(int k = 2; k <= n; k++) 
			for(int i = 1; i < k && ( cnt < (2*k + p) ) ; i++)
				cout << i << " " << k << "\n", ++cnt;	
	}
    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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

Great!

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it +17 Vote: I do not like it

    i dont know whats the funniest of the following:

    • user thinks that adding comments makes it difficult for others to see that solutions are similar
    • the two handles are FakeErdem2 and kalimm (also very similar)
    • they both submitted within 30 seconds of each other
    • the "fake" account submitted before the "real" one
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        oh. so ur saying that if two exactly identical solutions 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 public site?

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Sooo when will ratings be updated ???

→ Reply
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

Div2 D,div1 B

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    V[j]/=gcd(V[j],Div[i]);
Div[j]/=gcd(Div[j],Div[i]);

    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

    → Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I seriously can't understand E. If the edge (x, y) is of different colour than (p, q), then x and y lie in a different tree than p and q, so condition 2 is impossible. No?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

waiting eagerly for Round Statistics which DmitriyH usually posts!

EDIT: its now available here, and i got my wish of my name being published! :)

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/402/submission/6050051
Using Normal factorization (TLE at #42) : http://codeforces.me/contest/402/submission/6046374

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/402/submission/16409847 http://codeforces.me/contest/402/submission/16409976 http://codeforces.me/contest/402/submission/16420324

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

→ Reply