*"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**:

- Um_nik (first to solve F)
- tourist (first to solve A, B, D and E)
- Benq
- HIR180
- jiangly
- TLE
- AprilGrimoire
- Golovanov399
- cz_xuyixuan
- fateice

**Div. 2**:

- DestinyFucker9000 (solved all Div.2 problems!)
- about
- Isaunoya
- espr1t
- Nephren
- the_happy_camel
- changruinian2020
- Agarifighter
- Small_Pax
- 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.

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

oh, it's actually my favorite song =)) still can't believe that there is an artist (in Viet Nam) dare to make it.

actually this is friendlier :) https://www.youtube.com/watch?v=qPpvKcNCMjY

5 months ago???

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

Thanks for not RickRolling.

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

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

Cytus XD Interesting!

\PAFF/\PAFF/\PAFF/

Round #614 is back!

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

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

UPD1 is amazing and funny at the same time.

NEKO your songs are not as good as PAFF!

[User is now banned.]:D

weeb

siromaru is that you? :o

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

osu!

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

I think round 616 should be about Arcaea LOL

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

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

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

I'm waiting for it

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

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.

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!

Nice and simple editorial. But now I have epilepsy.

Welcome to Æsir-FEST.

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.

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

Fortunately, anime is not present in this announcement

Can anyone explain to me problem D?

SpoilerEditorial is available .

Problem D is too HARD.

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.

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

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.

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

You may be overflowing.

well I mean D div1 but thanks anyway :D

Haha, really sorry. You're right :P

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

interesting :D hope my rating will increase after this.

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

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

orz Itst Rhythm Game Master!

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

Shit

why interactive problemm ;(

Just think VOEZ by Rayark is better for me XD

No weeboo shit please :((((((

Weeb is love

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

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

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

Editorial is a song!!

why editorial is a youtube video?

PS-Someday i really want CF editorial youtube videos

Then Chinese will kill you.

.

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

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

After knowing there might be an interactive problem ...Interactive problem!!! That's great.... Hope all of us will enjoy it

The interactive problem will be solved with binary search

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.]ConneR txdy!(The NO.1 in the world)

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

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

How does one

the contest?giveWow, 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%!!!

Now, Is it rated? is banned. I want to ask it! 807A - Is it rated? tourist also approves 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.]Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).I think you accidentally leaked the editorial.

when will be themed contest based on sOsU

"Can you see me?"

"John Cena...?"

The true editorial is here.

What's the score for each problem?

will be out 3 seconds before the contest as usual :D

But now we can see :D.

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

and finally — how many interactive problems in div1?

Atcoder then codeforces :) what a balanced day

Atcoder then Codeforces :) what a fulfiled Sunday

Then codechef cookoff :D

This made my day unbalanced.

Cytus is a great game

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

Any one can explain D?

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

I made a meme for div1D

Thanks, will include this in editorial after system test.

how to solve Div2 E?

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

Any hints for E?

Very nice contest after a long time.

How to solve C division 1?

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

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

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.

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

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

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

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

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!

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

Observe that

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?

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.

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)$$$.

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?

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)$$$.

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.

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

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

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.

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.

The question is: Why should the greedy work?

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.

I can't think of one :(

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

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.

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

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.

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:And it didn't work, but when I changed it to

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

`lower_bound(eil.begin(), eil.end(), i)`

might return`eil.end()`

, and it is undefined behaviour to dereference the end iterator.Got it, thanks

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(

[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?

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).69145588 WHAT HAPPEND TO A (div 2) It requires special solutions?

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.You probably want

`unordered_set`

actually. It took me a while to figure out python`set`

is not c++`set`

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

`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.true, worst case vs avg case — I did not even consider hacking.

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 :(

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.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.

How to solve div2 D ?

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.

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

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.

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

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

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?

all edge weights have to be distinct

Oops, can't believe I made this stupid mistake.

lol I'm stupid,

`vector<vector<bool>> cell(n, {false, false});`

is NOT how you init a 2D vector lmaoalso for 2B I even wrote up a DP solution :(

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

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

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.`block`

counts number of path blocks so that for example if a[2][3] is lava then any of a[1][2], a[1][3], a[1][4] will block the path. As far as I can tell this is enough to solve the problem (I can't think of any edge cases right now)it fail on pretest 7 .

Sorry, I don't know. I used square root decomposition.

https://codeforces.com/contest/1293/submission/69148329 it is showing uninitialise value usage in test7

okh i got my error

FSTForces.

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

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

I have WA on 132 :(

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

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

Many of the solutions failed due to overflow.

Fastest editorial

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

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.

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

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

What will happen when

`a = 1e15`

and`b = 1e4`

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

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$$$).

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

Auto comment: topic has been updated by AkiLotus (previous revision, new revision, compare).When ratings are gonna update???

any hints for C ?

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.

was it worth it

I'm on taxi cause I woke up late

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

what is your logic

weak pretests for D :(

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

When would this contest be rated?

Sometime. Nobody can tell you this.

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

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

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.

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 :/

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.

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)It allows parsing command line arguments into the source code. This thing is in fact not very common in competitive programming, but has more uses in actual practices.

TaeHo0o00o0N is 9th place WOW

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?Dp problem after all!

thanks for the nice contest