niyaznigmatul's blog

Codeforces Round #467
By niyaznigmatul, 7 years ago, translation, In English

Editorial

Hello!

Codeforces Round 467 (Div. 1) and Codeforces Round 467 (Div. 2) will take place on February, 25 at 14:35 UTC. Most of the problems are Innopolis Open Olympiad in Informatics problemset. We ask olympiad participants not to take part in Codeforces rounds and not to discuss the problems till the end of the rounds.

Problems were prepared by: niyaznigmatul, pashka, vintage_Vlad_Makeev, VArtem, burakov28, budalnik, YakutovDmitriy, dusja.ds, GreenGrape, tourist. We thank testers: demon1999, craborac, the_art_of_war, qrort, .tx, izban и julsa.

Good luck!

UPD: The round is rescheduled to +1.5 hours to avoid collisions with other events.

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

Comments Comments (270)
| Write comment?
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Hope the problem statements are as short as the announcement!! :D

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

There are some users who regestered in div.2 round before the rating change of round 466 and now they are div.1

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

    did they ever fix the one where the educational round let div1 participate in div2

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

      It wasn't a bug to be fixed. It was totally intentional.

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

        So it's intentional that a purple user can farm rating in contest strictly for < 1900? Where did they ever say that's intentional?

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

          The results of educational round was announced after div 2 contest so it was made rated for everyone who were div 2 before the educational round. Participants want to know whether it's rated or not before they participate in contest. The only fair way to ensure this was to make it rated for everyone who were div 2 before educational round. As you say you can't simply "farm" rating. I actually dropped from div 1 back to div 2 after that contest. Whoever had rating increase totally deserved it.

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

          official comment (http://codeforces.net/blog/entry/57819?#comment-414872)

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

    Anyone in particular you have in mind? I only see a handful of >1900 people in the div2 results and it doesn't look like the competition counted towards their rating.

    → Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it -66 Vote: I do not like it

This round will be held in usual time. It's good for someone.

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

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

It's the first time ever I've seen a contest with 10 distinct writers :O

Let's hope for a quality contest with no interference from DDoS and server issues ;)

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

Round# 467 is a prime number while contest(div. 2) 937 is a prime number, too!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    Problem A: 

    467 and 937 are lucky numbers, given a string count..
    → Reply
»
7 years ago, # |
  Vote: I like it -60 Vote: I do not like it

I have found the name tourist in the problem setter section :D

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

10 problem setters , sir tourist is also here , i think this contest problems are too much perfect and malleable , too much excited :)

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

Hopefully the number of problems is less than 10 considering there are 10 problem setters xD

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

My brain singing "I want something just like this" :p

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

How many problems are expected? There are many setters

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

So is contest starting at 16:05 UTC now?

Edit: I realised later I can see the time in Contests tab.

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

Hope a round whose time is good for East Asia users!!!

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

Please make this round visible in a "Pay attention" section (can't see it in RU version) and include it into the list of upcoming events! I found this round only accidentally.

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

tourist as setter in Contest #2 of 2018 (Contest #1 — Hello 2018).

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

It is not good to change the timings at the last moment as all my plans are getting disturbed.

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

So sad it delayed.It is 12:05 UTC+8 now :( I know I'm not that good at programing,but I just want to join in the contest for fun... (Unhappy Chinese pupil)

BTW,will my comment be hidden because too negative feedback?

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

The comment is hidden because of too negative feedback, click here to view it

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

Why the delay...? I want to know what those "other events" are?

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

so what about score distribution?

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

Got up early on a Sunday morning for a contest and found it delayed like.

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

I can't participate in this contest because it delayed. But I have registered. So the question is: will my rating be influenced if I don't participate. If yes, what should I do?

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

I know the event today.

it's VK Cup 2018,not tourist's marriage.:-)

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

Although I was very busy at work but came home earlier for the round, and see that the scheduled time is changed. For next rounds, I suggest to change date or time at least a day before the round.

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

Events like Chelsea VS Manchester United :)

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

    original time would have been better, I would have been able to watch Man City vs Arsenal! much better than chelsea vs united

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

I'm too worried about codeforces server errors during the contest. Let's that it'll not happen again.

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

please post the new score distribution.

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

Hate the time delaying. The new time conflict with my sleeping time

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

I hope this contest will make me green !.. I just need +75 rating to become a green coder...

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

Hopefully it will be a cool contest.

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +66 Vote: I do not like it

I hope, systesting of VK cup will be turn off during the round.

UPD: So you haven't done this...

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

I think all of you guys should stop arguing. Codeforces is a programming website, not a quarrelling website!

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

Came here to read funny comments but man wtf?!

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

to CF Server : DON'T FREEZE.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -50 Vote: I do not like it

From my school years I remember this olympiad as a trash. Seems like not much have changed. No offence.

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

    No offence

    But it was offensive

    Btw why?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it -41 Vote: I do not like it

      Cause it's just my opinion, and I don't wanna be rude or something. Just really don't like it.

      Low problems quality. When I participated, it was 4 very-very easy (like div2 A) problem with a lot of stupid coding, and one hard geometry problem. So the places were distributed by points in only one problem (on olympiad there are problems with subproblems, you get points for solving subproblems, no time/resubmit penalty). This time they are harder, but still boring/stupid.

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

        Yesterday's difficulty distribution was good though :)

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

        I don’t know which problemset you are talking about. Any link would be helpful.

        You are welcome to become one of the problemsetters, if you have "not stupid/not boring" problem ideas in your mind.

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

        Don't be angry because you can't solve them

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

Unrated Round cy >(

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

fucking long queue!

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

What is this? There is 10 pages long queue. (~700 submissions only in div2)
Make this round unrated >.>

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

Today's day is so good : I am performing wonderful in the contest and queue is helping me in it :)

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

what is this? This much Queue

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

goodness me there is a 10 page+ long queue. Please fix it asap!

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

13 page long queue ! what is this !

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

You know the queue is so long when you're in Div.1 and the "In queue" verdicts' region is wider than a 50-line page...

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

Shit man! I really hope the round won't be unrated because of the long queue.

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

It's taking a very long time to process submissions...

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

The judge is running too slow . so frustrating at times .. look into it

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

Tomorrow is my Exam but still i'm giving the contest to get away from the stress situation but these long queues of codeforces are giving me more headache than my syllabus did.

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

Are DIV 2 Contests getting harder or I'm the one who is getting dumber ??

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

What the hell is pretest 10 in C?

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

how to solve DIV2 : B?

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

    Check if there is number from y to y-300 that is not divisible by any number from 2 to p. 300, because prime gap is at most 300 in this number range

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

      prime gap is 300?

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

        Yes, maximum distance between two primes is a bit less than 300 in range from 1 to 10^9

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

      "because prime gap is at most 300 in this number range" can you please elaborate it a little?

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

        You can find it on wikipedia, just search for prime gap

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

          thanks mate! I have wasted my 20 mins on this:(

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

      since p can also be of order 109 checking in [2, p1 / 2] [2, min(n1 / 2, p)] is enough.

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

        Please explain a little why we check only till sqrt(p)

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

          If P has any divisors, it can be written as a*b. Now, if a is less than sqrt(P), then b must be greater than sqrt(P). Therefore, either a or b is greater than sqrt(P). So, if divisors exist, we only need to check up to sqrt(P).

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

        can u help me to figure out why this is wrong my submission

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

          You are only checking divisibility up to mn = min(1000LL, p); but should be sqrt(y), since y could be 1E9, whereas 1000*1000 = 1E6.

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

          mn = min(1000LL, p);

          why 1000?

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

      prime gap: https://en.wikipedia.org/wiki/Prime_gap

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

      what if p is 10^8 or greater. wont it get TLE

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

        You check for prime divisors of i where y-300<=i<y. If divisor is less than or equal to p, i is not the answer. So you check for sqrt(i) numbers

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

    Then why is this solution wrong ?

    https://ideone.com/3YAlQZ

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

      case 2, 9 answer is 9

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

      the solution need not be prime everytime. The only condition it must satisfy is that in the range [2, p] it doesn't have any factors!

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

      Thanks guys. Silly bugs everywhere :(

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

    You don't need to do calculate any prime gaps, just work backwards from y. Because you know that there won't be a huge prime gap, you are sure to find something pretty quickly. http://codeforces.net/contest/937/submission/35691076 Just be sure to leave the loop once you find it and to only check up to sqrt(y) when searching for divisors

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

      How to calculate the time complexity of your code WolfBlue

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

        In the worst case, outer loop runs until we find a prime number, so when calculating the complexity you need to use prime gaps, but you don't need to actually know the exact value to implement it, just know it is relatively small. Let P(n) be the largest prime gap. Complexity will be O(P(y) * sqrt(y)). Because you are checking up to sqrt(y) to find divisors, and you are doing this at most P(y) times.

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

How to solve Div-1 C?

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

    First turn the string into a permutation, that we want to transform into 1,2,...,n. Then, starting from n/2, start constructing the string. In a single step, do: 6789...5... --> ...6789...5 --> 5......6789 --> 98765...... This reverses the string we've built, and adds the number we wanted to add to the end of the reversed string. Use this to append small and large numbers alternatingly. It takes 3*n = 6000 operations.

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

    I had similar idea to other one.But I wanted to share my way of thinking.I could easily come up with 4*n steps for building from one corner to another. But the 4*n was coming because each time the string was coming reversed so that wasted n steps to straighten in it. So doing from middle and adding a letter on each side we can get rid of straightening here.

    4*n approach: assume u have come to this form S.... S is suffix of required string . Now I will describe a method to convert it to Y.... where Y is bigger suffix by 1 than S. So now we find character before S in t and flip it there so now ....Y... we have.Now we have to bring Y to start for that we reverse whole string(...rev(Y)...) and bring rev(Y) to end (....rev(Y)) and now flip from just before Y giving Y..... . So main idea is getting rid of reverse whole string by doing operations from both sides.

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

      I extend the prefix like you do in your 4N approach, but each time I add a letter from a different end considering that s[0] and s[n-1] are adjacents. At the end the string may need to be reversed and/or rotated. Reversing it is simple: op(n). Then if it needs to be rotated X times, you can do that with 3 operations: op(x), op(n-x), op(n).

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

Problem E is fucking awesome (no sarcasm)

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

Again a good problemset... Thanks codeforces.

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

What is hack test for Div.2 D???

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

    Something like

    4 4
    1 2
    2 3 4
    0
    1 2
    1

    You can't win, but you can draw by cycle 2->4->2

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

      My code gives the right answer, thanks :D

      I was fearing something harder

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

        You can check also odd length cycle, then you must win.

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

          too many bugs in my solution, yet it passes pretests.

          seems like bad pretests

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

    Suppose, it was against invalid back path construction. It is not enough to build back path until start vertex is found, the additional condition of stop must be the first player in start vertex.
    Otherwise for the path like (1)->(2)->(3)->(1)->(4)->(5) the first player can win in case of complete path walking, but back path construction, with mistake mentioned above, brings to only (1)->(4)->(5) which is not the win of the first player.

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

What were the hacks for B?

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

May anyone tell me the core issue to raise a TLE in pretest 4 of Div1B/Div2D? ;)

Here is my last solution, sorry for the code being so messy...

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

    Maybe you didn't judge the condition when there is at least one circle in the graph,but there don't exist anyway to get to a point with a 0 outdegree,then in this case he could at least draw?

    I didn't pass all the pretests until the end of the contest(it may be something wrong with the output of the path),but I failed on pretest 4 previously,and after I found this condition and judged it I passed pretest 4...

    Hope it can help you,and sorry for my bad English

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

      Well, seemed like I got the issues. I did check for such, but I was totally careless when handling my condition-checker in return commaands.

      Not sure if it could save me from TLE-ing, but at least it was wrong.

      Thanks ;)

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

MATH, MATH, everywhere MATH.

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

Hack for D div 2:

5 5
1 2
2 3 5
1 4
1 2
0
1

Expected :

Win
1 2 3 4 2 5
→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    What is the answer? Edit: You already edited your comment. Thanks !

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

      Sorry I forget to write the answer ... I edited it

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

    Thanks, i hope my solution is right.

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

    how the answer can be win ? when petya moves from 1 to 2 vasya will move from 2 to 5, as both will play optimally. so how can petya win?

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

      They don't play optimally, Petya plays for both of them.

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

        ohh ! I wrote the condition for optimally well. As i thought that petya checks whether he will win the game no matter what vasya will move after sleep, or make it draw. And how did it pass the pretests ? As the checking condition itself is entirely wrong

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

          And how did it pass the pretests ?

          pretests are weak in this one, probably intentionally. which is a good idea for div1-B but not good for div2-D.. but i guess thats a disadvantage of mixed round.

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

          Your solution fails for this:

          3 3

          1 2

          2 1 3

          0

          1

          Answer is Draw.

          Idk how you passed pretests, I guess they are weak

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

            It fails for all cases as my checking condition itself is entirely wrong, as i misunderstood it.

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

https://postimg.org/image/ts93ksg85/ still waiting :)

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

Can someone please explain the logic for solving Div2.D/Div1.B ?

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

    You need to reach a childless node in an odd number of steps to Win. You can track the parents of all nodes that can be visited starting from s in an odd and even number of steps and their in a 2*n array.

    If one childless node can be visited in an odd number of steps, you win. Else, you draw if there is a cycle attainable from s. Otherwise, you lose.

    Edit : my condition for cycle detection was wrong. You have to check explicitely for cycles starting from s to differentiate draw from loss

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

      Nice. Thanks !

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

      Not really. If a cycle has a way in and a way out, which lead to a childless node by an odd number of steps, you can still win.

      Also, if a cycle has an odd number of sides, any path from it to an arbitrary childless node can lead to victory as well.

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

        how to check if there is an odd cycle?

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

          (Actually, I wasn't able to solve it probably — it got TLE verdicts).

          Since I can't handle cycles properly, I used Kosaraju's algorithm and divided vertices into SCCs.

          Then, the condition to call each DFS function is to check if there has been a path from s to that vertex with odd/even number of edges (based on the oddity of the currently working-on-vertex).

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

          can u tell me why my code is wrong http://codeforces.net/contest/937/submission/35735167

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

            For the failed case, Someone else marked vis[node] = 2; for node = 45.

            So, when you tried to end game by visiting 45, it was already visited in some path so it was never even tested.

            Basically, you aren't trying certain paths once that node is visited in some other path.

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

        If you (implicitly) create a bipartite graph G', with twice the number of the original graph, one vertex for each (vertex, parity) setting, and the same relative neighborhoods and perform a DFS on that graph, this case will be treated without having to explicitly detect odd cycles.

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

          Hi, Can you suggest some readings/problems based on the similar idea? A lot of programmers have used this technique, is it well known?

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

        My algorithm will go at most twice through every edge : once when you reach him with an odd number of steps, and once when you reach him with an even number of steps.

        I believe this takes care of these two cases

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

      How do u calculate if a childless node can be reached in odd number of step(I mean there could be cycles)?

      Thanx in advance!!

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

        Is this solution correct?

        We have to reach the start node from childless node in odd number of steps.So lets say we color the nodes starting from the childless node.lets say i color the childless node with black.So i'll color its adjacent white.So the question comes that whether the source vertex can coloured white.

        So just do a sort of bfs with two visited array ,vis1 to denote if it has been coloured black,vis2 to denote if it has been colored white.

        push all childless node and start the normal bfs,i mean if i am black and my adjacent are not white then push them,else dont.

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

        each time you visit a node, mark all his children to be visited with the opposite parity, if they have not been visited with this parity. You'll find out in O(n+m) if each node can be reached in an odd or even number of steps, then you can check the childless nodes one by one

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

          will this handle the cases where there is an odd cycle in the path from s to any vertex?

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

Could anyone give any hint to solve div2 D?? Thanx in advance!!

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

    Just replace any vertex v to vertex (v, 0), (v, 1) and any edge u -> v to two edges: (u, 0) -> (v, 1) and (u, 1) -> (v, 0). Now you can do simple Dijkstra from (start, 0).

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

If you pass pretests on a submission and then get compilation error on the next, does the accepted solution go through system testing or does cf take the last submission even if it gives WA/compilation error?

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

In div-2 D, when I tried to hack and got unsuccessful attempt, I realize I misunderstood...

I thought the real Vasya starts after some point, So for have a draw, in every possibility they cannot get out of the loop .

3 3

1 2

2 1 3

0

1

my answer is Lose for it although the real answer is Draw :(

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

Another hack for B. Although i din solve D, as i found the test case in which it will fail 35 min before the end and i could not find the solution, this is it. 8 8 1 2 1 3 2 4 6 1 5 1 1 1 7 1 8 0 4 ans is win and 4 5 1 2 3 6 7 8

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

For div2d ..

if: find any path to a leaf and it's vasya's turn --> win

else if: cycle --> draw

else: --> lose

What's wrong ?

Edit: never mind. My code contained a bug

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

    else if: cycle --> draw
    You must also check if you can reach that cycle.

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

    if: find any path to a leaf and it's vasya's turn --> win

    also, any path can contain itself contain a cycle (might not be required to traverse same cycle more than once though, not sure)

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

    The fact is that while traversing if you en-counter a odd length cycle, it can be used to change the parity and reach the same state with the other parity of the solution.

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

How people could solve problem C in 1 minute? Like LoDThe.

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

in D div 2, assuming both petya and vasya play optimally well right?

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

    Vasya doesn't even play how he can play optimally lol.

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

    No we have to favour petya (check test case 1) vasya can move 1 -> 2 -> 5 but we favour petya thats why 1 -> 2 -> 4 -> 5

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

      since petya plays first, how will he wants to lose. And what i thought is petya is checking whether he will win, if tomorrow vasya gets up from sleep and play optimally. AND by the way how did it pass the pretests ?

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

        you are checking petya can win or not irrespective of how vasya will play, if vasya will play optimally there is no way petya can win in first test case.

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

          He can. if petya goes to 3, instead of 2, He will definitely win, As petya moves first.

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

            yes if petya will play 1->3 than vasya can't, but both the moves were made by patya, so petya is playing optimally, and vasya's moves always favouring petya

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

In problem D : my codes second one is correct :( :(

Unable to parse markup [type=CF_TEX]

https://www.diffchecker.com/FXKB7hnM

UPD : second one also wrong ! :))

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

long queue but nice round, hope rated!

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

4 4 2 2 3 1 4 1 4 0 1 hack for div2 D: ans is lose

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

    Doing the hard work but getting WA due to wrongly implementing cycle detection as in a non directed graph = priceless

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

      pretests were too weak.. i was using 0 indexed vertices instead of 1 indexed vertices in dfs and still it passed the pretests

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

Can anybody tell me what is the time complexity of this code for DIV2 B.

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

Late hack announcement! Little too late!!!

I submitted Div1B in 01:22:38 and it was hacked in 01:31:59. Room

But I didn't get any hack announcement notification during the contest time. I checked my submission couple of times in Room standings and Common standings but didn't see that it had been hacked. Even, I refreshed the main Problems page and standings page after the contest had ended, till then it was in "pretests passed" state instead of "hacked". I only got a hacked notification during the system testing. I didn't take any screenshots for proof as now I think I should have (sorry). Now I am thinking, how much a late hack announcement/update can affect a contestant? Also had anyone else experienced this?

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

    My Div1B was also hacked without giving me a pop-up notification whereas it should be given immediately right after a submission is hacked in normal practice.

    Luckily, in my case the verdict showed correctly with "hacked" in "My submission" page. As a result, I was not affected by the missing of the pop-up notification after all.

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

Poland stronk!

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

Ooops! Something has broken down in Codeforces :<

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

In Div2 problem C: what is the correct output for this test case: 999999999999999999 999999999999999998 1000000000000000000

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

    1000000000000000000.93750000000

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

      i got 1000000000000000000.93750000000 and 1000000000000000000.00000000000 and 1000000000000000001.00000000000 from different accepted codes

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

        hmm.. I think its something about the precision. Mine returns the .9375 one

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

        Thats because mod(x-y)/max(1,y) should be less than pow(10,-9) which is true for all accepted code

        x,y are expected and actual output

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

    I am getting 999999999999999998

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

    1000000000000000001 here (on AC code).

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

    1000000000000000001 to be exact, but just 1.0E18 works

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

How did LoDThe solved div2A at 00:02:12 and div2C at 00:03:38 in div2?

No one in the top20 positions in div1 solved div2C in under 4 minutes, and he even solved A before!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 6   Vote: I like it +26 Vote: I do not like it

    He took part in offline part. Just cheats and no more.

    P.S. His name is Igor Balyuk

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

      Shouldn't this be taken care of? Because it'd affect the rating change. I mean if he took part in the actual contest before, then it's not fair.

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

        hope :p

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

        Of course it wasn't fair. I believe somebody should fix it.

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

          And the rating has been updated, they won't fix it :( And I'm only 2 short from being a Candidate Master :( It's not fair. I would have been Candidate Master if he didn't participate :( I'm so frustrated now...Can't anything be done?

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

          I write to niyaznigmatul and KAN about this problem and don't get any feedback. Lets think it's legal to cheat on rounds.

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

D went from ~400 ACs to ~70. E F F C Y C L E S

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

I got WA for problem DIV2 D on test 28 which was:
Participant's output
Win
233 971 277 477 871 502 673 37 219
Jury's answer
Win
233 864 714 151 370 604 141 233 971 277 477 871 502 673 37 219

what was wrong ?

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

    Your answer is an odd length, the correct answer must be even length...

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

    To win you have to have a path of even length

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

      I made a terrible mistake while printing path :(

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

        If it makes you feel any better, I made the exact same mistake. :(

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

    Well, to win you need go from 233(turn First Player) to 233(turn Second Player).

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

Why am I getting the wrong answer for div2B. I used the segmented sieve and I am getting the correct answer when I run it on my pc.Here is the code..

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

    You mean to say you're getting the correct answer for the case that is failing?

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

Testcases for E are too many..

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

Currently, Div.1 contest doesn't have a final result yet, because of this.

If molamola.'s solution for Div1E is correct, he/she will make it to the 3rd place. Cheers! ;)

UPD: Accepted. Congrats!

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

i got wrong answer in C-Div2 because the output number was in double format like that 7.67538e+017 insted of 767537647587662141 , so is that my fault or the judge fault

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

Running the same code on the computer gives different results from that when it's run from the judge! Link

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

    In this function:

    int divs(int x)
{
    for(int i=2;i<x;i++)
        if(x%i==0)
            return i;
}

    You didn't handle the case when x is a prime number. It is an undefined behavior, therefore the result it returns may differ from varied compilers.

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

Rating changes take forever when you want them to be quick.

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

Yes.

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

    Never purple again! Congrats!

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

Hmm.. Feels like someone was writing div1 and div2 contest in the same time http://codeforces.net/contest/937/submission/35707300 http://codeforces.net/contest/936/submission/35706280

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

    It doesn't make sense. Why did he do that? I could understand testing div1 solutions on div2 pretests, but he submited div1 earlier than div2...

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

Can somebody please tell me why my code for D gets a TLE at pretest 4? Link- http://codeforces.net/contest/937/submission/35711753

For some reason, the DFS function is running into an infinite loop- but according to me that shouldn't be, as I am using the recur[u] to act like visited[u] in a way. I used the fact that, the only way when recur[u] will be 0 again after becoming 1 is when the DFS of the subtree of u ends- else its a cycle which we detect and exit such visited nodes.

Any test case or help is appreciated. Thank you :)

(I know this can Time out for larger cases, like, vertex s leading to n/2 nodes, and all those n/2 nodes leading down to same chain of length n/2. Like a long-tailed kite. But why is it getting TLE at pretest 4 with n=50 is bugging me :( )

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

    After done With current node you are allowing others to come back to the same node later on. Many node can come back which points to this node causing infinite’s loop.

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

Hi guys, while you are waiting for editorial, I'll try to help you to solve problem D.

So, our task is to find a uneven route to a leaf-vertex (a vertex that has no edges coming from it)

The answer is Draw, if the graph doesn't contain leaves at all.

If the graph has a leaf (leaves). But a route to each is only even, we need to check whether the graph has a cycle. If it does — the answer is Draw else the answer is Lose.

If the graph has a leaf with an odd route to it the answer is Win.

Now our task is to output the way to our leaf. We should be careful with it and not break a while(probably :P) cycle if our route at the moment is even!

How can we code the written above? I think, that one of the easiest way is to write a bfs and check the following:

"If we can reach a V-vertex with an uneven route then we can reach TO-vertex with an even route. And vice a verse"

My solution is here. Feel free to ask me some questions. GLHF

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

Too eager to know solution for Div2 E/ Div1 C.. help required

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

    The cleanest solution I've seen is if you perform the operation on x = n, then on x = i, then on x = 1, you move the ith character to the front, e.g. if we want to move the c to the front:

    front|c|back (ignore the |'s)

    -> kacb|c|tnorf (x = n) -> frontkacb|c| (x = i) -> |c|backfront (x = 1)

    Using this operation, you can repeatedly build the string in reverse order, using at most 3*N < 6100 steps.

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

      Oops formatting:

      front|c|back

      -> kacb|c|tnorf (x = n)

      -> frontkacb|c| (x = i)

      -> |c|backfront (x = 1)

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

        Thanks. Got it . xD

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

          I think it would be x=i since after the first operation the character is in the n-i'th position.

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

            Got it man. Thanks. by the way your last ans is wrong. it should be |c|frontkacb

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

I am seeing some pretty complicated submissions for problem B — Vile Grasshoppers.

The main idea is that the distance between consecutive primes upto 10^9 is never more than 300 or so. This allows us to start from y and keep decrementing, till we get a number who's smallest factor is greater than P. Worst case, we will not have to do more than 300 root(n) factorisations.

Explanation and code.

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

Lost ~1300 points because I didn't use std::fixed in the output of Div2/C...

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

Can anyone tell me why my solution is failing at test 28?

http://codeforces.net/contest/936/submission/35722758

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

    Cause in your solution you do not consider paths like 1->2->3->1->4->5 when you can return to previously passed vertex and still win, I guess so.

    Check this out:

    5 5

    2 2 4

    1 3

    1 1

    1 5

    0

    1

    If it returns "Draw", your solution is wrong.

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

When can we expect editorials ?

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

Hey in the C problem of div. 2 one of my friend's code got accepted and as I was going through the test cases I found this(refer link). How is this possible? https://drive.google.com/open?id=1scjEnYJuRpkfcu2gPGvJRpBm94NcH1sH

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

    Everyone who solved C has this problem, but the answers are definetely right

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

How to solve Div2 C?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 5   Vote: I like it +14 Vote: I do not like it

    Our goal is to find how long will be a chicken in a fast mode and in slow :D.

    So, in first k minutes chicken will be prepared for ((k/t)*100)%.

    fastMode=((k/t)*100)

    Now we need to find a moment of time when Julia will again switch chicken to fast mode. This moment will be f:

    f=ceil(k/d)*d => (f-k) minutes chicken will be in a slow mode and will be prepared for ((f-k)/(2*t)*100) %.

    slowMode=((f-k)/(2*t)*100);

    So total time of that cycle is k+(f-k). After each cycle our chicken will be ready for fastMode+slowMode%.

    Now let's find out how many full cycles we will be able to "put" in our 100%. That is floor(100/(fastMode+slowMode))

    At that moment our answer=floor(100/(fastMode+slowMode))*f

    Finally we need to check how many percent of chicken preparation left left=100-floor(100/(fastMode+slowMode))*(fastMode+slowMode). If it is equal less than (k/t)*100 then we just add to our answer (left/(fastMode))*k, else ans+=k, left-=fastMode and then ans+=(left/(slowMode))*(f-k)

    Yeah, I see it looks quite complicated , but you are free to ask questions. Maybe my solution could also help.

    ** P.S. When I was using % (multiplying by 100) i received a WA on test case #32. On codeforces compiler answer was "nan" while on mine it was OK :( **

    UPD Corrected a formula

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

      If d > k then your algorithm will give f = 1 => f-k = 1-k(negative for k > 1) minutes chicken will be in slow mode. Isn't it undesirable? BTW thanx for great explanation.

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

        Yeah, I did a mistake Correct is: f=ceil(k/d)*d

        Thank you for your answer.

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

      This solution is correct but the formulas can be simpler:

      Indeed, the chicken is cooked in fast mode for k minutes then, for d — k mod d minutes. Indeed, after k + (d — k mod d) minutes, you will be on a multiple of d. So the lenght of a cycle is of k + d — k % d. The formula for the number of cycles : cycles = t / (k + (d — k%d)/2)

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

      When I ran your code for k = 2, d = 5 and t = 10 it outputs 14 whereas the answer should be 12, shouldn't it? or am I missing something?

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

        The correct answer is 14.

        After first cycle: chicken is prepared for 4/20+3/20=7/20; TimeTaken=5;

        Second cycle: chicken is prepared for 14/20. TimeTaken=10;

        Third cycle onlyFastMode: chicken is prepared for 18/20. TimeTaken=12;

        We need to prepared chicken for 2/20, while using fullSlowMode we will prepare it for 21/20. That's why we need to use only 2/3 of our SlowMode. So the time of this part of SlowMode will be 2/3*3=2.

        TimeTaken=12+2=14

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

          As d = 5 when Julia goes to kitchen at t = 5 she will find the stove to be on. So she will not do anything and return. So The time period of one cycle comes out to be = 10.
          I guess you have taken time period of your cycle = d(= 5) which I think is be wrong in this case...
          How I visualized it is as follows

          When the clock is high it means gas is on and when it is low it means gas is off.

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

            You misunderstood the problem. The stove turns off by itself, but only Julia can turn it on. When t=4, who turned it on on your graphic?

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

              Yeah my bad I misunderstood the problem. Anyway thanx for helping me.

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

Editorial?

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

17 people contributed to this contest and there is no editorial after one day!!

UPD1 : a semi editorial is posted,hope to see the complete one!

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

    Perhaps Brooks's law applies to writing editorials, too?

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

      although i had to use wikipedia to understand your comment's meaning, but i'm agree with you :D

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

      I think it's more of bystander effect.

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

        I wouldn't call this round an accident. I quite liked problem C.

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

Why 35710602 WA ? Div2D

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

    Your problem is that you overlooked the case when you have a cycle with odd number of vertices where you should transverse the cycle to change the turn from Petya to Vasya and vice versa.

    Consider the following testcase:

    5 4
2 2 4
1 3
1 1
1 5
0
1

    This corresponds to a graph that has a cycle 1->2->3->1 but it still had an answer 1->2->3->1->4->5 Your Code gives a wrong answer in that case as it prints "Draw" instead, you just didn't handle the cycles with odd number of vertices case.

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

i was waiting for editorial but after a day now i decide to ask my question here...

how to solve Div2.D(Div1.B)?

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

where's the tutorial to the problems ?

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

pls, upload the editorials...

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

niyaznigmatul Div. 1 E doesn't appear to be viewable.

→ Reply