### Akikaze's blog

By Akikaze, 17 months ago,

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

• 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 Sooke 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!)
3. Isaunoya
4. espr1t
5. kkktl01
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.

• +703

 » 17 months ago, # |   +39 If you have epilepsy, you can check out my own friendlier version of editorial for this round here.
•  » » 17 months ago, # ^ |   0 oh, it's actually my favorite song =)) still can't believe that there is an artist (in Viet Nam) dare to make it.
•  » » 17 months ago, # ^ |   0 actually this is friendlier :) https://www.youtube.com/watch?v=qPpvKcNCMjY
 » 17 months ago, # |   +49 5 months ago???
•  » » 17 months ago, # ^ |   +3 Yeah, we planned for a contest long ago, but various things have happened in the last 5 months.
 » 17 months ago, # |   +9 Thanks for not RickRolling.
 » 17 months ago, # |   +172 I want to say that this is one of the best CF contests I remember. Recommend to participate for everyone!
 » 17 months ago, # |   0 So Interactive problem(s)... I hope we will find the best problems.
 » 17 months ago, # |   +9 Cytus XD Interesting!
 » 17 months ago, # |   +31 \PAFF/\PAFF/\PAFF/
 » 17 months ago, # |   +3 Round #614 is back!
 » 17 months ago, # |   +170 Petition to refer MikeMirzayanov as Mike "Don't call me Mike MikeMirzayanov Mirzayanov" Mirzayanov.
•  » » 17 months ago, # ^ | ← Rev. 3 →   +48 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: MikeMirzayanovMikeOutput: YES# Sample 2:Input: MirzayanovMikeMikeOutput: NO# Sample 3:Input: MikeMikeMikeMirzayanovMirzayanovMirzayanovOutput: YES
 » 17 months ago, # |   -6 UPD1 is amazing and funny at the same time.
 » 17 months ago, # |   +49 NEKO your songs are not as good as PAFF![User is now banned.]
•  » » 17 months ago, # ^ |   0 :D
 » 17 months ago, # |   +38 weeb
•  » » 17 months ago, # ^ |   0 siromaru is that you? :o
•  » » 17 months ago, # ^ |   -7 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
•  » » » 17 months ago, # ^ |   -10 Bandori
•  » » » 17 months ago, # ^ |   -15 osu!
 » 17 months ago, # |   +8 OMG!!! Cytus II!!! I must not miss this round!
 » 17 months ago, # |   +49 I think round 616 should be about Arcaea LOL
•  » » 17 months ago, # ^ |   +45 Maybe we can made Grievous Lady and Fracture Ray be the FINAL Problems ：D
•  » » 17 months ago, # ^ |   +13 Then next comes Cytus I, Deemo, VOEZ, Dynamix, Lanota, Hachi Hachi, Tone Sphere, ZyonI wonder if anyone has the guts to make a round themed on Bandori, iDOLM@STER, or LLSIF. That'll be hilarious to see XD
 » 17 months ago, # |   +137
 » 17 months ago, # |   +46 Are you ready y y y y y y y y y y y y y y
 » 17 months ago, # |   0 I'm waiting for it
 » 17 months ago, # |   +17 Brain Power was originally a SDVX FLOOR's song...
•  » » 17 months ago, # ^ |   +29 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.
•  » » » 17 months ago, # ^ |   +11 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!
 » 17 months ago, # |   0 Nice and simple editorial. But now I have epilepsy.
 » 17 months ago, # |   +32 Welcome to Æsir-FEST.
 » 17 months ago, # |   +57 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.
•  » » 17 months ago, # ^ |   +33 Rest easy friend, there is no irrelevant picture in the problem statements.
•  » » 17 months ago, # ^ |   +8 Fortunately, anime is not present in this announcement
 » 17 months ago, # |   +7 Can anyone explain to me problem D?
•  » » 17 months ago, # ^ |   0 SpoilerEditorial is available .
•  » » 17 months ago, # ^ |   +5 Problem D is too HARD.
•  » » » 17 months ago, # ^ |   +4 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.
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 what do you mean by go forward of backward? can you elaborate please
•  » » » » » 17 months ago, # ^ |   +3 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.
•  » » » » 17 months ago, # ^ |   0 I did exactly this, still, I was getting WA. 69137106
•  » » » » » 17 months ago, # ^ |   0 You may be overflowing.
•  » » » » 17 months ago, # ^ |   +12 well I mean D div1 but thanks anyway :D
•  » » » » » 17 months ago, # ^ |   0 Haha, really sorry. You're right :P
 » 17 months ago, # |   +33 Who else saw the editorial and thought he already missed the round xD
 » 17 months ago, # |   0 interesting :D hope my rating will increase after this.
 » 17 months ago, # |   +66 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
•  » » 17 months ago, # ^ |   0 People say he's still at the Black Market...
•  » » 17 months ago, # ^ |   0 orz Itst Rhythm Game Master!
•  » » 17 months ago, # ^ |   +40 Unfortunately, I have a piano session with Alice at that time.
 » 17 months ago, # |   -35 Shit why interactive problemm ;(
 » 17 months ago, # |   0 WTF... I am so confused for editorial tag before contest.
 » 17 months ago, # |   0 Just think VOEZ by Rayark is better for me XD
 » 17 months ago, # |   -10 Weaboo community is awesome!
 » 17 months ago, # |   +24 No weeboo shit please :((((((
•  » » 17 months ago, # ^ |   -9 Weeb is love
 » 17 months ago, # |   +3 Haha, some weird and interesting words around, but nice to google these words in comments and blog. Cool.
 » 17 months ago, # |   0 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
 » 17 months ago, # | ← Rev. 2 →   -8 I felt that D was easier than C. anyways thank you for the Amazing contest and editorial.
 » 17 months ago, # |   0 Epic
 » 17 months ago, # |   0 The music track for either Div 1F or Div 2F better be Floor Of Lava hehAlso hoping my favorite chaos chart Chrome VOX gets a problem
 » 17 months ago, # |   0 interesting:)
 » 17 months ago, # |   -21 Editorial is a song!!
 » 17 months ago, # | ← Rev. 2 →   -26 why editorial is a youtube video?PS-Someday i really want CF editorial youtube videos
•  » » 17 months ago, # ^ |   -24 Then Chinese will kill you.
•  » » » 17 months ago, # ^ |   -17 Why?
 » 17 months ago, # | ← Rev. 2 →   -6 .
 » 17 months ago, # |   0 Haha, well played.
 » 17 months ago, # |   -8 Everything will much better if there are no interactive problems :')
•  » » 17 months ago, # ^ |   +18 It ain't that bad when you get the hang of the interactive mechanism. ;)
 » 17 months ago, # |   +30 After knowing there might be an interactive problem ...
 » 17 months ago, # | ← Rev. 3 →   +8 Interactive problem!!! That's great.... Hope all of us will enjoy it
 » 17 months ago, # |   +17 The interactive problem will be solved with binary search
 » 17 months ago, # | ← Rev. 7 →   +9 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.]
•  » » 17 months ago, # ^ |   +18 ConneR txdy!(The NO.1 in the world)
 » 17 months ago, # | ← Rev. 2 →   +8 do not watch the MV if you have photosensitive epilepsy, seriously (another little cute MV i suggest is this)
 » 17 months ago, # |   -14 Can anyone tell me if tourist will get the first rank in the contest and Retired_MiFaFaOvO will not give the contest then who will be at top after the contest?
•  » » 17 months ago, # ^ |   +2 How does one give the contest?
 » 17 months ago, # |   +8 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%!!!
 » 17 months ago, # |   0 Now, Is it rated? is banned. I want to ask it! 807A - Is it rated? tourist also approves it!
 » 17 months ago, # |   0 as cytus is one of my favorite rhythm game,i'm so glad to see it in codeforce
 » 17 months ago, # |   +1 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.]
 » 17 months ago, # |   +1 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 17 months ago, # |   +25 I think you accidentally leaked the editorial.
 » 17 months ago, # |   +3 when will be themed contest based on sOsU
 » 17 months ago, # |   +13 "Can you see me?""John Cena...?"
 » 17 months ago, # | ← Rev. 2 →   +26 The true editorial is here.
 » 17 months ago, # |   +2 What's the score for each problem?
•  » » 17 months ago, # ^ |   0 will be out 3 seconds before the contest as usual :D
•  » » » 17 months ago, # ^ |   0 But now we can see :D.
 » 17 months ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 17 months ago, # | ← Rev. 2 →   +7 "interactive problem(s)"and finally — how many interactive problems in div1?
 » 17 months ago, # | ← Rev. 2 →   +13 Atcoder then codeforces :) what a balanced day
•  » » 17 months ago, # ^ |   +4 Atcoder then Codeforces :) what a fulfiled Sunday
•  » » » 17 months ago, # ^ | ← Rev. 3 →   0 Then codechef cookoff :D
•  » » » » 17 months ago, # ^ |   +1 This made my day unbalanced.
 » 17 months ago, # |   -11 Ok I'm stuck on C right now.The song is nice though. Like that.
 » 17 months ago, # |   +1 Cytus is a great game
 » 17 months ago, # |   +8 A very special contest for me, it's my 100th contest in Codeforces, and yes today's contest was really awesome.
 » 17 months ago, # | ← Rev. 3 →   -15 Any one can explain D?
 » 17 months ago, # | ← Rev. 2 →   -17 One can jump from ~1000 rank right into top 12 by solving E (Div2)
 » 17 months ago, # |   +34 I made a meme for div1D
•  » » 17 months ago, # ^ |   +20 Thanks, will include this in editorial after system test.
 » 17 months ago, # |   +16 how to solve Div2 E?
•  » » 17 months ago, # ^ | ← Rev. 9 →   +8 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
 » 17 months ago, # |   0 Nice contest!!!. I feel C was a lil bit easy.
 » 17 months ago, # |   0 Any hints for E?
 » 17 months ago, # |   0 Very nice contest after a long time.
 » 17 months ago, # |   +13 How to solve C division 1?
 » 17 months ago, # |   +2 Is this correct for Div2 E — Find diameter, then every number from [0,x] should appear consecutive on diameter edges.
•  » » 17 months ago, # ^ |   +8 No. It isn't correct even for a simple path with more than 2 edges.
•  » » 17 months ago, # ^ |   +3 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.
 » 17 months ago, # |   0 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
 » 17 months ago, # |   +2 How to solve Div.2 C? I am too stupid to solve such a problem.
•  » » 17 months ago, # ^ |   +10 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
•  » » » 17 months ago, # ^ |   0 I do not understand. What do you mean by "connect"?
•  » » » » 17 months ago, # ^ |   0 for example if the tiles (1, 2) and (2, 3) are with lava, then the column 1 is connected with column 2.
•  » » 17 months ago, # ^ |   0 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 columnCase 3: Right Cross.Now you can similarly decrease counter if you are turning off the lava cell.AC submissionHope you understood!
 » 17 months ago, # | ← Rev. 3 →   0 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?
•  » » 17 months ago, # ^ | ← Rev. 4 →   +10 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.
•  » » » 17 months ago, # ^ |   +5 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)$.
•  » » 17 months ago, # ^ |   +24 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?
•  » » » 17 months ago, # ^ |   0 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)$.
•  » » 17 months ago, # ^ |   +27 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.
•  » » » 17 months ago, # ^ |   0 Hmm. I had done this DP on (edge, direction) thing already once so it struck me quickly. Anyway, neat trick.
•  » » » 17 months ago, # ^ |   +10 Why (edge, direction)? Why not paths (u, v)?
•  » » » » 17 months ago, # ^ |   0 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.
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   +8 The question is: Why should the greedy work?
•  » » » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 17 months ago, # ^ |   0 I can't think of one :(
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +8 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) branchif you take the lower branch you would gain 5 * (size Left) now, but in the next run you would only gain 1* size Leftwhile if you take the upper branch you will gain 4 * size Left now, but 3 * size left in the second run which is betterso just looking at the current size without looking at how it is branching is not enough
 » 17 months ago, # |   -11 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.
•  » » 17 months ago, # ^ |   0 everything in this problem is <= 10^16, long long goes up to ~10^19, you probabilly had some other bug
•  » » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # |   0 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.
•  » » 17 months ago, # ^ |   +19 lower_bound(eil.begin(), eil.end(), i) might return eil.end(), and it is undefined behaviour to dereference the end iterator.
•  » » » 17 months ago, # ^ |   +5 Got it, thanks
•  » » 17 months ago, # ^ |   +3 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(
 » 17 months ago, # |   +5 [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?
 » 17 months ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
 » 17 months ago, # | ← Rev. 2 →   -37 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
 » 17 months ago, # |   0 69145588 WHAT HAPPEND TO A (div 2) It requires special solutions?
•  » » 17 months ago, # ^ |   +1 I recommend using set or map instead of vector, 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.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +3 You probably want unordered_set actually. It took me a while to figure out python set is not c++ set...
•  » » » » 17 months ago, # ^ |   +8 Well, $\log(k)$ isn't the end of the world.
•  » » » » » 17 months ago, # ^ |   0 Thank you for helping
•  » » » » 17 months ago, # ^ |   +8 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.
•  » » » » » 17 months ago, # ^ |   +3 true, worst case vs avg case — I did not even consider hacking.
 » 17 months ago, # |   +5 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 :(
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   0 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.
 » 17 months ago, # | ← Rev. 2 →   0 How to solve div2 D ?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 17 months ago, # ^ |   0 can you explain the part after sorted (and justification for that) ?
 » 17 months ago, # |   +40 Div.2D/Div.1B is a bad problem.
•  » » 17 months ago, # ^ |   +5 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.
 » 17 months ago, # |   0 What's the test 13 of 1D... I've been stresstesting my solution for over 10 minutes and no countercase was found.
 » 17 months ago, # | ← Rev. 2 →   0 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?
•  » » 17 months ago, # ^ |   +3 all edge weights have to be distinct
•  » » » 17 months ago, # ^ |   0 Oops, can't believe I made this stupid mistake.
 » 17 months ago, # |   +4 lol I'm stupid, vector> cell(n, {false, false}); is NOT how you init a 2D vector lmao also for 2B I even wrote up a DP solution :(
•  » » 17 months ago, # ^ |   +3 Don't say that, at least I'm more stupid than you.
•  » » » 17 months ago, # ^ |   0 what's worse is that my init, besides being undefined, also has wrong indexing order
 » 17 months ago, # |   0 https://codeforces.com/contest/1293/submission/69142492 what wrong in c .
•  » » 17 months ago, # ^ |   0 My code is nearly the same... once I can submit practice problems I'll try to debug
•  » » 17 months ago, # ^ |   0 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.
•  » » » 17 months ago, # ^ |   0 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)
•  » » » » 17 months ago, # ^ |   0 it fail on pretest 7 .
•  » » » » 17 months ago, # ^ |   0 Sorry, I don't know. I used square root decomposition.
•  » » » » » 17 months ago, # ^ |   0 https://codeforces.com/contest/1293/submission/69148329 it is showing uninitialise value usage in test7
•  » » » » » » 17 months ago, # ^ |   0 okh i got my error
•  » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 my fixed solution https://codeforces.com/contest/1293/submission/69150580 ignore r and c, should be x and y
 » 17 months ago, # |   +41 FSTForces.
 » 17 months ago, # |   +4 Anyway Div2 B would be more interesting as a DP problem instead of being able to guess the solution from the examples...
 » 17 months ago, # |   +16 1e17*100 will overflow long long->WA 127……
•  » » 17 months ago, # ^ | ← Rev. 2 →   +4 I have WA on 132 :( EDIT : Its indeed 1e17 * 100 overflow thing. changed limits to 2e16 and it passes :/
 » 17 months ago, # |   +3 Why Div2D/Div1B has so many system failed? :(
•  » » 17 months ago, # ^ |   +10 Many of the solutions failed due to overflow.
 » 17 months ago, # |   0 Fastest editorial
 » 17 months ago, # | ← Rev. 3 →   +32 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
•  » » 17 months ago, # ^ |   +26 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.
•  » » » 17 months ago, # ^ |   0 This works for me and is simple enough that I can remember next time, thanks!
•  » » » 17 months ago, # ^ |   +22 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; } 
•  » » » » 17 months ago, # ^ |   0 What will happen when a = 1e15 and b = 1e4?
•  » » » » » 17 months ago, # ^ |   -8 $a * b$ would evaluate to $1e19$ and the function will return $true$. What are you thinking about?
•  » » » 17 months ago, # ^ |   +13 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$).
•  » » » » 17 months ago, # ^ |   +10 Fair enough, I suppose my complaint is solely about doing dumb stuff under contest pressure. That shouldn't be your responsibility as setters.
 » 17 months ago, # |   0 Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).
•  » » 17 months ago, # ^ |   0 When ratings are gonna update???
 » 17 months ago, # |   0 any hints for C ?
 » 17 months ago, # |   +7 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.
•  » » 17 months ago, # ^ |   +12 was it worth it
•  » » » 17 months ago, # ^ |   +20 I'm on taxi cause I woke up late
 » 17 months ago, # |   +3 What a pity! In my solution to Div2 D, I used <= to see if the time was over T, instead of using
•  » » 17 months ago, # ^ |   0 what is your logic
 » 17 months ago, # |   +14 weak pretests for D :(
 » 17 months ago, # |   0 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
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 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.
 » 17 months ago, # |   0 When would this contest be rated?
•  » » 17 months ago, # ^ |   0 Sometime. Nobody can tell you this.
 » 17 months ago, # |   +4 why in Div. 1 D $k_i = 0$ was allowed ? isn't it very strange when we have $k_i = 1$ allowed ?
 » 17 months ago, # |   +5 I can't understand why weaks pretest ,is a mistake of problemsetters or a problem. Thanx for such a nice contest!
•  » » 17 months ago, # ^ |   +33 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.
•  » » » 17 months ago, # ^ |   +14 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 :/
•  » » » » 17 months ago, # ^ |   +25 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.
 » 17 months ago, # |   0 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)
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 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.
 » 17 months ago, # |   +3 TaeHo0o00o0N is 9th place WOW
 » 17 months ago, # | ← Rev. 3 →   -7 Oh, I hacked my solution(https://codeforces.com/contest/1292/submission/69143854) in Div1D with this testcase: https://codeforces.com/contest/1292/hacks/610526/testUPD: I hacked 10 solutions with this testcase. Why were tests so weak?
 » 17 months ago, # |   0 Dp problem after all!thanks for the nice contest