AkiLotus's blog

Codeforces Round #614
By AkiLotus, 5 years 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 AkiLotus 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:

  • Our dear Codeforces coordinator Dmitry cdkrot Sayutin for reviewing our problems, and roasting a whole bunch of them as well. :D
  • Grigory vintage_Vlad_Makeev Reznikov, Quang-Minh MofK D. Nguyen, Yufan ouuan You and Sulfox for helping us in preparing and adjusting difficulties of a few problems.
  • Anton antontrygubO_o Trygub, Duc-Trung Kuroni D. Dang and Duy-Thuc leduythuc Le for being our testers.

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. Nephren
  6. the_happy_camel
  7. changruinian2020
  8. Agarifighter
  9. Small_Pax
  10. TaeHo0o00o0N

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

Comments Comments (196)
| Write comment?
»
5 years 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.

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

5 months ago???

→ Reply
  • »
    »
    5 years 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.

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

Thanks for not RickRolling.

→ Reply
»
5 years 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!

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

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

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

Cytus XD Interesting!

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

\PAFF/\PAFF/\PAFF/

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

Round #614 is back!

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

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

UPD1 is amazing and funny at the same time.

→ Reply
»
5 years 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.]

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

weeb

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

    siromaru is that you? :o

    → Reply
  • »
    »
    5 years 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

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

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

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

I think round 616 should be about Arcaea LOL

→ Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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

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

→ Reply
»
5 years 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

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

I'm waiting for it

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

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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!

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

Nice and simple editorial. But now I have epilepsy.

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

Welcome to Æsir-FEST.

→ Reply
»
5 years 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.

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

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

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

    Fortunately, anime is not present in this announcement

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

Can anyone explain to me problem D?

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

    Problem D is too HARD.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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.

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

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

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

        well I mean D div1 but thanks anyway :D

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

          Haha, really sorry. You're right :P

          → Reply
»
5 years 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

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

interesting :D hope my rating will increase after this.

→ Reply
»
5 years 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

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

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

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

    orz Itst Rhythm Game Master!

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

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

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

Shit

why interactive problemm ;(

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

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

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

Just think VOEZ by Rayark is better for me XD

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

No weeboo shit please :((((((

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
»
5 years 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

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

Editorial is a song!!

→ Reply
»
5 years 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

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

.

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

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

→ Reply
  • »
    »
    5 years 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. ;)

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

After knowing there might be an interactive problem ...

→ Reply
»
5 years 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

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

The interactive problem will be solved with binary search

→ Reply
»
5 years 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.]

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

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

    → Reply
»
5 years 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)

→ Reply
»
5 years 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 jqdai0815 will not give the contest then who will be at top after the contest?

→ Reply
»
5 years 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%!!!

→ Reply
»
5 years 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!

→ Reply
»
5 years 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.]

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

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

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

I think you accidentally leaked the editorial.

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

when will be themed contest based on sOsU

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

"Can you see me?"

"John Cena...?"

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

The true editorial is here.

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

What's the score for each problem?

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

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

→ Reply
»
5 years 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?

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

Atcoder then codeforces :) what a balanced day

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

Cytus is a great game

→ Reply
»
5 years 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.

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

Any one can explain D?

→ Reply
»
5 years 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)

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

I made a meme for div1D

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

    Thanks, will include this in editorial after system test.

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

how to solve Div2 E?

→ Reply
  • »
    »
    5 years 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

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

Any hints for E?

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

Very nice contest after a long time.

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

How to solve C division 1?

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

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

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

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years 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!

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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)$$$.

      → Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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)$$$.

      → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

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

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

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years 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.

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

      The question is: Why should the greedy work?

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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(

    → Reply
»
5 years 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?

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

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

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

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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...

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

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

        → Reply
      • »
        »
        »
        »
        5 years 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.

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

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

          → Reply
»
5 years 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 :(

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

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

How to solve div2 D ?

→ Reply
  • »
    »
    5 years 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.

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

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
»
5 years 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?

→ Reply
»
5 years 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 :(

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

https://codeforces.net/contest/1293/submission/69142492 what wrong in c .

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

    I assume block counts connected components. If so, it's strange that it could increment/decrement by $$$3$$$ each query. Maybe I'm not seeing your thought process, sorry.

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

FSTForces.

→ Reply
»
5 years 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...

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

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

→ Reply
  • »
    »
    5 years 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 :/

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

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

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

Fastest editorial

→ Reply
»
5 years 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 AkiLotus

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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!

      → Reply
    • »
      »
      »
      5 years 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;
}
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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?

          → Reply
    • »
      »
      »
      5 years 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$$$).

      → Reply
      • »
        »
        »
        »
        5 years 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.

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

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

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

any hints for C ?

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.net/contest/1293/submission/69149165

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

weak pretests for D :(

→ Reply
»
5 years 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.net/contest/1293/submission/69151171

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

When would this contest be rated?

→ Reply
»
5 years 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 ?

→ Reply
»
5 years 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!

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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 :/

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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)

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

TaeHo0o00o0N is 9th place WOW

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

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

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

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

Dp problem after all!

thanks for the nice contest

→ Reply