platypus179's blog

By platypus179, history, 9 months ago, translation, In English,

Ladies and gentlemen!

Codeforces Round #395 for both divisions will happen tomorrow, on Thursday, 2 February 2017 at 13:35 UTC.

Problems were prepared by me (Vasiliy Alferov) and students of Moscow school #179: s17b2_voroneckij (Dima Voronetsky), ilya_the_lamer (Ilya Pauzner) and akvasha (Anton Kvasha). Also, KAN (Nikolay Kalinin) is author of one of the problems.

Invaluable help was given to us by Codeforces coordinator KAN (Nikolay Kalinin). Thanks to MikeMirzayanov (Mike Mirzayanov) for wonderful platforms Codeforces and Polygon. Also thanks to Endagorion (Mikhail Tikhomirov), winger (Vladislav Isenbaev), AlexFetisov (Alex Fetisov) and cdkrot (Dmitry Sayutin) for reading out our statements and testing the round.

Participants will be given five problems in both divisions. Some of the problems will be common for both divisions. The scoring distribution will be announced later.

Good luck to all!

UPD: Scoring distribution:

Div1: 500-750-1500-2000-2500

Div2: 500-1000-1500-1750-2500

UPD2: The contest is over. Hope you enjoyed the problems :)

UPD3: Congratulations to the winners!

Div 1:

  1. moejy0viiiiiv

  2. V--o_o--V

  3. fjzzq2002

  4. SkyDec

  5. uwi

  6. Belonogov

  7. aid

  8. dreamoon

  9. Um_nik

  10. Andrei1998

and Div 2:

  1. ljh2000

  2. MashiroSky

  3. sqcszboyi

  4. _Reborn_

  5. Factorio

  6. Dirak

  7. lnjlnj

  8. Manchery

  9. SarvagyaAgarwal

  10. mik

The editorial will be posted very soon.

UPD5: Editorial

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +62 Vote: I do not like it

I am new to programming and I have visited number of coding sites and I found Codeforces one of the best coding sites on the Internet. Coding rounds like this are so amazing. I really enjoy coding on Codeforces. Thanks a lot for making coding site like this.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -53 Vote: I do not like it

    i just signup to this site..i will see how much fun it wil give to me..i hope HACKEREARTH and HACKERRANK are best site that i came across..just go through once i hope i will never come back to this site..

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro..At least write correct English...you are tough to get..

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Those sites are also good, I am just saying that I liked this site a lot. Its my own opinion and opinions can differ from person to person. Hope you will understand.

»
9 months ago, # |
  Vote: I like it +46 Vote: I do not like it

I hope it won't end up unrated like yesterday :\

»
9 months ago, # |
  Vote: I like it -59 Vote: I do not like it

Time collides with Hackerrank's HourRank. I'm a pupil. I'll probably end up participating in both contests.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +70 Vote: I do not like it

    what does being a pupil have to do with anything?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      We dont solve lots of problems. Lots of free time. :D

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +126 Vote: I do not like it

        If you think that way, you are going to stay at pupil for a long time. Seriously, just keep trying until the contest ends.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it -20 Vote: I do not like it

          Ofcourse I don't think that way. It was just a joke. Clearly, a bad one.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +80 Vote: I do not like it

    HourRank is at 16:00 UTC. The contests don't collide.

»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Hope the Codeforces polygon won't be unstable this time, or this round will remain unrated too... :( Anyway, I'll try my best to work on the problems no matter whether it's rated or not. :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    what's the need of writing it here?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Because it happened in the last round two days ago. Although I didn't take part in it, I think it would be very disappointing if this happened. So just pray for it...

»
9 months ago, # |
  Vote: I like it -7 Vote: I do not like it

the round rated?

»
9 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

A week without any rated contest, hope this contest doesn't have any bugs like the previous one:)

»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

blue coders prepare a contest for Red coders. Amazing :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    It should not be underestimated because of the color. Let us estimate after the contest.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    As you can see, a purple color and a red also worked on the problems.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    Not being an excellent coder does not mean not being an excellent problem setter :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +149 Vote: I do not like it

      Yes, but as a former TopCoder admin and current AtCoder admin, I'm sure there's strong correlation between the originality of problems and the writer's rating. That's why we set a rating cutoff for being a writer.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    I was orange two months ago :(

»
9 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Hope codeforces is stable today and we get a rated contest! :)

»
9 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hopefully we get something other than math and greedy for Div2 ABC :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +124 Vote: I do not like it

    What do you expect? Persistent segment trees? :)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      easy dp , graphs ?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +47 Vote: I do not like it

        Graphs are too complicated for beginners who have just started competitive programming. Some of them don't even know what a graph is. So I believe graph problems are not suitable for div2 AB.:)

        Easy DP would be a good idea for div2 C. But similar to graph problems, I don't think it's a good idea for Div2 AB.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +27 Vote: I do not like it

          Yeah, in my opinion, problem Div2 A and B will be the situations that we'll meet in our life, such as buying watermelons(just kidding :P). They won't require a very high skill. You can just do it in the way you think. So I don't think they require learning deeply into mathematics or greedy. Just very simple thoughts. The problem for beginners is that they can't code it or consider every situation, instead of they can't get the way of doing them.

»
9 months ago, # |
  Vote: I like it -14 Vote: I do not like it

The answer is Yes, right?

»
9 months ago, # |
  Vote: I like it -35 Vote: I do not like it

I hope to see some physics problems this round :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Hope it won't be so..

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A change of scenery would be nice... a bit tired of all the math problems haha

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think this idea is interesting. But for the ones who haven't learnt deep into physics, it's a little bit unfair, because they have to spend a lot of time understanding the problem statement. Also they won't think of some situations that is different from others but not mentioned in the problem statement. So personally, I won't choose a physics problem. But I don't have the chance to decide or know. :D

»
9 months ago, # |
  Vote: I like it +45 Vote: I do not like it

I hope this time we don't have any problem with the server. I got trauma from this image in the previous contest.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    it is already showing very busy, i wonder if it will happen today again

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally Div1 & div2 separated

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

CodeForces is toooooooo slow from here Hope not a server error

»
9 months ago, # |
  Vote: I like it +30 Vote: I do not like it

A good time for Chinese students!Hope it will be a good warm-up round for the Chinese Winter Camp next day.

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope that this time contest doesn't go unrated.

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope that this contest will be interesting :)

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope all is well this time! :D

»
9 months ago, # |
  Vote: I like it -20 Vote: I do not like it

PC hanged while reading problem A. Forced shutdown and restart. More than 3400 submissions on A and 1800 submissions on B. out of competition :(

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

What does "more" in div1D mean? more pairs or more vertices?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add the explainations to div 2 problem c sample inputs and also adding explainations to the problem like A and not to a problem like C is not fair at all :(, seems like it is done deliberately.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the input of Problem C from div2, u < v , or it doesn't matter?

»
9 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Very Nice Problems! :D I made a history for myself, this is the my First Time to solve graph related problem! Trees are so much fun! Hooray Rating!

»
9 months ago, # |
  Vote: I like it -78 Vote: I do not like it

problems like shit .

  • »
    »
    9 months ago, # ^ |
    Rev. 5   Vote: I like it +32 Vote: I do not like it

    Never say something like this. It's your fault that you can't solve the problems. The problem settler may should have designed some easier problems, but it's their chance to do that. Also taking part in contest will be more valuable if you can discover what you are poor at. You should improve your own skills, instead of saying rude languages towards the problems.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Problems were easy compared to regular contests

»
9 months ago, # |
  Vote: I like it +38 Vote: I do not like it

The gap between div2C and div2D problems is far bigger than 250 points imo.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm not so sure. Maybe because I'm not used to DP on trees, but have a lot of experience in combinatorics style problems, I found D to be far easier than C. At the very least, it was easier to code.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now when I saw solutions to D I'm not so sure either :D

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I couldn't submit on time , but i am not sure if we even need dp on trees . Could be done without that.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Easier to code? Could you, please, share your solution? I've struggled a lot with implementation.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      DP on trees? If you are reffering to div1A, it was just a matter of finding all edges that connect vertices of different color, and seeing if all those edges share a same vertex.

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem set of this contest was nice. Although Problem D deserved 2000 points imo, if not 2250, since the difficulty gap between C and D was too high.

»
9 months ago, # |
Rev. 2   Vote: I like it +117 Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +47 Vote: I do not like it

Is this an IQ contest or something ??????????????

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    If it is, I am very stupid :D

    Very nice problem D, I really like it.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      How did you solve it?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +33 Vote: I do not like it

        Just consider the top-right corner of each rectangle and color it based on (xmod2, ymod2).

        I somehow thought this doesn't work in the contest and got stuck for 40+ minutes. Then I realized it actually works -_- RIP rating.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you prove its correctness?

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            It's quite easy to prove. Just prove that the top right corner of two touching rectangles cannot have both coordinates with equal parity (with the condition that all rectangles are non-intersecting and have odd side lengths)

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -17 Vote: I do not like it

        answer is always YES . let a = x1&1 , b = y1&1 , colour the rectangle with colour = a*2+b+1 .

        I liked this problem the most .

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Notice that two adjecant recetangles must have left (right) — bottom corner with different x % 2 coordinate or y % 2 coordinate.

        So for each combination (0,0), (0,1), (1,0), (1,1) assign different color.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +21 Vote: I do not like it

          OMG, this is so simple and easy. And there am I, generating an adjacency list and trying to solve the graph problem.

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I was doing the same thing at first, and than I saw that guys solved in three minutes and I said forgot this, try again :)

            I believe we can run normal dfs for case with any length of sides and put the smallest different color than all adjecant colors and run dfs from next node again. Somehow I think it will produce correct answer.

            But you need big code for caluclating adjecants recetangles. Can someone prove than we won't have more than 4n pairs of adjecant recetangles ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    no, usual one don't be rude. dude

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach problems like Div2C which require dfs to calculate answer?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Consider writing dfs.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      er...i am poor at the problem at div2c , and now after i read the editorial,i dont know how to implement it by myself,i think i should practice some similar to this problem or maybe easy than this problem, can anybody suggest me some similar problem ? thanks in advance , and sorry for my bad english ^_^

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But what is diffuclt in this problem? The dfs there is rather simple.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Find two adjacent nodes where their colours are different, if the answer is YES, then one of those two points would be the root.Do a dfs at both the points to check if their subtrees have nodes of the same colour. If it is not possible for both of them, then it is NO. It is YES otherwise,and you know the answer.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but it looks brute force i thought that did not implemented that, then i thought some more complex solution dsu + segment tree but got memory limit exceeded :( . I think sinus_070 your solution complexity is O(n2) , either the testcases are not more strong enough or i am missing some thing . Anyways it is always fun to think and solve problems , it always gives satisfaction .

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm doing 2 dfs' only. And finding the pair is O(n)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Nice and easy problem I had wrong answer on testcase 10,hadn't time to solve some special, but this algorithm almost surely is correct.You have to find 2 vertices that are connected and different color, one of them must be root.So if you you have more then 1 such pairs and they don't share one vertices you're done,otherwise that vertices is root,proof is simple.

»
9 months ago, # |
  Vote: I like it +28 Vote: I do not like it

How to solve Div1 C??

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    How to solve Div1 C without random !

»
9 months ago, # |
  Vote: I like it +126 Vote: I do not like it

Div 1C is the same as this problem http://codeforces.com/gym/100451/problem/I.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +14 Vote: I do not like it

    Shit.

    In fact, it isn't exactly this problem, in our Div1C the modulo was prime and the model solution uses this fact.

    Anyway, I didn't see this problem before. Neither, probably, did KAN.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how to solve it ?

    I could only think of O(N^2)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way, is there any published editorial for Petrozavodsk training camp contests? The official one seems to require credentials to log in.

»
9 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

On problem D, my output for the first test is:

YES
3
2
2
1
2
1
2
1

Why does it give WA?

Here are the rectangles, black numbers are indexes, brown numbers are color. No same color touches:

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    In system your output is "NO".

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So weird. I tried custom invocation, it outputs NO. On my compiler it outputs the right answer. I'm sure the files are the same, I tried uploading the file twice, it told me I've submited it before. My code is here. Might be a C++11/C++14 problem.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The problem is in line 67:

        bool can[5];

        It looks like you are expecting the initial values to be 0. But you are dynamically allocating the array, so it will be uninitialized.

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

No Hacks This Time :) !!

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

How to solve Div1 B??

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +49 Vote: I do not like it

    Since edge lengths are odd, just assign colours on basis of the pair (a%2, b%2), where top-left corner is (a,b). You are guaranteed that same color rectangles will never touch each other.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    colour of a rectangle is 2*(x1&1) + (y1&1) + 1

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve div2C ?

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I solved it using greedy technique.

    The solution is that we define f(u) for vertex u as the number of adjacent vertices to u like v such cu != cv. then choose the vertex with greatest f(u) and check if erasing it from tree annoys him or not! if not, the answer is "NO". otherwise, print this vertex.

    I hope it would pass sys tests. ;)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume vertex #1 is the root. For each child C of the root check whether all elements in subtree with root C are the same color as C. If you found vertex of different color — make it a root of your tree and do this checking one more time but now print NO if found different color.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    My approach- Consider all such edges that connect two vertices of different color. Let's call them heterogeneous edges.

    There will be an answer iff there is one vertex common in all the heterogeneous edges. And that common vertex will be the root.

    You don't even need to build a graph. It's elegant...well, only if it's correct. :D

    Edit: It is correct. :)

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I think it was better that task D worth 2250 points, it seems really tough for lots of competitors

»
9 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Div2 A .. very bad statement

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I tried to conceive the whole situation for a few minutes, but failed to understand what's going on there. Then I went straight to the examples and was able to abstract away from these climbers, artists random phone calls and odd killings for no reason.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The only thing I could say it was bad is because you don't know if he would kill everyone that has visited, or only people that visit that minute.

    However, test case 3 answers that question. I thought it was good, but I was second guessing myself.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      exactly :D

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The statement says "Print single integer — the minimum number of artists that should be killed so that there are no artists in the room when Ilia calls."

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I missed that somehow. However, the test cases gave the example. So there was multiple ways to get the information. Awesome Sause.

        Have a great day!

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't read statements, just looked samples, then got the idea :D

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Strongly agree!

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Does anyone knows the test case of pretest 7 of problem C in the div 2 contest. It's like a freaking walls.

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    5 — 1 2 — 1 3 — 1 4 — 1 5 --- Mb

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you have figured out what's special about pretest 7 let me know. Thanks

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

For description of DIV1 E. I think you should let (1<=l<=r<=100000) be (1<=l<=r<=n)

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the nice problemset! I really enjoyed this contest!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D...I thought about turning it into a graph and then DP it but I thought it would be too messy and I didn't know how to handle cycles could anybody who has solved it explain his/her solution ?

My DP was going to be DP(node, which color this node is)

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    If you mean Div.2 D, there is a simple trick. Let's say that the top left corner of rectangle 1 is (X1,Y1) and rectangle 2 is (X2,Y2). As the rectangles have odd length, they can only be in contact if either X1-X2=1 (mod 2) or Y1-Y2=1 (mod 2) or both. In other words, two rectangles can not be in contact if the modular 2 of the top left corner is the same. There are four possible ways for (X,Y); (0,0), (0,1), (1,0), (1,1). Assign a color for each.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmmm...interesting observation...I wish I could notice that at the right time...Thank you.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 D? I assume it is graph constructing and coloring problem. Can you give some hints if it's so? Otherwise please tell me that it's wrong approach.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No. Just output answer based on whether x and y are odd or even. Because the side length is always odd.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved Div. 2 C with DSU. I don't know if it's wrong, since many people solved with normal DFS. How would you do normal DFS though?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was too trying with DSU but didn't managed to get AC.-_-

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    first dfs from any leaf till you encounter a node with different color(named save and its parent in dfs be save2). Now (if the # of nodes with distinct colors attached with this node save2 > 2) then mark save as the desired node and run dfs for all vertices attached with save and check if they are of same color to their respective parents. else mark save2 as the desired node and run dfs for all vertices attached with save and check if they are of same color to their respective parents. if its possible then output mark else "no"

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    well, I solved(passed pretest) with dsu. Just merge the neighbor together if their color is the same, then iterate over the vertex. See if the size of all distinct dsu from its neighbor and himself is equals n. If so then you can choose it.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Now I got it , did exactly same as you did but i checked degree not number of vertex may be thats why i was getting WAs. thanks :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I solved without using dfs/bfs/dsu. Just checked edges between two different colored vertices.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even i tried with DSU and segment tree got memory limit exceeded :( .

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice div2 D! That was wonderful

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Nice hack case to C: n=m-3 and sequence lacks 3 elements that don't form arithmetic sequence.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2D was awesome . How to solve it if the dimensions of the rectangles can be even too ?

»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

What was the expected (or popular) solution to C? I noticed that, given and , we have a quadratic equation on d, though I somewhat expect to see many probabilistic solutions.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I tried all possible starts and found d from equation, then verified that sum of squares is same as well. Not sure that it will pass.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The difference between any two element is kd, and we can use the number of occurrence of kd to compute k since k1d = k2d implies k1 = k2.

    If we choose kd to be the smallest difference between any two elements, the number of kd can be counted in via sorting. Suppose we have c pairs of element having difference kd. Originally I take k = n - c, but this is correct only when 2n < m and I didn't notice it until the last 15 minutes. I "flip" the sequence to fix it but maybe it's not necessary. :P

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I'm sure that the number of (x, d) satisfies two equations is O(1) (It can be three or more equations). So the complexity may be O(NlogN).

»
9 months ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Div1 A is so simple..

Spent about an hour trying to write hard dfs-tree-based solution. Finally got simple idea, coded in 4 minutes:

All the edges (u, v) such that color[u] != color[v] should have one common vertex. This vertex is the answer. Otherwise, there is no answer.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah bro, but Div1 B is an even bigger fail for most people here. :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah man did exectly same,but got WA on test 10 mabe I messed some special case...

»
9 months ago, # |
Rev. 2   Vote: I like it +90 Vote: I do not like it

Me after reading Div1-B solution

Best Div1-B problem ever (even though I failed to solve it).

»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Didn't notice, rather didn't pay much attention to the fact that lengths were odd inspite of it being in bold for Div 2D. Ended up thinking about general case and hence wasting the whole time :(

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I know there's an easy solution for D, but what if the sides can be even too? I think this will work, correct me if I am wrong: Create 2 arrays, one for vertical sides and one for horizontal sides, sort each of them by y/r, then by beginning and end of a side. Then we just use two pointers to find all intersections of rectangles and build a graph. Then just DFS in this graph. I tried to implement this but the round ended. Do you think it will fit into the time limit?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    This way the problem is NP-complete. Given that n ≤ 105, it cannot be solved in 2 seconds.


    Nevertheless, I did a blind try 24386589 =)

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      What, the complexity will be O(nlogn).

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Then, probably, I don't understand. Could you, please, explain how would you use DFS to color the graph?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For some reason I believe you can do greedy approach while scanning through the rectangles from left to right. Does that seems plausibly true?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          First we create the graph itself by creating arrays for vertical and horizontal sides, then sort them(nlogn) and then iterate through this array using two pointers(linear). The resulting graph has O(N) vertices. We just start a DFS from some vertice, DFS all its neighbours and their neighbors and try to colour the vertice in a colour that its neigbours don't share. I think this should work.

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Define F(a) as the number of neighbors of rectangle a.

          1) sort these rectangles by F(x);

          2) for each unfilled rectangle: fill an available min color, do 3);

          3) for each rectangle's neighbor: do 2).

          I am not sure if it's right...

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            This might work. But why do you need 3 if you have already sorted them by the number of neighbours?

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Sorry, my mistake. In fact, I tried BFS, just visit each neighbor by F(x)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thats what I did in contest. But for some reason I get WA on test 1 while it works on my compiler.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Not joined the contest, but isn't it related to parity of corners?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my second time to participate in codeforces, and now or unrated, I hope this will be integral.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems. I really enjoyed. ty

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

When will be rating updated ?

»
9 months ago, # |
  Vote: I like it +39 Vote: I do not like it

After seeing this 24373708 solution for Div2D/Div1B —

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Amazing solution. I start thinking that D was very easy problem after seeing this :)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    That's nothing. 17059723 was once the correct answer to a Div2D.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      That was easily guessable :| But what happened in this round is speechless. Almost everybody didn't expect to have this kind of solution :(

      I have another one also — 23720774 Div2D :P

»
9 months ago, # |
  Vote: I like it +25 Vote: I do not like it

It seems the standings page is a bit bugged.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please tell why 24374429 is giving TLE for problem B. Simple O(n) loop.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because u used scanner , if u used the buffered reader it would have been accepted which is kinda bad

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Due to slow response time of the website and slow rating changes, this contest will be unrated.

Have a great day!

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Problems like today's Div 1B make me feel handicapped :| Such an easy solution, yet I was nowhere near it during contest

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My head is hurting very much for not being able to solve. Uggh. I hope intuition comes by practice.

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

it so unfair to solve a simple problem in o(n) to recieve a TLE because of input time , this is the first time this happens to me on codeforces , i dont wanna bring up the conflict of java vs c++ but this shouldnt happen :'( http://codeforces.com/contest/764/submission/24371107 http://codeforces.com/contest/764/submission/24388501

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am a java person too.

    For large inputs you need to use BufferedReader for input, and for large outputs you need to do PrintWriter.

    CodeForces has done this to me multiple times. It sucks I know.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i never faced this problem here before although i took inputs very much similar to this problem if not larger , still i though it was similiar to c++ 's cin/cout vs scanf/printf but i guess i was wrong >.<

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial ?

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is it just me or Codeforces lags really hard?

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think this solution for Div2C should get TLE or something like that on the following test:

100000
1 2
2 3
3 4
4 5
.
.
.
99999 100000
1 1 1 1 1 ... 1 2

but it gets Accepted...

»
9 months ago, # |
  Vote: I like it -10 Vote: I do not like it

How can O(z^2) algorithm get Accepted in Div2 A. I was trying to hack this code by giving the test case 1 1 10000. And I think this code does 10^8 operations for the particular test case. Then why didn't it gave TLE?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    TLE starts from 109 operations. In a good day you can even try to fit 109 operations in one second.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I see! But is it only for codeforces or for all other online judges(like codechef)?

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I don't know about codechef, but it is also true for topcoder.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On my PC it runs in about 1.2-1.3 seconds.

»
9 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

It seems that some people knew that C appeared previously at Saratov training camp.

Compare the following 2 solutions: 24379628 24373544

There may be other people with the same code but I assume the plagiarism test should detect it. What will be done in such a case?

Edit: Huh, looks like nothing has been done. platypus179 are you going to overlook this?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Et tu, moejy0viiiiiv? How sad.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    I have read such sentence in the rule: Solutions and test generators can only use source code completely written by you, with the following two exceptions: the code was written and published/distributed before the start of the round, the code is generated using tools that were written and published/distributed before the start of the round.

    So I don't think it is cheating.

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Well, yeah, it's not cheating obviously because you didn't share it with anyone else. I didn't know about the rule you quoted(I've never even read the rules, heh). I just supposed that the plagiarism test would detect this and some kind of announcement would be made by the authors.

      So, in conclusion, it's fine to use code that was published before the start of the contest and it's the responsibility of problem setters to guarantee the originality of the tasks.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I must ask how did you find this problem? Did you remember it from solving or was it some very clever Googling? I am very impressed because the problem statements are fairly different, even though it is the same problem I suppose :)

»
9 months ago, # |
Rev. 3   Vote: I like it +41 Vote: I do not like it

It looks like two first coder's solutions for div2E is same. Compare:

24380405

24382432

UPD: their D codes looks similar too

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    and they are from the same school :|

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    High possibility that both two ids are fake id of a red coder :| Their graph's are same too :| But going trough their past submission it seems that they write code in same style .. :) Since they both from same institution :) But there are still many codes that they shared :| :| i.e exactly same

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +14 Vote: I do not like it

      No,No,No,our school training program always contains many problems in codeforces,so we ususally solve the same problem.We share our solutions,because our teacher encourage us to have discussions together,it's a part of our study program,too.

      If you say we are fake id of a red coder,that's interesting.And I really hope my id can become a red id one day.:)

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    First,I have to say that this problem has been done by all of my classmates in our teams.As you know,we come from the same school and the same city,and I want to tell you that div2 E has appeared in our school test we attended in the past.

    Also,that problem has been published by our fellow students in China before,our teacher can prove that we all solved the problem ourselves,because she has told us the solution to the problem a month ago when we first read the problem which is similar to the div2 E(maybe a little different,but the solution is similar,too).

    If you say we write code in same style,what I want to say is that we have studied together for two years,and all of my classmates' styles are the same.:) I have to say if the code has been written and published before the start of the round,if I need to write it again,and our classmates are taught by the same teacher,and we all have the solution by our fellow students,it's not difficult to explain this situation.

    div2 E is a difficult but intersting problem,I hope you can solve this problem soon,too.:)

    UPD:div2 D is also a interesting problem ,maybe everyone who has solved this problem used the same solution.:)

»
9 months ago, # |
  Vote: I like it -26 Vote: I do not like it

is it rated ?? Div 2D problem — can't be better !!

»
9 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Why rates changed for previous contest?! :|

UPD: It's fixed now

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

There is something weird going on. The ratings for Round 394 are getting updated in few profiles.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this —

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B was copied :-|

Tournament of Towns problem 5 is div1 B exactly!!

»
9 months ago, # |
  Vote: I like it +25 Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm new to competitive programming. and this is my first contest that I have managed to solve at least one problem; although it became unrated, I learnt a lot!

»
9 months ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

my solution for Div2C get Accepted http://codeforces.com/contest/764/submission/24389994 but this solution should get WA on the following test :

11

1 2

3 2

4 2

5 2

6 2

7 2

8 2

9 2

10 2

11 2

1 1 2 3 4 5 6 7 8 9 10

Weak tests!!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell the hack for question B of div2?

»
9 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Finally purple ^_^

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Very nice contest. I like C task!!!

»
9 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

The testdata for the C is weak, This code 24392371 passed

It doesn't pass this case:-

4

1 2

1 3

3 4

4 1 5 3

I sent it during the contest then i realized that the idea is wrong so I changed it but I was surprised after the contest that it passed system tests.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/763/submission/24391818

Hey guys just wanna share a greedy solution to the problem Div2C I just came up with. First I have to find all the connected pairs which has different color. Then I divide by 2 because some will be repeated. And then I will just find out if there is any vertex that has the same amount of connected vertex with different color as the total sum. That vertex will be the root. Hope my solution help.

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    There is a better solution Store all the edge which connects two node and both the node having different color. Now in all this edge there should be only one common node. If there is then print yes and that node. Otherwise print no. There will be one more case in which every node have same color then in this case print YES and any node.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I came up with an O(n^2) solution for the second exercise but I got a TLE. Was the maximum time limit allowed O(nlogn)?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    there is a simple O(n) algorithm

    note that each item i will be swapped several times against n-i+1

    more precisely, each item i will be swapped min(i,n-i+1) times with its counterpart

    so you check whether each pair will be swapped an even or an odd number of times, if the number is odd, then it is the same as 1 swap, is it is even the same as no swaps

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Wrong : vector < bool >can_be_child (true,N);
Accepted: vector < bool >can_be_child (N,true);

Took me an hour to notice that bug.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how did the first one got right answer in first 6 cases ! o.O o.O

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It surprised me too. Actually vector < bool > C(true,N) is equivalent to C(1,N).
      It creates a vector of size 1 and initialized it with N. As N!=0 it is taken as true. Hence C(true,N) is equivalent to C(1,true). So basically It created a vector of size 1 initialised with true, but except the first value all other values(extra spaces of vectors) will be false by default.
      Unfortunately all inputs tll tc 6 were such that initialization values didn't affect final answer.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by platypus179 (previous revision, new revision, compare).

»
9 months ago, # |
Rev. 8   Vote: I like it -20 Vote: I do not like it

shouldn't all div2 C solutions be re-judged with stronger tests since the test data was weak ? (and accordingly updating the standings and rating changes again)

EDIT:

note to be clear: weak test data of problem C in div2 is not an argument in my imagination, there are two comments or more in this comments section which are describing that their codes give wrong answer on test cases they wrote in their comments but despite that their codes are accepted.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Div.2 D is allsome…… -_-||

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Getting TLE on DIV2 C . My logic is : First i store those edges node to set those which color are different , then i put a simple dfs on each of the node assuming as root which stored in set , now which node will fulfill properties of root i break the loop and print it . If i aint found a node , print no . Now I understand for which case i got TLE . If i can stop calling dfs again and again , i can reduce TLE . But can find the logic .

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No need for doing dfs There is a better solution Store all the edge which connects two node and both the node having different color. Now in all this edge there should be only one common node. If there is then print yes and that node. Otherwise print no. There will be one more case in which every node have same color then in this case print YES and any node.