Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Akikaze's blog

By Akikaze, 6 months ago, In English,

"Can you hear me?"

"Vanessa...?"

Hello Codeforces!

We are here to invite you to Codeforces Round #614 (Div. 1) and Codeforces Round #614 (Div. 2), which will take place at Jan/19/2020 16:35 (Moscow time). The round is rated for both divisions.

This is our first round including Div.1 parts, hopefully you'll find the problems interesting. ;)

This round is themed based on the Rayark Inc.'s rhythm game, "Cytus II". You are about to help our characters in various problems, whether inside or outside of the virtual Internet! Also, feel free to listen to the music tracks I've chosen from the game for each problem (and later, editorial!). ;)

Each division will be given 6 problems to solve in 2 hours. The round's problems were prepared by Xuan-Quang xuanquang1999 D. Nguyen, Duy-Bach Akikaze Le and Tuan-Dung low_ To.

Interactive problem(s) might be found in this round. Learn about them here.

We also want to thanks our friends for helping this contest being possible:

Last but not least, I want to give a huge appreciation to MikeMirzayanov for the awesome Codeforces and Polygon platform, which makes this contest possible.

Wish everyone good luck and high rating!

UPD1: Editorial is available here.

UPD2: Many more testers helped us in this round! Huge thanks to Kevin ksun48 Sun, Andrew ecnerwala He, Aydar aid Sayranov, Nikolay KAN Kalinin, Oleg Mustang98 Vallas, Mohammed mohammedehab2002 Ehab, Artem Rox Plotkin, Mingming Nero Zhang, Darko Aleksic, Ilya IlyaCK Porublyov, NatInTheHat and NIWIS!

UPD3: Score distribution:

  • Div. 1: 500-750-1250-1750-2250-2750
  • Div. 2: 500-750-1250-1500-2000-2500

UPD4: True editorial is available here!

UPD5: The contest is over. Thanks for participating, and here are the winners:

  • Div. 1:
  1. Um_nik (first to solve F)
  2. tourist (first to solve A, B, D and E)
  3. Benq
  4. HIR180
  5. jiangly
  6. TLE
  7. AprilGrimoire
  8. Golovanov399
  9. cz_xuyixuan
  10. fateice
  • Div. 2:
  1. DestinyFucker9000 (solved all Div.2 problems!)
  2. about
  3. Isaunoya
  4. espr1t
  5. kkktl01
  6. the_happy_camel
  7. changruinian2020
  8. Agarifighter
  9. Small_Pax
  10. TaeHooooon

Also, as the direct setter of Div1B/Div2D, I sincerely apologized for the weak testsets. I must admit, I underperformed this time, and might cause some of you inconvenience. Hope to see you guys another time with a better contest.

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

»
6 months ago, # |
  Vote: I like it +39 Vote: I do not like it

If you have epilepsy, you can check out my own friendlier version of editorial for this round here.

»
6 months ago, # |
  Vote: I like it +49 Vote: I do not like it

5 months ago???

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

    Yeah, we planned for a contest long ago, but various things have happened in the last 5 months.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for not RickRolling.

»
6 months ago, # |
  Vote: I like it +172 Vote: I do not like it

I want to say that this is one of the best CF contests I remember. Recommend to participate for everyone!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So Interactive problem(s)... I hope we will find the best problems.

»
6 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Cytus XD Interesting!

»
6 months ago, # |
  Vote: I like it +31 Vote: I do not like it

\PAFF/\PAFF/\PAFF/

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Round #614 is back!

»
6 months ago, # |
  Vote: I like it +170 Vote: I do not like it

Petition to refer MikeMirzayanov as Mike "Don't call me Mike MikeMirzayanov Mirzayanov" Mirzayanov.

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +48 Vote: I do not like it

    Problem : Give a string formed by the words "Mike" and "Mirzayanov", is it possible to have only "MikeMirzayanov" by removing characters from the front or back only?

    # Sample 1:

    Input: MikeMirzayanovMike

    Output: YES

    # Sample 2:

    Input: MirzayanovMikeMike

    Output: NO

    # Sample 3:

    Input: MikeMikeMikeMirzayanovMirzayanovMirzayanov

    Output: YES

»
6 months ago, # |
  Vote: I like it -6 Vote: I do not like it

UPD1 is amazing and funny at the same time.

»
6 months ago, # |
  Vote: I like it +49 Vote: I do not like it

NEKO your songs are not as good as PAFF!

[User is now banned.]

»
6 months ago, # |
  Vote: I like it +38 Vote: I do not like it

weeb

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    siromaru is that you? :o

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

    BMS/ToneSphere/Cytus/SUPERBEATXONiC/Chunithm/SDVX/GrooveCoaster/TsumaMia/Synchronica/Taiko/maimai/Rhythmsia/Deemo/Arcaea/Dance Rail/Tapsonic Top/Muse Dash/ONGEKI/PiU/TAKT-RHYTHM/WACCA/SEVEN'S CODE Any other missed bus stop(s)? XD

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

OMG!!! Cytus II!!! I must not miss this round!

»
6 months ago, # |
  Vote: I like it +49 Vote: I do not like it

I think round 616 should be about Arcaea LOL

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

    Maybe we can made Grievous Lady and Fracture Ray be the FINAL Problems :D

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

    Then next comes Cytus I, Deemo, VOEZ, Dynamix, Lanota, Hachi Hachi, Tone Sphere, Zyon

    I wonder if anyone has the guts to make a round themed on Bandori, iDOLM@STER, or LLSIF. That'll be hilarious to see XD

»
6 months ago, # |
  Vote: I like it +137 Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Are you ready y y y y y y y y y y y y y y

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm waiting for it

»
6 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Brain Power was originally a SDVX FLOOR's song...

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

    I'm not sure if I could create a SDVX themed contest anytime soon...
    Anyway, the song is quite popular in many rhythm games so I guess it ain't a poor choice.

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

      I want to see that a contest SDVX-themed! If such contest hold, maybe I join it too! CytusII made the song famous again, so it is good choice!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice and simple editorial. But now I have epilepsy.

»
6 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Welcome to Æsir-FEST.

»
6 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Anime in the announcement is a troubling sign. Please, do not put irrelevant pictures into the statements, or at very least ensure that they are not too big or heavy.

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

    Rest easy friend, there is no irrelevant picture in the problem statements.

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

    Fortunately, anime is not present in this announcement

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

Can anyone explain to me problem D?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Problem D is too HARD.

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

      Problem D seemed really easy to me.. maybe I got it wrong. Just make the observation that $$$a_x >= 2$$$, so your point is always at least twice as far away. Log(1e18) is about 70, so the number of data nodes will not exceed 70. Now if you are given any point p, either you go forward or you go backward from here. jumping any point is pointless, because the distance is always more. So for each point, just check how far back you can go, and how far forward you can go, and update those points.

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

        what do you mean by go forward of backward? can you elaborate please

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

          Think of the datanodes as a line (sort of). Then you can enter at any part of the line and either go forward or backward as far as you can.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did exactly this, still, I was getting WA. 69137106

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

        well I mean D div1 but thanks anyway :D

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Haha, really sorry. You're right :P

»
6 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Who else saw the editorial and thought he already missed the round xD

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting :D hope my rating will increase after this.

»
6 months ago, # |
  Vote: I like it +66 Vote: I do not like it

Really surprised when seeing the poster of 'Cytus II' on the main page of Codeforces.

I believe it will be an amazing contest!

Anyway, I'm curious about whether Deemo will participate in this contest. XD

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    People say he's still at the Black Market...

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    orz Itst Rhythm Game Master!

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

    Unfortunately, I have a piano session with Alice at that time.

»
6 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Shit

why interactive problemm ;(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF... I am so confused for editorial tag before contest.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just think VOEZ by Rayark is better for me XD

»
6 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Weaboo community is awesome!

»
6 months ago, # |
  Vote: I like it +24 Vote: I do not like it

No weeboo shit please :((((((

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Haha, some weird and interesting words around, but nice to google these words in comments and blog. Cool.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial is available: O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I- :D XD

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

I felt that D was easier than C. anyways thank you for the Amazing contest and editorial.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Epic

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The music track for either Div 1F or Div 2F better be Floor Of Lava heh

Also hoping my favorite chaos chart Chrome VOX gets a problem

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting:)

»
6 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Editorial is a song!!

»
6 months ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

why editorial is a youtube video?

PS-Someday i really want CF editorial youtube videos

»
6 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Haha, well played.

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Everything will much better if there are no interactive problems :')

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

    It ain't that bad when you get the hang of the interactive mechanism. ;)

»
6 months ago, # |
  Vote: I like it +30 Vote: I do not like it

After knowing there might be an interactive problem ...

»
6 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Interactive problem!!! That's great.... Hope all of us will enjoy it

»
6 months ago, # |
  Vote: I like it +17 Vote: I do not like it

The interactive problem will be solved with binary search

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

Wow!Cytus II Round!

As a faithful Rhythm Game player(Always osu!,arcaea,cytus II,musedash etc.),

I'm really excited for this precious round.

Be ready for getting a great score!


Liberation Glitch 15 is too hard!!!!!!

I can only get 887k+ & TP 91.2% TAT


NEKO's song isn't better than Ivy & ConneR & Miku!

[User is now banned.]

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

    ConneR txdy!(The NO.1 in the world)

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

do not watch the MV if you have photosensitive epilepsy, seriously (another little cute MV i suggest is this)

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Can anyone tell me if tourist will get the first rank in the contest and MiFaFaOvO will not give the contest then who will be at top after the contest?

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow, that's great! Cytus II is my favourite game and they made a programming contest about it!! I have played the game since it released and now I can Million Master a level 14 song. Hope you guys will do the test as perfect as a TP100%!!!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Now, Is it rated? is banned. I want to ask it! 807A - Is it rated? tourist also approves it!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

as cytus is one of my favorite rhythm game,i'm so glad to see it in codeforce

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA

[User is now banned.]

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +25 Vote: I do not like it

I think you accidentally leaked the editorial.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

when will be themed contest based on sOsU

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

"Can you see me?"

"John Cena...?"

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

The true editorial is here.

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

What's the score for each problem?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

"interactive problem(s)"

and finally — how many interactive problems in div1?

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

Atcoder then codeforces :) what a balanced day

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Ok I'm stuck on C right now.

The song is nice though. Like that.

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Cytus is a great game

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

A very special contest for me, it's my 100th contest in Codeforces, and yes today's contest was really awesome.

»
6 months ago, # |
Rev. 3   Vote: I like it -15 Vote: I do not like it

Any one can explain D?

»
6 months ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

One can jump from ~1000 rank right into top 12 by solving E (Div2)

»
6 months ago, # |
  Vote: I like it +34 Vote: I do not like it

I made a meme for div1D

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

    Thanks, will include this in editorial after system test.

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

how to solve Div2 E?

  • »
    »
    6 months ago, # ^ |
    Rev. 9   Vote: I like it +8 Vote: I do not like it

    Start by putting 0 on one edge, and notice that it is pointless tu put 1 on an edge that is not consecutive to it, then you put 2 on an edge consecutive to 1 or 0, and so on, in short you form a path. Thus you can do a quadratic dp with state u,v where u and v are the ends of an already built path where you need to add the next number, adding it let's say to an edge that leads fro u to pu, will increase the solution by size(u->pu)*size(u->v) where size(a->b) is the size of all the tree but the subtree from b that contains the path to a so you try for each edge next to u and for each edge next to v (except the ones you already took) to add the edge, and see which gives you the best score

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest!!!. I feel C was a lil bit easy.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for E?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice contest after a long time.

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve C division 1?

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this correct for Div2 E — Find diameter, then every number from [0,x] should appear consecutive on diameter edges.

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

    No. It isn't correct even for a simple path with more than 2 edges.

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

    Not diameter, but DP for each path. We can extend a path with length $$$x$$$ (containing $$$[0,x-1]$$$) to length $$$x+1$$$ by adding $$$x$$$ to one edge adjacent to it.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone! I hope everybody is doing great! Does anybody have any idea on how to solve Problem C of Div.2? I was constantly getting tle on test #7. Thanks <3

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve Div.2 C? I am too stupid to solve such a problem.

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

    you just need to worry when the column 1 connects to column 2. so, every step you have to see if it connects or disconnects, then add or discount the number of connections. If the number of connections is 0, the answer is yes

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I do not understand. What do you mean by "connect"?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for example if the tiles (1, 2) and (2, 3) are with lava, then the column 1 is connected with column 2.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maintain a counter of all blocked_passages in your grid.

    Now, if the counter is 0. Then only a path is possible. Else, it is not possible. As there always be a way that is blocked so you can't reach your destination.

    Now for each query, there are only a few cases possible that passage is blocked.

    Case 1: Left Cross( i.e if you are in upper cell currently and in the previous column, down cell is blocked.You increase your counter).

    Case 2: Same column

    Case 3: Right Cross.

    Now you can similarly decrease counter if you are turning off the lava cell.

    AC submission

    Hope you understood!

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I really liked today's Div1C/Div2E. Here's a hint:

Observe that

$$$S = \sum_{i=1}^{n-1}{\text{number of paths } (u, v) \text{ having all edges from }0\text{ to }i-1}$$$

Edit: Since, this was obvious for lot of people, hint 2:

Let dp[u][v] denote the maximum answer given edges from $0$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$. How can you transition?

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like it

    Can you solve this with 2D DP?

    DP[a][b] being the current mex sum from node a to node b, DP[a][b] = max(DP[c][b] + sz[a] * sz[b], DP[a][c] + sz[a] * sz[b]) where c is the node in the tree that brings a & b closer to one another?

    EDIT: I was like 10 characters away from this solution :( I calculated sz[a] and sz[b] incorrectly because I'm stupid.

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

      Yeah I did with 2D DP. I let dp[u][v] denote the maximum answer given edges from $$$0$$$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$.

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

    I observed this one but didn't find any way to give weights that'll maximize the total sum. can you give some more hint?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah let dp[u][v] denote the maximum answer given edges from $$$0$$$ to $$$x-1$$$ lie on the path between $$$u$$$ and $$$v$$$ where $$$x$$$ is the length of path $$$(u, v)$$$.

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

    At least for me (69143650), that part was obvious, but writing the DP to calculate the optimal answer was hard. DP on pairs (edge, direction) is very tricky and unusual.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm. I had done this DP on (edge, direction) thing already once so it struck me quickly. Anyway, neat trick.

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

      Why (edge, direction)? Why not paths (u, v)?

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, just paths as states would have been better here. The transitions would stay the same, but it would have at least prevented issues with memory usage.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why the greedy doesn't work?

    I check each leaf-to-leaf path. let $$$a[..]$$$ be array of size of sub-tree of that path.

    pick max_i $$$a[i] * (n-a[i])$$$, then expand left/right by greedy compare which $$$a[l]*(n-a[r])$$$ is greater. sum it up.

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

      The question is: Why should the greedy work?

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

        Well, I didn't mean greedy should work, I just wonder what's wrong with this method, since I need someone give me a counterexample, that would be helpful.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      well suppose you have to make such a decision:

      you have 2 edges you are deciding between:

      • one having a simple path with 4 nodes (A, B, C, D) connected one next to each other

      • the other having 5 nodes, parent node E, then 4 children (F, G, H, I) all directly connecter to E

      so here you are deciding whether to take the upper (A, B, C, D) or the lower (E, F, G, H, I) branch

      if you take the lower branch you would gain 5 * (size Left) now, but in the next run you would only gain 1* size Left

      while if you take the upper branch you will gain 4 * size Left now, but 3 * size left in the second run which is better

      so just looking at the current size without looking at how it is branching is not enough

»
6 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Why set the data range exceed long long in C++ for div2:D ? I waste 1h for this problem and finally get Pretestpast by rewrting my code in Python.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    everything in this problem is <= 10^16, long long goes up to ~10^19, you probabilly had some other bug

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but I pass the system test... that is the only bug of my code in c++.And seems like week pretest for this problem? My rank rise by 500 after system test.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a stupid question. Does *lower_bound(vector.begin(), vector.end(), x) == x ALWAYS hold if and only if vector contains element x? (vector is sorted) I always thought, that the answer to this question is "yes, of course", but for some kind of reason it isn't so. In task A I had this:


if(*lower_bound(eil.begin(), eil.end(), i) == i) continue;

And it didn't work, but when I changed it to


for(auto x : eil) if(x == i) is = true; if(is) continue;

it got AC. I know it's problem A and stuff, but still, I am really interested why this doesn't work.

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

    lower_bound(eil.begin(), eil.end(), i) might return eil.end(), and it is undefined behaviour to dereference the end iterator.

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

    if vector doesn't contain element x, lower_bound return vector.end(). if u try to get the element of vector.end(), u got rubbish or RE(

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

[Idea for Div.2 F]

I was thinking of creating a compressed trie. We'll insert numbers in their compressed form e.g. 24 = {(2, 3), (3, 1)}, 720 = {(2, 4), (3, 2), (5, 1)}.

Now the problem is reduced to given a weighted tree find the node such that the distance from that node to all the leaves is minimum.

Am I right in my approach?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

you cant make pset look cool just by shoving some lame ass irrelevant story. sorry but please dont do this. this is painful and irritating af

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

69145588 WHAT HAPPEND TO A (div 2) It requires special solutions?

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

    I recommend using set<int> or map<int, int> instead of vector<int>, since all you really need to know is whether a given floor is closed or not. Beyond that your solution seems to be too slow. If I'm not mistaken, the loop for (int j = 1; j < store[0]; ++j) is $$$\mathcal{O}(n)$$$, which is too slow.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      You probably want unordered_set actually. It took me a while to figure out python set is not c++ set...

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

        Well, $$$\log(k)$$$ isn't the end of the world.

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

        unordered_set actually isn't very good to use when someone can tailor an input to make your hash set go to its worst case of $$$O(n)$$$. Unless your hash function is unhackable, you're safer with a regular BST set.

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

          true, worst case vs avg case — I did not even consider hacking.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

TL could have been better in D. Multiple possible solns in D close to TL. N*no_of_primes, sum_of_log_i(5000)*no_of_primes :(

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I managed to waste my time on stupid bugs, but generating a compressed tree seems pretty fast even when I'm map-ing exponent sequences to ints (extra slow log factor), probably because I'm removing trailing zeros, which are very common.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was actually calculating costs for all possible suffixes and taking the minimum of those which happened to be very close to 2s. My AC solution runs in 1.902s xD.

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

How to solve div2 D ?

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    The number of points can be atmost 55. So, compute the points. Points will be sorted. Then go to i th point (for all i) from source point, and check how many points you will be able to get if you go to points on the left, and on the right. Take maximum between them. Just do this for all i.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain the part after sorted (and justification for that) ?

»
6 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Div.2D/Div.1B is a bad problem.

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

    Problem A and D were both pseudo-brute force that relied on the solution set being extremely limited (2000 points to check in A, and at most 55 in D). C was also a straightforward problem with emphasis on implementation, as in A and D.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test 13 of 1D... I've been stresstesting my solution for over 10 minutes and no countercase was found.

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

What should be the answer for the following case in DIV2E/DIV1C?

4
1 2
2 3
3 4

All the accepted solution prints 7, but if we allot 0, 1, 0 to the edges respectively, S seems to come out to be 8. Am I making some mistake?

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

lol I'm stupid, vector<vector<bool>> cell(n, {false, false}); is NOT how you init a 2D vector lmao

also for 2B I even wrote up a DP solution :(

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

    Don't say that, at least I'm more stupid than you.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what's worse is that my init, besides being undefined, also has wrong indexing order

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it +41 Vote: I do not like it

FSTForces.

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Anyway Div2 B would be more interesting as a DP problem instead of being able to guess the solution from the examples...

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

1e17*100 will overflow long long->WA 127……

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

     I have WA on 132 :(

    EDIT : Its indeed 1e17 * 100 overflow thing. changed limits to 2e16 and it passes :/

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why Div2D/Div1B has so many system failed? :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fastest editorial

»
6 months ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

The problem setter of Div 2D should not make such constraints. It was difficult for people using c++ to avoid overflows. It was pretty disappointing. P.S:-The problems were really good and I hope we will see more contests from Akikaze

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

    Here's a trick to avoid overflow. Say you set your limit to $$$10^{17}$$$, so when either coordinate gets that high, you stop. This means that you'll stop when $$$coord * a_x > 10^{17}$$$, ignoring $$$a_y$$$ because it's the same. If you instead change this condition to $$$coord > 10^{17} / a_x$$$, then overflow will not be an issue, and the inaccuracy of integer division will not be a problem if your limit is high enough. This is also nice because you don't have to worry at all about your limit being too high :)

    I'm not disagreeing with you, $$$10^{16}$$$ was probably unnecessary, but this trick is still good to know in case the bounds are $$$10^{18}$$$ or something annoying in the future.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This works for me and is simple enough that I can remember next time, thanks!

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

      You can also think less about how high the limit should be if you cast everything to long double and check overflow with it.

      bool overflow(long double a, long double b){
          return a * b > 1e18 + 10;
      }
      
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What will happen when a = 1e15 and b = 1e4?

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          $$$a * b$$$ would evaluate to $$$1e19$$$ and the function will return $$$true$$$. What are you thinking about?

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

      Actually, the constraint was set in a way that the trick to check overflow above is not necessary (by using the stop condition $$$\max(0, x_i - x_s) + \max(0, y_i - y_s) > t$$$).

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

        Fair enough, I suppose my complaint is solely about doing dumb stuff under contest pressure. That shouldn't be your responsibility as setters.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any hints for C ?

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

I just trade my sleep with this round, and got sysfail on div2D, and I'm about to wake up 4 hours later to go to work.

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What a pity! In my solution to Div2 D, I used <= to see if the time was over T, instead of using <

By the way, I used long long in my solution too, but I accept.......

Here is my AC code:https://codeforces.com/contest/1293/submission/69149165

»
6 months ago, # |
  Vote: I like it +14 Vote: I do not like it

weak pretests for D :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am unable to figure out a testcase for Div2C that makes my solution incorrect, and I am getting WA on pretest 5. Can someone please look at my solution here? https://codeforces.com/contest/1293/submission/69151171

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

    Test this: 5 5 1 2 (yes) 1 4 (yes) 2 3 (no) 1 3 (no) 2 3 (yes)

    This should most likely be the issue.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When would this contest be rated?

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

why in Div. 1 D $$$k_i = 0$$$ was allowed ? isn't it very strange when we have $$$k_i = 1$$$ allowed ?

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I can't understand why weaks pretest ,is a mistake of problemsetters or a problem. Thanx for such a nice contest!

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

    I totally overlooked such possible fails from the beginning (thinking that nobody could go that far other than trolling), and it was my fault, I admit.
    Thanks for the kind words.

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

      I dont think so you that you should take it on yourself. I personally like the fact that people had to think about overflows, calculate them, and they missed (and they will of course rue on that). In real life problems as well, I have encountered such overflow issues. Its a learning process, and hopefully I wont overlook such subtle overflows. I also made that overflow mistake setting my check limits to 1e17 :/

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

        Thanks.

        I'll be frank, the burden I took on myself is something sort of "capability". If you tried my previous rounds (#538 and #554), you would see that I've tried to limit the possibilities of hackfests and FSTs to minimum (even when using problems with controversial stuff, like that random interactive in #538). So this sort of things, no matter how I could excuse myself of blaming participants' mistakes, I still had my parts in it.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In some submission, i've found this code line: int main(int argc, const char * argv[]) What effect does it take? (sr my bad english)

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

TaeHooooon is 9th place WOW

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

Oh, I hacked my solution(https://codeforces.com/contest/1292/submission/69143854) in Div1D with this testcase: https://codeforces.com/contest/1292/hacks/610526/test

UPD: I hacked 10 solutions with this testcase. Why were tests so weak?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dp problem after all!

thanks for the nice contest