Блог пользователя niyaznigmatul

Автор niyaznigmatul, 6 лет назад, По-русски

Разбор задач

Всем привет!

Codeforces Round 467 (Div. 1) и Codeforces Round 467 (Div. 2) пройдут в воскресенье 25 февраля в 17:35 по московскому времени. Раунды основаны на задачах Олимпиады Университета Иннополис для школьников по информатике, но совпадают с ней не полностью. Просим участников олимпиады воздержаться от участия в раундах и обсуждения задач до конца раунда.

Задачи подготовили: niyaznigmatul, pashka, vintage_Vlad_Makeev, VArtem, burakov28, budalnik, YakutovDmitriy, dusja.ds, GreenGrape, tourist. За прорешивание и вычитывание спасибо demon1999, craborac, the_art_of_war, qrort, .tx, izban и julsa.

Удачи!

UPD: Раунд пришлось подвинуть на 1.5 часа вперед, чтобы избежать пересечения с квалификационным этапом VK Cup 2018.

  • Проголосовать: нравится
  • +335
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Почему бы не сделать раунд во время олимпиады?

Тогда и возможность нечестного участия тех, кто уже видел задачи, была бы исключена.

»
6 лет назад, # |
Rev. 7   Проголосовать: нравится -66 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -68 Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

How many problems are expected? There are many setters

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

So is contest starting at 16:05 UTC now?

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

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +106 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

labib attacked by chikunguniya :D please pray for him ;)

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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?

»
6 лет назад, # |
  Проголосовать: нравится -99 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

中国迎来了帝制,我无比的伤心。

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

so what about score distribution?

»
6 лет назад, # |
  Проголосовать: нравится +118 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +43 Проголосовать: не нравится

А что, вчера не было известно, что с квалификацией пересечется?

UPD Письма тоже не было. Очень некрасиво так делать, пишите тогда прямо причину — думали, что можно два контеста одновременно проводить, оказалось — нельзя.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know the event today.

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

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Events like Chelsea VS Manchester United :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

please post the new score distribution.

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Исправьте

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Hopefully it will be a cool contest.

»
6 лет назад, # |
Rev. 5   Проголосовать: нравится +66 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Came here to read funny comments but man wtf?!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

to CF Server : DON'T FREEZE.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -50 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    No offence

    But it was offensive

    Btw why?

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -41 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yesterday's difficulty distribution was good though :)

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +30 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Unrated Round cy >(

»
6 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

fucking long queue!

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is this? This much Queue

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

13 page long queue ! what is this !

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What the hell is pretest 10 in C?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve DIV2 : B?

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve Div-1 C?

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Problem E is fucking awesome (no sarcasm)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Again a good problemset... Thanks codeforces.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

What were the hacks for B?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

MATH, MATH, everywhere MATH.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

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 
  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, i hope my solution is right.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Nice. Thanks !

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        how to check if there is an odd cycle?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо за интересный раунд, надеюсь на + к рейтингу

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

long queue but nice round, hope rated!

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Poland stronk!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ooops! Something has broken down in Codeforces :<

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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!

  • »
    »
    6 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +26 Проголосовать: не нравится

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

    P.S. His name is Igor Balyuk

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        hope :p

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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?

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится +84 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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 ?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Testcases for E are too many..

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +75 Проголосовать: не нравится

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!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В div2 минут 10 как дорешивание открылось, а в div1 всё еще проверяется одна единственная посылка по Е... хорошо, наверное, что только одна)

»
6 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes.

»
6 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody please tell me why my code for D gets a TLE at pretest 4? Link- http://codeforces.com/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 :( )

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 6   Проголосовать: нравится +23 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Тем, кто участвовал в Бишкеке результаты олимпиады не сказали. Они есть вообще где-нибудь?

P.S.: футболки и прочие приблуды до Бишкека тоже не доехали. Вот печаль-беда =(

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Результаты

    Вроде и не должны были доехать. Площадки соревнований создаются для удобства участников, как минимум чтобы им не приходилось искать большое финансирование на поездку. К сожалению, кроме отправки приблуд есть ещё много организационных проблем. Приезжайте на основную точку проведения финала :)

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

When can we expect editorials ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 C?

  • »
    »
    6 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +14 Проголосовать: не нравится

    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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        Thank you for your answer.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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?

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Editorial?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why 35710602 WA ? Div2D

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

where's the tutorial to the problems ?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

pls, upload the editorials...

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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