Errichto's blog

By Errichto, 7 years ago, In English

Hello everybody!

On December 30 at 14:05 UTC/17:05 MSK (check your time zone here) Codeforces will host the New Year's contest Good Bye 2016. The contest is combined for both divisions, lasts 2.5 hours and contains 8 problems. Thanks to Harbour.Space and Barcelona ACM-ICPC Programming Bootcamp 2017 sponsoring the contest, winners can expect really cool prizes:

  • 5 best participants (not ACM ICPC veterans) will win free participation in Hello Barcelona programming bootcamp.
  • 30 best participants (not ACM ICPC veterans) will receive a 30% discount for participation in Hello Barcelona programming bootcamp.
  • 100 best participants will receive t-shrits by organizers and Codeforces.

Hello Barcelona programming bootcamp in collaboration with Moscow Workshops ACM ICPC is a competitive programming training camp to be held between February 6-14, 2017 at Harbour.Space University in Barcelona. Note that lecturers and coaches are: GlebsHP, MikeMirzayanov, Endagorion, Michael, Jacob and snarknews, so the camp must be valuable. The registration is open up to January 20th, 2017.

More information can be found here: http://in.harbour.space/icpc/

I'm an author of problems. I want to thank several people. MikeMirzayanov for creating Codeforces and Polygon and for allowing me to prepare this contest. GlebsHP for his help in everything (hope to work with you again!). mareksom for testing (other testers TBA). My sister for drawing. I also want to thank the Hello Barcelona organizers for providing nice prizes for you.

I'm proud of the problem set and I think that everybody will find something interesting for themselves. I tried to keep statements shorter than usually so it may be a good idea for you to read more problems and choose one that fits you. Obviously, problems will be about the New Year and a little polar bear whom you might know. Since you will face one interactive problem, please read the Interactive Problem Guide in advance.

Don't forget to register. I wish you great fun and no frustrating bugs.

UPD1: The points drop will be adjusted to the round length. It means that for submitting e.g. at the end of the contest gives the same percent of points as in usual 2-hour rounds. Also, I remind you that there will be an interactive problem (as mentioned above).

UPD2: In 750F - New Year and Finding Roots the interactor was printing neibhours in format "k t1 ... tk" instead of "k\nt1 ... tk" (in one line instead of two lines). It's my fault and I'm sorry for the inconvenience. If you were heavily affected, please write to me or GlebsHP. And thanks for noticing/guessing, Gassa!

UPD3, WINNERS

  1. Petr
  2. tourist
  3. rng_58
  4. mnbvmar
  5. Kostroma
  6. Rafbill
  7. Egor
  8. ainta
  9. al13n
  10. molamola.

Congratulations!

Thanks for participating. If you want to know intended solutions, see the editorial (it isn't completely ready yet though). See you next time and have an awesome New Year!

Announcement of Good Bye 2016
  • Vote: I like it
  • +556
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the large number of problems. It's always more fun to have a choice in what I try to solve (instead of hitting a wall where everything afterwards is unrealistic for me to solve lol).

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

    You are always the first person to comment in cf round blog post. Why buddy

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

      I usually just come online to look for a problem to solve and then see the new post. I don't think I'm always the first though lol.

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

I tried to keep statements shorter than usually

»
7 years ago, # |
  Vote: I like it -61 Vote: I do not like it

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

    The legend says that in each round someone has to repeats the same joke

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

challange: make your rating 2017!

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

Codeforces Say Goodbye Again! Have a good time! I want to change my username. And how to do that ? THX

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

What do you mean by ICPC veteran? Do you have to be a medal winner to be a veteran or are you a veteran even if you have participated in regionals.

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

    veteran = retired

    You are eligible for free/cheaper camp if you still can participate in acm-icpc.

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

      This is not my concern, but what about guys who don't want to participate in ACM or are too young? Or are willing to go, but don't have teammates?

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

        And what about high schoolers? Are they too young

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

      "you still can participate" = "it's possible that you will participate in an official acm-icpc contest somewhen in the future"

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

I have a lot of games did not attend, in The hope that The contest Goodbye2016 would it be possible for me to rise!

»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

8 problems in 150 minutes for a solo contest.

Geez this is going to be tough.

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

    Why? The problems are sorted by difficulty. You don't even have to read all the problems. If I will add three nearly unsolvable problems to the standard CF round, it become harder? Don't think so.

    Even if the problems were not sorted by difficulty, there are many coders who much stronger than you. You can read only problems which are solved by someone.

    And this is combined round, so first problems will be like AB in div.2.

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

      Wouldn't the duration be a bit too short for coming up with ideas? Even for someone (like you) who are able to solve all 8 questions in a competition, I believe that the last three hard questions are going to be challenging enough to worth some time of yours to come up with an approach and 150 minutes seem to be a bit short for top contestants who will sprint through as many questions as possible.

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

        I agree with you but many a times, it is not about trying to come up with ideas about the question but about selecting which problem suits you the best and code it up and get it accepted. Even in ICPC, never has a team (except once) solved all problems or tried to think about all the problems.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it
        1. Your goal is to solve all the problems on the contest? I think you understood it wrong.

        2. Problems are different, you know? If the author (such experienced author as Errichto) thinks that 8 problems for 2,5 hours is good then maybe he is right?

        3. Let's take standard div.1 round and add div.2 AB to the problemset. It takes 5-15 minutes to solve them and it doesn't change hardness of the contest at all.

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

          I think you are right on the second and third point and I've evaluated the difficulty of the round incorrectly by my first impression.

          For the first point I think you are correct too, but I want to be an optimistic dreamer for now, especially when I am not sure how far can I push. =]

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

How many problems in the contest? 8 or 7

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

Mike! +17 rating to everyone please!

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

    If everyone's rating increases by the same amount your relative ranking is still the same.

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

      so, making it optional would be better..

»
7 years ago, # |
  Vote: I like it -69 Vote: I do not like it

Is the contest rated?

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

Goodbye 2016, Hello 2017 and higher rating :)

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

Is there a possibility that instead of getting funding to Barcelona camp we can get funding to Petrozavodsk camp xD? It is significantly cheaper, so that should be easier to give xD.

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

Nice id of contest : 750

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

The contest is combined for both divisions The red contestants:

»
7 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Limak brings me good luck! :D Yeaaah!!

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

Another contest? Another ** ** ***** meme.

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

A brilliant way to end the year :D.

»
7 years ago, # |
  Vote: I like it -55 Vote: I do not like it

условии задач будут на русском или на английском?)

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

Hoping for expert from this, but now I'm probably jinxing it.

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

may I can also say GOODBYE for Div2

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

To be honest, the thing I care about most is how the gifts will be awarded lol. If winners are the top 100 contestants then I would cry for a moment leaning against the wall...

»
7 years ago, # |
  Vote: I like it -76 Vote: I do not like it

I know I will get lots of downvotes but we just can't forget this meme and specially for new year, let's all say ** ** *****? ***, ** ** *****.

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

Finally I will take part in a round again, after a long time :D

»
7 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Is it rated?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it -31 Vote: I do not like it

    Upd: Ok, I understood. Just ignore "** ** *****" comments if you don't want downvotes

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

    say ** ** *****? is like say Lord Voldemort

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

    ** ** *****? question and no downvotes? that's weird!

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

codeforcces VS long queue . hope codeforces win :)

»
7 years ago, # |
  Vote: I like it -44 Vote: I do not like it

interesting ... Tourist vs Petr vs AnasAbbas

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

delay, delay, delay :(

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

I hate nothing more than getting ready and then finding the contest postponed xD

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

    it's not more than when they delayed the contest for 3 more days :(

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

8.7 k registered users!)

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

10 mins delay

thanks to the delay 9k user registered

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

good bye 2016 with a delay! the last delay of this year :P

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

Contest Delayed. Can't even say I'm surprised!

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

Good to see people informing for the delay in the comments. I was right about to start solving but you reminded me, thanks!

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

Interactive Problem Guide is temporarily blocked by administrator?

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

almost 9000 registrations!! It's going to be furious!

»
7 years ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

I am 100% sure that Problem B is judged incorrectly. There is a difference between going towards the south and to continue moving in the direction that he specified from the start of movement if I am at some place on the earth and I specified that I will move INF kilometers to the right then I will be moving in circles around the earth and I will not stop !! It doesn't mean that I will leave the earth xS

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

    Problem B* :v

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

    The earth is round :/, so it should be mentioned that if we can go in circles or not :(.

    The problem should be cancelled.

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

      The contest not the problem.

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

        we can go in circles is demonstrated in sample tc 3.. ?

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

          You can always go West. But you can't go South after hitting the South pole...

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

    I spent lot of time solving B and then as it is written earth is round, so obviously one has to move forward for distances > 20000.

    Should have been properly explained, spent lot of time and got result as hacked.

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

      So, the answer for
      1
      40000 South

      is NO?

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

        Yeah, According to the judge, its a NO. :/

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

          I am so stupid :(

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

            There is a sentence in statement about this: "before any of the instructions or while performing one of them".

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

          Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.

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

        After moving 20000 KM to the south you are at the South Pole, you can't continue walking beyond that because you are at the South Pole and want to move (20000 KM) to the South which is not allowed as described in the statement.

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

          Howerver in test case:

          5 20000 South

          1000 North

          1000000 West

          9000 North

          10000 North

          Ans: Yes

          1000000 west means around the circle but same is not true for north and south, is quite strange for me.

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

            The problem is that in every place of the world, you can go west (except on the poles), but you cannot go Norther than North Pole

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

              What I am saying is 1000000>20000 is allowed for west but not north and south.

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

                I mean, if you are in Australia, you can go east and reach the Americas, and from there, you reach Africa, and then India, and then you repeat. From any point not in the poles, you can always go east/west. However, if you go from Africa, north, you reach Europe, and then the North Pole. But any direction you move from there, you are moving south. The problem is that the división of earth in the north-south direction is not according to the sphere shape, but to the projection shape

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

            The answer is "YES" here, Notice that if you go West or East your distance from the South and North Poles won't change. So moving East or West can simply be ignored.

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

    Something has to be done about B.

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

    Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.

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

    As you said, there is a diffrence between moving into direction that he specified from the start, and going towards the south. And the sentence "If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South." in my opinion makes it 100% clear that Limak goes towards the south, not in one direction.

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

worst problemset ever !

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

    worst comment ever

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

      nice problemset!! but i need to improve a lot

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

    I too was expecting a much better problem set..very much disappointed..

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

      Your arguments are overwhelming.

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

        I think the majority is probably people salty about B. It wasn't unclear you just had to read carefully.

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

    Not the worst problemset ever ! it's just your worst performance ever !!!

»
7 years ago, # |
Rev. 2   Vote: I like it -20 Vote: I do not like it

Tell me result at this test. (task B)

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

B is a shitty problem. sorry.

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

After reading problem setter is Errichto i was expecting a great contest :/

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

    same.

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

    Maybe the fist four problems aren't interesting but the last four are very good,i can even say that they are some of the best problems i have ever seen!!

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

How to solve E?

»
7 years ago, # |
Rev. 4   Vote: I like it +35 Vote: I do not like it

please someone call PrinceOfPersia

I miss his problems' difficulty

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

I need to wait 2 minute at last 30 minutes of contest to look code of a participant, it's awful

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

Contest last 10 seconds, going to submit hack case. WiFi disconnected....

life

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

    I realised my mistake on F 7 mins before end... I needed just one more function(10-15 lines) and there were just 15 secs... Now I wanna cry :((((

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

How to approach D?

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

Pretty hard but enjoyable contest I think. Can anyone explain how to solve D? I was looking for some kind of pattern but couldn't seem to find anything that worked.

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

    Hint: Notice that the farthest visited cell will have distance at most 5*30 = 150 (in x and y coordinate).

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

    I did a sort of BFS with memoization for repeated states. Since you could never shoot a firework more than 150 or so squares from the start, you can generously say that there is a 300 by 300 square area where fireworks can explode. Of course, there are 8 different directions the fireworks could be going, and 30 different possible states it could be at indicating how many splits that firework can do. I know this leaves out a lot of information, but you can see the main idea of how you memoize, you can figure the transitions out yourself.

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

      I started thinking along those lines but convinced myself that there'd be too many states to place into a queue but now that I think about it's not bad. Yeah the main idea is pretty clear, thanks for the help!

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

    Simulate the process, but remove fireworks that are in the same location and going in the same direction. There are not that many possible positions of the fireworks, they can be bounded by a 400x400 square, and each firework only has one of eight possible directions.

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

it's over 9000

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

How to solve D?

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

    Hint : You can build the grid via an alternating sequence of 90 degree and 180 degree rotations and you need to perform this replication of the grid exactly n times.

    Also observe that the final grid size is not that big

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

How to solve C?(ternary search?) I remember there was a blog asking for finding maximum value of x where f(x)=1 and where f(x) varies as 00....000....1111...11...00...00. There someone said it was impossible.

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

    form the inequality equations.

    After forming the inequalities the possible range of initial ratings lies in the range [L,R].

    if R==INF ans = Infinity. if L>R ans = Impossible. else ans = R+(some of all rating changes)

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

    Let x be his initial rating. Write the inequalities after every round, choose the 2 most restricting ones, and from there you can determine the answer.

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

B was a hard problem at the way i understand:

he finishs in north pol with the same direction as first :|

.

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

I think D is such a great problem (Assuming that I pass system tests of course ;D)!

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

1.Petr

2.tourist

3.rng_58

reminds me of good old memories! ^_^

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

IN problem B, if Earth is sphere, how come he fall down from earth ? Errichto I was expecting to end my year happily :(

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

Apparently the solution for this test for B according to judge is NO :
2
25000 South
15000 North
The earth is a sphere. Why is this not allowed?

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

    You cant move south when you are at south pole

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

    If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North.

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

    25000 South means he has to move 25000 miles, constantly in the southern direction, NOT "face South, move straight 25k miles".

    He can't move 25k miles to the South, because there are only 20k until the South pole, where he can't keep moving South.

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

    Clearly in the problem statement, it has been mentioned that whenever you are performing a work, you should not move south of South pole or north of north pole.

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

To be honest this contest was very confusing. I wish some things were worded differently or omitted to make problems clearer.

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

I wasn't able to submit last 20 seconds, the page was loading ... the site is very slow when there're a lot of people. I will be upset if problem will pass systest in practice. : ((

p.s very good problem set : ))

p.p.s HAPPY NEW YEAR.. !!!

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

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

Goodbye 2016. Goodbye rating.

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

Nice Set of problems :) Happy New Year In Advance :) Happy Coding :)

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

What is the answer for this test case for problem C?

20 -2 1 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2 -100 2

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

    I mean I get -1, but I suck so that could be entirely wrong.

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

    -1

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

    -1

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

    I tried to hack Coder_404's solution with this case and I was quite sure his code gave "Impossible" as an answer for this case :( seems I was wrong. I can't check his code right now. I wish he tells me now what his output for this case is :/ if he notices this comment then, I guess.

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

    A negative value. I failed because I didn't realise this:

    "... rating, described with one integer, possibly negative or zero."

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

    -1, But how come the rating be -1? Just kidding :-p

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

The 32 pages of people who were hacked on B probably hints at some unintentional ambiguities in the problem.

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

    I don't think it's the problem's fault in this case... "Go South/East/whatever X miles" is a pretty unambiguous command imo, and it does NOT mean "face South/East/whatever and move forward X miles straight". Also if you understand it that way, the East/West directions should involve a stupid amount of trigonometry (you wouldn't stay on a constant latitude), which makes it even clearer that can't be the author's intention.

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

    Many people tried to hack me on problem B, I hope there is no tricky case i missed.

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

      in this case:

      3 1000 South 2000 North 1000 South

      your solution return yes or no? I tried hack you :[

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

        my output is "NO"

        oh, I see what cause many people tried to hack me, it's because I usually use unsigned data type, I only use int data type only if it's too important, sorry for that..

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

Is it just me, or difficulty increase between D and E is too big? I mean, I expect a lot of people have exactly 4 solved problems.

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

    I was thinking the same thing, but if you look at the difference between A and B, B and C, C and D you'll notice the same pattern.

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

      Hm, maybe, but not for me. For me A and B are basically the same and D is easier than C.

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

        By difficulty I mean the number of solvers.

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

          A to B: 6434/4267 ~ 1.50

          B to C: 4267/3100 ~ 1.38

          C to D: 3100/1296 ~ 2.39

          D to E: 1296/113 > 11

          So I don't understand what do you mean.

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

            If you look at percentage of solvers:
            A: 6434/6610 ~ 97.3%
            B: 4267/6610 ~ 64.6%
            C: 3100/6610 ~ 46.9%
            D: 1296/6610 ~ 19.6%
            E: 113/6610 ~ 1.71%

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

Statements weren't short :|

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

Can someone explain how to solve C? Thanks.

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

    binary search

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

      could you explain more ?!

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

        our left bound is 1899 — 200000 * 100

        our right bound is 1899 + 200000 * 100

        mid = (left + right) / 2

        mid — our start rating

        we check this one in a loop from 1 to n, and if it didn't pass in any time, we change our bound (r = mid if our current rate more than we need (we didn't change div 1 to div 2 ) and left if our curr rate less than we need(we didn't change div 2 to div 1)

        And, finally, we check our bouds(right and left) if it pass write final rate, else write "Impossible".

        Variant "Infinity" can be only if all d[i] = 1;

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

      I was trying with dynamic programming, which doesn't pass the 10th test, sadly.

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

        let's assume initial rating was x

        then at ith step tot rating change =y

        then if div1 x+y>=1900,x>=1900-y if div2 x+y<=1899,x<=1899-y this gives a minimum value for x and a maximum value of x take maximum of all minimums(eg x>=5 ,x>=6,x>=7 all relate to x>=7) take minimum of all maximums if min>max impossible case else maximum is ans

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

          Did exactly this, but failed on Test case 25 :(

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

      I couldn't find some monotone function in this problem, can you explain some?

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

    Let LL be the lower limit of ones rating, and UL is the upper limit.

    Now, let the ith contests input is Ci Di

    if Di is division 1, then you check if his upper limit allow him to participate in the div 1, also change the rating of both LL and UL according to the rating change.

    If Di is division 2, then you check if the LL allow it, and change rating accordingly.

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

    For each contest count difference between rating after it and at the beginning of the year (easy DP). If there is no div2 rating answer is infinity.

    Then find div2 contest with a maximal rating before it. For optimal answer this rating is 1899. When you assume that it is equal to 1899 you can calculate rating at the beginning.

    After that check if every div1 rating is above 1900, if not print impossible.

    And print rating after last contest.

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

Everyone solved C except me.. I participate as an Expert and I solve at most 2, i participate as a Specialist and I solve 3-4, what is wrong with me.

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

Whats wrong with problem B ? Isn't it allowed to move along NS or SN arc on arrival on either of poles ?? It wasn't mentioned.

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

    If I understand what you mean correctly: "If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North."

    i.e. You go North to the North pole, then you must stop and go South because that's the only cardinal direction available at that point.

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

      To my problem TestCase :

      1
      40000 South
      YES
      
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The answer should be NO. After moving 20000 km, you hit the South pole, at which point you are supposed to go further South but that is impossible.

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

          Simple Misunderstandings can ruin our solutions. I thought that when we move in a direction , we continue to move in that direction till we reach our destination. :P

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

            A problem with that (besides the fact that the "while performing one of them" sentence made the author's intention pretty clear imo) would be that moving east or west would be very difficult to handle — think of going south 1 m from the north pole first, then going west 1000 m, keeping your path straight instead of staying on a constant latitude (ie always keeping west). How far from the pole are you now? You would need some painful trigonometry.

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

    You could have clarified.

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

Can someone plz share any ideas to solve problem F?

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

    Find some path from leaf to leaf. For the middle vertex of it, you'll know for sure what depth it's on, and what its parent is. Use that information to find a longer path (you already have a half of it) etc. Some optimizations are needed on the low depths to fit under 16 queries.

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

When you do a good contest: The best problem-set ever When you don't : The worse Come on people!

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

What could be some initial ideas on E?

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

    The first thing I thought about after reading the statement was Mo's algorithm. But then contest ended :( I don't know whether it could be solved using this thing, It's just an idea.

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

    I was going to try using a segment tree to keep track of occurances of 2, 0, 1, 6, 2 followed by 0, 2 followed by 1, and so on until you have a count of all 12 possible combinations. You could easily query how many 2016s were in a range, and then I had a theory that if there was more than 1 2016, the answer would be the min of all vals in my seg tree within the given range. Of course you store a similar tree for 2017, but you only need to check if a single 2017 exists. Shouldn't be to big of a problem on memory, but I figured I didn't have enough time to code it.

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

      To remove 201666622222016 you only need two erase operations.

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

        right, my segtree would store:

        val[("2")] = 6
        val[("0")] = 2
        val[("1")] = 2
        val[("6")] = 5
        val[("20")] = 7
        val[("21")] = 7
        ...
        val[("2016")] = 7
        

        remember it's storing the number of occurences of "stringhere" as a substring within the range. So the min of all those numbers is 2. And so the answer is 2.

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

Errichto, you are the best. I really loved problems from A to E, they are as much complicated as they need to be, the statements are clear and ideas are pretty interesting.

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

Very nice problemset! :)

I wish the duration was longer... The last three problems were really interesting, but I couldn't spend enough time on any of them during the contest. Even top-rated users didn't solve more than 6 (out of 8) problems!

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

Failed to submit solution for F... The connection is not good in china.

Anyway, we enjoyed this contest. Thank you.

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

But we expected nice problemset from Errichto.
:(:(:(

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

    I think the problems were good. Prob B was clear from the context.

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

Ok, just finished writing D. Here is my approach: Assume starting point is (0;0). Build the first firework and add passed points to the set. Now, instead of running 2 recursive functions for left and right subtree, run only one for the left. Add points to the set. After that it is possible to find all points from the right subtree using symmetry around last point of previous firework ending. Does it make any sense? Will it pass system tests? :D

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

    I think you'll get tle...

    My approach: you can consider a grid of size 300x300, because 30*5 = 150 so if you start at center (pos (150,150)) you won't ever leave any border. You can simulate the steps recursively with this cut: if position (x,y) was visited going on direction d on step i, return.

    if(dp[x][y][i][d]) return;

    And this cuts off a lot because you have just 300*300*30*8 possibilities for these... You go from 5*2^30 complexity to just 5*8*2700000.

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

      Well, actually my solution passed with 139 ms time which is pretty solid. Shame I didn't manage to finish writing it during contest.

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

        Just saw your code... amazing job! :D I said I thought it would be TLE bcause I thought something similar but the way I'd code it (a "dumber" way) it would be TLE... nice

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

        How are you exactly calculating the reflection of a point on the line ? I know that there is a standard formula from coordinate geometry but the problem with that is that the resultant coordinates may not be integers.

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

          Let's say firework is going straight up. In some point P it splits into two. Then one child goes left by 45 degree and another right by 45 degree. For each point from left subtree we can find corresponding one from the right like this:
          rightX = P.x + P.x — leftX;
          rightY = leftY.

          The same way coordinates can be calculated if firework is going straight down. If it is going left or right rightX will be equal leftX and rightY = P.y + P.y — leftY.

          If firework is going diagonally then new coordinates:
          rightX = P.x — P.y + leftY;
          rightY = P.x — leftX + P.y.

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

            I used the same idea as yours during the contest but alas made a stupid bug in the reflection part :( Now got AC. Thanks for the help.

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

      Can you tell me why those overlapping state(same depth and direction) won't give any new cells?

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

Flat Earth believers' reaction when reading this problem statement : In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere.

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

What was the idea behind F?

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

    "I didn't participate in contest but I hope this is true.

    After making 11 random guesses, the probability of not to find any leave is 1/2048. After finding a leave, just ask h-2 question to go root."

    I thought it's the solution but when I was writing I realised we can't go to root that simple :P So what is the solution?

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

      Each testcase has 500 inputs, so I don't think a probabilistic method would work. I'm also curious.

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

      of course it's not that simple :D

      I have an idea but I'm not sure if it's correct and it seems it's not the intended one.

      first ask question on any node S, then walk in a random path starting from S you will end up in a leaf, now return to S and walk in a random path too but in other direction, merging the two paths you get a path that starts at leaf and end at a leaf.

      no it's easy to know which node of this path have maximum height (it's middle node in the path), and you also know its exact height (number of nodes in the path)/2, let's call this node V, now go to parent of V and go into a random path until you reach a leaf again you can know which node have maximum height make this node the new V and repeat until you reach a node that is direct child of the root

      the worse case to reach direct child of the root is 1+2+3+4+5 = 15 questions most probably you will ask less

      if you have asked less than 15 questions then you can ask about the direct child of the root and you have two candidates to be root, ask about on of them if its degree is 2 then the node you asked is the root otherwise it's the other node. in this case you you can at most 16 questions.

      but what if you asked exactly 15 questions? then you have to guess the root (1/2) chance of correctness, however if you shuffled to adjacency list of all nodes that you asked then this case will rarely happen. (**UPD**: fruwajacybyk's comment is fixing the this issue in my solution )

      I was going to add shuffle line but time was up before I submit so I don't if this idea will pass

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

      If you have a vertex v with depth d, and a known children u at depth d+1, you can find the parent by doing a walk of length (h-d) from v, not going through u. The walk ends at a leaf if and only if the first edge is not an edge to the parent of v. When close to the root (d <= 2), it is possible to find the root with a search at depth at most d. (It is needed to get under 16 queries). To find the initial vertex, use two disjoints paths to a leaf from a starting node, as the depth of all nodes in the paths are then known.

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

    Search for a long path connecting two leaves, using DFS. When you have a path of length at least 7 then the root is at distance at most 2 from the middle of that path.

    In worst case scenario you need 1 + 2 + 3 + 4=10 questions to get path of length 7. Then there are 7 possibilities for the root. So in 6 questions you can choose among them.

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

    Here's a solution, completely deterministic.

    Start at vertex 1. Choose 2 of its neighbors and ask questions and dfs along those paths until you reach a leaf.

    Now you know which direction is to the root. If you are distance <= 2 to the root, BFS. Else, dfs from this vertex until you find a leaf. Then move back to the top of this path (you can do this because you know the length of the path AND what the depth of the vertex you started at is).

    Now repeat, if you are distance <= 2, BFS. You can check that in all cases this takes at most 16 queries.

    Very ugly to implement though :(

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

Nice quality problems, hard statement for me though. :(

Am I the only one who logged out two times automatically during this contest? Maybe its because of the internet disconnection issue, but is it a feature?

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

The best gift for the new year is a new division!

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

What was the hack in Problem:B ??

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

I think tourist lost first place because comunodi hacked 7 solutions in his room .

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

    Maybe if Petr wouldn't hack, he could solve F. So, we cant be so sure!

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

      Yes , but now tourist needs only one hack to win while peter hacked 6

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

    Is there any efficient way to find which room a person belongs to?

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

      room 67

      you can click on the country flag in the standing page to know the room and view all submission

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

        oh~ I see!

        Thanks a lot!

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

        Well, I found it's actually double click the block with handle.(but don't click on the handle)

        There may be some people without setting their country :D

»
7 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

ААА

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

How to solve E?

»
7 years ago, # |
  Vote: I like it -90 Vote: I do not like it

 system testing__

»
7 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

a

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

For problem F my program reads k in a line, but then the real format turns out to be k and ti in the same line

So sad :(

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

    See UPD2 in the post — if that's the only issue with your solution, you're likely to get the points

»
7 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Problem B was asking for a solution which was contrary to logic . If the earth is round, even in the South Pole one can go West or East. Goodbye 2016, goodbye rating :( .

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

    The West and East directions are actually not defined on the poles. (Think of these directions as a vector field on the sphere, defining it on the poles would break the continuity)

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

      [offtopic] Congratulations on the new color!

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

    Actually no. If you are exactly at the north pole, whatever direction you would go it would be south.

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

    Actually we can keep on arguing about the geography, but the matter of fact is that we should do what's written in problem statement(if problem states you can't go south from south pole, accept it). No one ever batted an eye about the polar bear doing all the funny things it did in today's problem statements, you accepted it didn't you :)

»
7 years ago, # |
Rev. 3   Vote: I like it -47 Vote: I do not like it

DELETED

»
7 years ago, # |
  Vote: I like it -37 Vote: I do not like it

is it rated?

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

can anyone help me with 3rd question of contest http://codeforces.com/contest/750/submission/23442653 in my above code it shows wrong answer on pretest 1 but when i am running it on my pc i am getting right answer

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

    you should use long long or long long int for rx, because 3000000000 in long int is negative

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

      ohh yeah an extra zero.. but how come it is giving right answer on my pc i am running same code same input?

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

Contest not yet open for practice? I'm unable to submit code now.

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

Problem C: my solution failed on test # 32

What I missed?

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

    You didn't check if there was a div1 rating that was lower than any div2 rating.

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

Solution my solution for B FST at this test case: 2 15072 South 15072 North The system says the solution outputs a "NO" and expected "YES". I use the custom test and paste my solution and the input correctly. But it outputs an "YES" after running..... Sad story... FLOAT TRAP?

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

Please tell how can we clarify a question in ongoing contest?

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

Please tell how can we clarify a problem statement in ongoing contest if we have doubt in it?

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

I wonder when I can submit my code...

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

Tourist lost the first place by just 44 points and was way clear of everyone else. Still got a negative rating change. Such harsh is life once you are on the absolute top. :/

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

why practice submission is closed ?? :(

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

when the round will be opened for practice ?

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

When I can change my nickname ?

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

Symmetry

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

Moral from today's problem D :| If you have choice between bfs and dfs, always choose bfs.

»
7 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Saddest round of the year , I always fail the Goodbye Round(3 years straight)

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

Good Bye 2014, 3rd place, 2894 -> 2898 (+4)

Good Bye 2016, 3rd place, 2895 -> 3030 (+135)

The inflation is surprisingly fast.

»
7 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Ignorance

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

Actually, a straight line from West to East on normal global map curves to across the equater on the Earth. For example, half line towards West from England hits around Mexico.

So I though problem B was very difficult geometric problem at first (><)

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

That moment when you lose the first place because of a newbie.

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

    That moment when you lose a CF t-shirt because of 1 minute late

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

      Yeah that's exactly the same :D

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

Errichto, GlebsHP and all who helped, thank you a lot! The problems were great. It was the most popular round in the history of Codeforces.

Errichto, looking forward to see you as a problem writer again! I'm really happy to see Limak on the contest :-)

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

IDK why F is not working for me. My solution: http://codeforces.com/contest/750/submission/23459842 Infinite random tests variant: http://pastebin.com/jE98nJyH At that moments, I always suspicious about author's bug, but for all such situations it was bug on my side.

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

    Found all bugs, when Infinite random starting to find mistakes after adding shuffle of links. It had first link always pointing towards to root, so... simple asking of first link was eventualy leading to root.

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

Can anyone explain problem D?

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

    You can observe that the maximum ends from the starting point, the particle can go is 150 Up,Down,Left,Right. So easily this is a 300*300 grid which our particle than cover. Now, at a given time, our particle can occupy 8 different positions at a cell(The 8 different directions namely). So you can easily simulate this. Think about the memoization states. You'll find there are 300*300*8*30 states at max(row*col*directions*particle_index). Transitions are of O(1) only in between these states as at one states, you can only go to the next two states.

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

Were there anyone who got AC problems C by binary search?

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

I have to say that problem F is ... Wow

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

AC on only B and C, failed systest on A, didn't have time to submit D. Still rating increase????????

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

**LET ME SURPRISE YOU

1.) LOOK AT COLOR AND RATING szawinis

2.) LOOK AT SUBMISSION AND HACKING ATTEMPTS OF P_Nyagolov**

MikeMirzayanov Errichto

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

I'AM SORRY FOR THIS.

Can we change our handle today as its last day of year and it use to happen on codeforces ?

I know this is not right place to ask but , after sending mails and messages to codeforces and Mike i didn't got any reply this was the only option.

P.S post added by Mike we can change handles now :)

Thanks sir, Happy New Year all.

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

    Rumors have said that it is a yearly event.

    (It is also the time of the year where you can't judge a book by its cover)

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

Problem D:my solution failed on test 15 and don't know what did I missed........

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

    u dp on the wrong state. vis1[x][y][1][t[id]] should be vis1[x][y][1][id]

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

    here you go.

    23465573

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

      WOW! Thanks!!!!!!!

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

      another question.... here vis1 should be vis1[505][505][10][31]? (id->n<=30) it should be RE?

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

        That is correct. Thanks for pointing out, I made a mistake. However, accessing an array out of bounds may not give RE, it will just have undefined behaviour. So, I am just lucky the code is still correct.

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

          I found that because I try vis1[x][y][d][id+1] and it was an MLE.... Anyway....it's lucky that I don't need to write a new one....

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

            that's strange. I did one with visited1[600][600][8][30] and I got AC. anyway, u only need [300][300][8][30] to get AC

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

            23466827 I got AC for this submission.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I think something is wrong with the interactor in 750F. In particular, the statement says

In any moment if the program reads h = 0 or k = 0 it should immediately terminate normally (for example, calling exit(0)). It means that the system detected incorrect request/output from your program and printed 0 because if can't process your requests anymore. In this case you'll receive verdict "Wrong Answer"

Yet, compare these two submissions: 23457950 and 23457959 (sorry for the weird indentation idk why). I assert against querying out of bounds and get RTE, while without it I get TLE even with the exit(0), rather than WA.

I spent the last 40 or so minutes trying to debug and find the infinite loop — but it doesn't exist and only in the final couple minutes did I realize the issue was simply a flaw in my algorithm. This is partially why I had 20 incorrect submissions — verdicts weren't making any sense. Am I missing something here?

Anyway, I thought it was overall a nice contest (although I have some qualms with the higher problems) so thanks for giving us all a fun way to end the year!

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

Errichto For problem B Div2 if a person is at the south pole will he not always move towards the north pole regardless of any given direction and therefore while passing through the poles the person would always move towards the other pole?

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

Limak after he read problem B

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

There is another way to solve C using binary search. I can't understand why it works, but it passed all tests.

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

Will there be any news about discounts?

I don't want to go to the Barcelona camp so I am curious if my prize can be given to someone else.

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

    Same story here. I still didn't receive anything about Barcelona, and I'm fine with transferring my discount to anybody else.

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

      Well, I received e-mail from organisers about a week ago.

      let us know if you are not able to attend so we can pass on the discount to the next eligible candidate.

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

Congratulations to Petr for beating tourist at Good Bye 2016 contest.

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

I'm curious about how the top 100 t-shirts are going on...

Anybody received it?