dalex's blog

Samara Farewell Contest 2020 (XXI Open Cup, Stage 8, GP of Samara)
By dalex, 4 years ago, In English

Hello everyone,

As you may know, ICPC movement has officially died in my university. It was a streak of 14 NEERCs in a row, with 3 WFs, but now it's over and it doesn't seem to recover in near future. Let's celebrate this event with Samara Farewell Contest, and don't forget to press F!

It is a collection of not-so-easy (still easy for nutellas) problems authored by dalex and craus throughout our ICPC career and then problemsetting career. Find the enter links on Opencup site on Sunday, January 3, 2021, 11:00 MSK.

We can discuss the problems here after the contest ends. I will also upload it to Codeforces Gyms, but a bit later.

Links:

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

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

I spent so much time on K and never realised you don't have to kill heroes in one go QAQ

Is the problem even solvable if that is required?

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

    I remember long time ago we concluded that it isn't, but maybe it's because we are orange.

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

I have solved B with some art of annealing: randomly choose one quest from each pair and perform 100 iterations by trying to flip quests while traversing in random order.

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

    :(

    Maybe you have a countertest? I'll add it.

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

      I don‘t — actually 100 was approximation for log improvements and random order for achieving log on average :)

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

By the way, could you share the grader for N?

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

    madskillz

    It is hardcoded for this problem, including the top-right corner starting position.

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

      Thanks, I now got AC :)

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

K's statement was quite confusing for me. I understood "Note that if Bloodseeker had 1 hit-point before he last-hits the i-th enemy, he doesn't die." as "in each second, first he hits an enemy and then he takes damage", but apparently that was supposed to mean that first he takes damage, then he hits an enemy, then the 0 hp condition is checked.

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

    Sorry for that. I didn't expect this statement to be understood this way. In the game losing HP is a continuous process, and regeneration is instant. I will rewrite this part before uploading to CF Gyms.

    You could ask a clarification request. I was ready to answer but there were no clars.

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

      Well, there was no way of requesting clarifications... ("Questions" tab is missing from this contest's Yandex interface.)

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

        I didn't know it's configured like this. Is it always the case on Opencups or was it a misconfiguration?

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

          Hmm, I just checked it and it seems that GP of Siberia was the last contest in this season which was configured to let us ask questions. snarknews, do you want to look into this?

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

What's the case 10 for F?

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

F. Thanks for the contest, I really enjoyed most of the problems! :)

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

I am curious about how others implement problem B.

For me I used binary search and got in trouble with the precision. I finally passed by recalulating the answer using the input data but rather not using the direct answer from the binary search.

Is there anyone willing to share the implementation?

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

    (btw, ld is long double in my code)

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

      Thank you for your code! I just found that I have set wrong lowerbound for the binary search. (I set it 1 instead of 0.) The interesting thing is that my code, which was accepted, is actually wrong (the precision is actually enough) and I don't know why it passed all the tests, lol.

      Thank you again!

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

Can anyone help me with promlem M?

I'm constantly having ML 21. I have only 3 arrays of int 0.5M each, and 1 array of bool with 0.5M elements. I do not have recursion :(

I can't understand from were I'm getting this ML :(
https://ideone.com/0veMsS

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

Can someone help me with the problem L? I can't understand how to construct the answer thorugh the parents. Can someone share the solution code or explain this to me?

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

I stucked at understanding problem B: If the NPC was chosen randomly, how come can we deterministically know the speed of earning gold? Is it that we need to find something like expected value?

To be more specific, there are infinitely possibility of infinite sequence of chosen npcs, but we need to calculate a single value out of all of that. Each possibility might have different speed. How do we make all that into a single value?

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

About Problem N:

  1. First, this problem requires some chess knowledges, and I felt that this is not trivial. In particular, avoiding stalemates was harsh, and without chess basics I wouldn't be able to handle those situations. Just an opinion, but I think this problem is not appropriate for competitive programming contest...

  2. If you decided to include this problem in a contest anyways(yeah, it's just an Open Cup!), you had to make your statements clear so that all required information about chess is provided in statement. There was no information about "stalemate" and "move that would place your own king in check is an invalid move" in the statement.

Chess from SEERC 2013 would be a good reference. This ICPC regional problem provides all (required) information about Chess rules, including basic rules, possible moves for each pieces, invalid move, and stalemate.

→ Reply