zscoder's blog

Valentine's Day Contest 2020
By zscoder, history, 5 years ago, In English

Hello everyone!

Will you be single and bored during Valentine's Day? Never fear, as zscoder is here to cure your boredom.

I would like to invite you to Valentine's Day Contest 2020, which will take place on Friday, February 14, 2020 at 12:30 GMT. The contest is unofficial and unrated, but the quality of most (if not all) of the problems are comparable to problems from a Codeforces round. I am the author of all problems.

The contest format will be IOI format, which means that each problem is worth $$$100$$$ points, and there are subtasks for each problem. There will be no time penalty. The problems are not sorted in increasing order of difficulty. Unlike IOI, you are allowed to use any templates or notes you have.

There are 7 problems to be solved in 3.5 hours. There is an interactive problem, so feel free to learn about them here.

There will be a special shoutout to the first person to AC for each problem (and also the first person to get all 7 ACs >_<).

The difficulty of the contest is aimed at higher-rated Div. 2 (Expert) to mid-red (low International Grandmaster) level participants but everyone is welcome to join the contest. Of course, if you are not single and are still free to join the contest, you are welcome to join as well. XD

Thanks to the testers Kuroni, tmwilliamlin168, duckmoon99, gamegame, ToxicPie9, dorijanlendvaj, kostia244 and alimq for testing the problems and MikeMirzayanov for the wonderful Codeforces and Polygon systems that made this contest possible.

The contest will be held (tentatively) within a Codeforces group and the link will be posted later.

UPD: The contest will be held as a training contest on Gym. (which will appear later) The contest is now available on Gym. Registration opens $$$6$$$ hours before contest starts.

If you are a coach in Gym, remember to disable coach mode before joining the contest. ^_^

I will be on the AC Discord server to discuss the contest after it ends.

Hope to see you in the contest!

UPD 2: Contest is over! Thanks to everyone who participated and made this Valentine's Day less lonely for me. Congratulations to the top 10:

Rank 1: Radewoosh (with 577 points)

Rank 2: jiangly and 244mhq (tied with 500 points)

Rank 4: NoLongerRed (with 426 points)

Rank 5: sigma425 (with 409 points)

Rank 6: noneTP (with 351 points)

Rank 7: wygzgyw (with 345 points)

Rank 8: chocorusk (with 340 points)

Rank 9: BigBag (with 334 points)

Rank 10: waynetuinfor (with 326 points)

Also, here is a shoutout to all the "first to AC"s:

Problem A: sigma425 at 00:16

Problem B: Unsolved during contest time :(

Problem C: 244mhq at 00:25

Problem D: TLE at 00:44

Problem E: TLE at 02:38 (and only AC for E during contest!)

Problem F: Moniphant at 00:12

Problem G: shirakami.rin at 00:24

UPD 3: The editorial is here!

Announcement of Valentines Day Contest 2020
  • Vote: I like it
  • +564
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
5 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Can i participate in contest in team with my girlfriend?

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

    リア充爆発しろ!

    It is an individual contest but that doesn't restrict you two from doing it together (not as a team though).

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

    Show off (๑˃̵ᴗ˂̵)ﻭ

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

    Your downvotes are count of those single people who are desperate and jealous. Hypocrisy is when you showcase your rating color its an "achievement" but when you tell you have a gf, you get downvoted for showing off.

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

      Read the first sentence of the announcement and you will see why he got downvoted.

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

      You can talk about your gf somewhere else, but commenting here is like an LGM saying "this contest is so easy" under a div3 round. This is not "achievement", I believe anyone who does this will get downvoted.

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

      I have known about gf(generate function). :>

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

    gr8 b8 m8

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

    NO U CAN'T , IT'S CHEATING

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

    Duuh...

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

Nice <3

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

This should be for teams of 2 :>

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

    "Will you be single and bored during Valentine's Day"

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

    Or you will be paired with a person with a similar rating. Or maybe a similar style of coding. ( ͡° ͜ʖ ͡°)

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

Finally a worthy Valentine partner thanks codeforces ;)

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

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

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

..

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

.

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

Will I be able to get the "one" in this contest?

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

ysav _sparky

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

Wish this contest to last longer. So that everyone can have some time to solve the problems. As it is not rated.Why not make it 24hours in Valentine's Day?

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

    You can always upsolve the problems after the contest.

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

      But don't you think 3.5hours for 7 problems is too short?

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

        On the other hand not everyone has such a long window of free time to join the contest. I think 3.5 hours is sort of a balance between having time to attempt most or all of the problems and also not being extremely long.

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

          I find that I can see the problems now and submit code(since I opened the coach mode). So the length of the contest do not affect me :)

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

Can me and my reflection in the mirror do this contest together?

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

Red coders of CF right now

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

    Coincidentally the main characters in the round are all from anime/light novels

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

"if you are not single"

Does it mean group participants? LOL

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

Hey, what's the contest link?

There are only a couple of hours left.

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

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

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

Why is this contest unofficial ? I mean why dont we held a contest for it ? It will be nice ^^

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

    It is unofficial only because it isn't an official Codeforces round. However, you are welcome to treat this as any other official round :)

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

      NNNNooooooooooooooooooo !!! I forgot the contest :<<< The notification doesnt show up for favorited contests ;-; Cry in tears

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

      Sorry and thanks for the contest <3

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

Contest starts in 5 minutes!

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

Nice problems.It would have been great if it was taken officially.

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

Statements are queit interesting! Some names in the statements are characters from some sweet love stories!

Problem A: School Days

Problem B: 徒然チルドレン (Tsuredure Children)

Problem D: 月がきれい (as the moon, so beautiful)

Problem F: 中二病でも恋がしたい! (Love, Chunibyo & Other Delusions)

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

Hate A, hate biconnected, just test your knowledge.

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

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

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

Nice problems! I'd be glad if someone can describe their solutions for problems C and D.

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

    For C my solution is follows. First denote d +1 points with sum of their coordinates equal to d(lying on the border of the romb) and lying in the first quarter and start point as special. Then do $$$dp[i][j]$$$ the number of correct paths(not visiting bad points maybe except initial one) of length $$$j$$$ starting at $$$i$$$-th special point. To calculate it consider substracting invalid paths from all paths. To calculate invalid paths try one of the bad point as last bad point in the path and every length of path to it and make corresponding transition. Note that if this last point is strictly inside the romb then it can be the last bad point only in case it's last in the path. Otherwise this point is in border and due to symmetricity we should know values of $$$dp$$$ only in border points in first quater. Maybe explanation is not good ask if there are questions.

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

      And you should be able to calculate also the number if paths from one point to other of fixed length. I only know how to do it in $$$O(length of the path)$$$. Only difference between corresponding coordinates matters and you can hash these values for the poinrs inside the romb.

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

Why is it a valentine's contest but FA are the easiest problems

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

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

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

Can someone help me in my submission for problem A. I am getting MLE on subtask 1 and 3. I don't understand why. Code is here

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

    your dfs_lca() is going for ever so it's causing a stack overflow.
    the given graph is not a tree.

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

      I have actually converted the graph into block cut tree. And then I am applying dfs_lca(). I don't know if I am doing something stupid in the process ;)

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

This day needs some lovely problems! lol :D

→ Reply