### KAN's blog

By KAN, 4 weeks ago, translation,

Hi everyone!

The Final Round of Technocup 2021 starts this Sunday, March 21, 2021 at 13:00 MSK (10:00 UTC)!

For those who want to compete on the same problems, we will hold two regular Codeforces Rounds in the evening: one for the first division, and another one for the second. The rounds are starting at Mar/21/2021 16:20 (Moscow time).

If you are a participant of the official Technocup Finals, you are not allowed to take part in the rounds in the evening. We ask participants of the official Finals not to discuss the problems in open media till evening.

The problems are prepared by: Alexander Golovanov399 Golovanov, Evgenii amethyst0 Belykh, Andrey AndreySergunin Sergunin, Alexey Aleks5d Upirvitskiy, Diego Diegogrc Garcia and me.

Also huge thanks to Bench0310, kokokostya, Um_nik, dorijanlendvaj, brunomont, Stepavly, antontrygubO_o, scnucjh, Nebuchadnezzar, wucstdio, golikovnik, kuviman, dantrag, BledDest, Supermagzzz, Maripium, geranazavr555, divanik, psevdoinsaf, Roms for testing and invaluable comments, and also to antontrygubO_o for the help in holding the mirror rounds.

Good luck!

Congratulations to winners of Codeforces Rounds!

Div. 1:

Div. 2:

Thanks for participation! Editorial.

• +368

 » 4 weeks ago, # |   +132 You missed " Notice the unusual timing "
•  » » 4 weeks ago, # ^ |   -172 You missed your brain
•  » » » 4 weeks ago, # ^ |   +102 Ok, thanks for letting me know
 » 4 weeks ago, # | ← Rev. 2 →   -44 Hoping for positive delta this time.
 » 4 weeks ago, # |   -27 Hoping for strong sample tests this time ;)
 » 4 weeks ago, # |   -15 Notice the unusual time and all the best to everyone
 » 4 weeks ago, # |   +256
•  » » 4 weeks ago, # ^ |   0 dude ur timeline is chaotic , can u tell desired rank to get to 1400+
•  » » » 4 weeks ago, # ^ |   +1 1400
•  » » » 4 weeks ago, # ^ |   0 Depends on how many participants participating in the round generally you need to be in the top 20% maybe and it differs when it's div 1+2 just being in top 30% would get you to specialist easily
 » 4 weeks ago, # |   +35 Is the official Technocup round (not the Div 1/2) rated? (not a bait question, genuinely curious)
•  » » 4 weeks ago, # ^ |   +4 Should be, all previous finals was rated
•  » » » 4 weeks ago, # ^ |   +2 The official contest is in a group rather than on the main CF contests page which is why I was wondering...
•  » » » 4 weeks ago, # ^ |   0 That answered my question I guess, goodbye Master.
 » 4 weeks ago, # |   +38 3 contests a day. Gonna be rough. - Kickstart - CF - Cookff
•  » » 4 weeks ago, # ^ |   +20 An ARC as well
•  » » 4 weeks ago, # ^ |   +7 same like like kickstart round A 2020 (kickstart -> atcoder -> codeforces) isnt it?? and worst of all that time too it was sunday :|
•  » » 4 weeks ago, # ^ |   0 leetcode as well.
•  » » » 4 weeks ago, # ^ |   0 CodeChef too
 » 4 weeks ago, # | ← Rev. 2 →   +2 AtCoder Regular Contest 115 — 5 PM (UTC + 6) CF DIV 1/2 — 7.10 PM (UTC + 6) MARCH COOK-OFF 2021 — 10 PM(UTC + 6)
 » 4 weeks ago, # |   +13 Last year, the contest was ethical and beautiful. Hope it will be the same this year!
 » 4 weeks ago, # | ← Rev. 4 →   +40 Today full of contests will coming...JOISC 2021 Day2 1p.m. — 6p.m.AtCoder Regular Contest 115 7.p.m. — 9p.m.CF Round #709 Div. 2 9.10p.m. — 11.10p.m. (Isn't it used to be 9.05 p.m.? Wondering for it)I've never participated in so many rounds in one day. It's busy without doubt, and I hope it'll also be a fulfilling and unforgettable day for me...P.S. UTC+8
•  » » 4 weeks ago, # ^ |   0 You forgot about Google Kick-start!!
 » 4 weeks ago, # |   -18 This round is rated or not...as it's not mentioned anywhere in the announcement ??
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   -29 Yes this round is rated
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -37 At least try to change it a bit when you copy a comment. UPD: Now it's better.
•  » » 4 weeks ago, # ^ |   +14 Codeforces Rounds (those that start with Codeforces Round #???) are always rated.
•  » » » 4 weeks ago, # ^ |   -56 Do converse also true XD?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   -30 .
 » 4 weeks ago, # | ← Rev. 2 →   -25 Hope you all do great in this contest ♥
 » 4 weeks ago, # |   +80 The Final Round of Technocup 2019 starts this Sunday, on the March 21, 2021 at 13:00 MSK (10:00 UTC)! Shouldn't it be Technocup 2021?P.S. If I misunderstand this, can someone please explain it to me?
•  » » 4 weeks ago, # ^ |   +75 I guess that they forgot to update the almost-copy-pasted part XDKAN please look into this.
•  » » 4 weeks ago, # ^ |   +125 Spoiler
 » 4 weeks ago, # |   +5 Atcder round will end exactly 10 minutes before the start of this round. Such a productive day
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 And this round ended 10 minutes before the start of Codechef Cook-Off :o
 » 4 weeks ago, # | ← Rev. 2 →   -8 Why unusual time though, so as to host it with the actual finals?
•  » » 4 weeks ago, # ^ |   0 I think they kept in mind, the time for other already announced contests, like cookoff and ARC.
 » 4 weeks ago, # |   +125 What is the score distribution for the tasks?
 » 4 weeks ago, # |   +62 How many problems will there be?
•  » » 4 weeks ago, # ^ |   +46 Its a surprise.
 » 4 weeks ago, # |   -7 How Many Problems will be there and problem ratings ???
•  » » 4 weeks ago, # ^ |   0 Problem *Scores
 » 4 weeks ago, # |   0 Delayed by 10 minutes
 » 4 weeks ago, # |   +6 Forget to release score distribution and make a 10 mins delay?
 » 4 weeks ago, # |   +25 Come on everyone and good luck!It's my first time to have a contest!
•  » » 4 weeks ago, # ^ |   0 Delayed for 10 minutes?
 » 4 weeks ago, # |   0 there is a delay!
 » 4 weeks ago, # |   -9 Round delayed?
 » 4 weeks ago, # |   -8 SO now what should i do for next 10 mins of my life?
•  » » 4 weeks ago, # ^ |   -40 plz dont simply copy paste someones else comments. this comment was written by me in the last edu round.
•  » » » 4 weeks ago, # ^ |   0 I am really sorry if I did this! but its a coincidence
•  » » 4 weeks ago, # ^ |   -8 You can sit and pray the round starts after this 10 minutes.
•  » » 4 weeks ago, # ^ |   0 It's a good idea to stay hydrated!
•  » » 4 weeks ago, # ^ |   0 See how many of your friends are online and taking part in this round? :P
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +14 Or remind your friends that you are online.
•  » » » » 36 hours ago, # ^ |   0 I GOT THE SAME NOTIFS!>_> and even yours
 » 4 weeks ago, # |   +77 Delay it some more times and the unusual timing will become usual again.
 » 4 weeks ago, # |   +3 what's the scoring distribution of the problems?
 » 4 weeks ago, # |   0 I guess score distribution is left for surprise.
 » 4 weeks ago, # |   0 So, the revealing of score distribution is gonna be the latest in codeforces history, lol!!
 » 4 weeks ago, # |   +16 Please don't delay this round more than this, we have to give cc march cookoff as well :( T_T
•  » » 4 weeks ago, # ^ |   +41 You know they don't delay it for fun, right?
•  » » » 4 weeks ago, # ^ |   +20 Yeah mate, I know . My apology for being a bit rude :(
•  » » » » 4 weeks ago, # ^ |   0 by mistake i locked my wrong solution instead of write due to technical glitch during start of contest will i get points of problem A as there is correct one but locked one is wrong please respond whosoever knows????
•  » » » » » 4 weeks ago, # ^ |   0 Once you locked your solution for A , the next solution of A will not be judged by the judge for competition,instead the judge will just take the response which u submitted just before locking. :-|
 » 4 weeks ago, # |   +6 Why score distribution for this round is not given
 » 4 weeks ago, # |   0 The contest is held live still the delay?
 » 4 weeks ago, # |   -18 Literally guys , again 10 minutes what to do for 10 minutes i controlled washroom for the contest Now fucked up !!
•  » » 4 weeks ago, # ^ |   +19 Man just go to the washroom, it's not worth it.
 » 4 weeks ago, # |   +8 Every minute seems like an hour now :)
•  » » 4 weeks ago, # ^ |   0 exactly man!
 » 4 weeks ago, # |   +15 Score distribution?
•  » » 4 weeks ago, # ^ |   0 I guess it will be a surprise
 » 4 weeks ago, # |   +3 no notice for unusual timing no score distribution whats going on?
 » 4 weeks ago, # |   0 All the best guys ! and Very Thanks authors!
 » 4 weeks ago, # |   -19 iS iT rAtEd?
 » 4 weeks ago, # |   0 Hope the contest does not delays furthur as there is contest on codechef too from 21:30 IST.
 » 4 weeks ago, # |   +9 How can someone solve A,B,C within 2 minutes unless they know the problems and the solutions beforehand! Ridiculous!!!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +9 Its clear they already know the questions. See this guy what a legendary speed he has https://codeforces.com/profile/OrleanMagic
 » 4 weeks ago, # |   +90 wtf? In two minutes this guy read 3 problems as well as solved them and then coded them.
•  » » 4 weeks ago, # ^ |   +22 They are geniuses bro
•  » » » 4 weeks ago, # ^ |   -25 YES
•  » » 4 weeks ago, # ^ |   +11 The No.2 Solve A and C in less than 1 minute ...?That's so strange, at least for me I can't type that fast...
•  » » 4 weeks ago, # ^ |   +13 because its based on technocup, which has already ended at the moment of beginning of the d2 round and they might be its participants. i guess they will get punished somehow.
•  » » 4 weeks ago, # ^ |   +28 They have been removed.
•  » » » 4 weeks ago, # ^ |   +9 how about dr_haider ? he also solved 2 problems in 2 mins
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   -8 how about [insert geniosity here]? he/she also solved x problems in y mins :O
•  » » 4 weeks ago, # ^ |   0 Me : Read only first question
 » 4 weeks ago, # |   +20 Total solve for each problem not visible on the dashboard(Div2)
•  » » 4 weeks ago, # ^ |   0 Same for Div1
 » 4 weeks ago, # |   +26 504 Gateway Time-outUnrated again?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +1 Now I face the problem The statement is not available now...
•  » » 4 weeks ago, # ^ |   0 Down only at the beginning. Later it was fine until the end of contest (at least for me).
•  » » 4 weeks ago, # ^ |   -8 No, m1/m2/m3 were working fine for the whole round.
•  » » » 4 weeks ago, # ^ |   0 But it lacks some useful functionality. E.g. statistics of solved tasks (one can determine which task better to solve next) and hacking (but it was too rare in this round).
•  » » » » 4 weeks ago, # ^ |   -15 Statistics of solved tasks was available in the bottom of the standings page
•  » » » 4 weeks ago, # ^ |   0 Idea to make m[X] for all users mandatory during the beginning of the round, e.g. first 30 minutes or so, when most participants upload their A and platform overloads.
 » 4 weeks ago, # | ← Rev. 2 →   +5 I am submitting using m3 and not able to see if my solution is submitted or not.
 » 4 weeks ago, # |   +53 It is being unethical and ugly. Again.
 » 4 weeks ago, # |   +6 Hey guys I can't see the statements of the problems now. What's wrong?
•  » » 4 weeks ago, # ^ |   +4 Its not visible in m1 but visible in codeforces.com
•  » » » 4 weeks ago, # ^ |   0 Thanks very much! Now I got the statements
 » 4 weeks ago, # | ← Rev. 2 →   -42 Toughest Prob B ever!!
•  » » 4 weeks ago, # ^ |   +3 B was pretty hard if not familiar with modular arithmetic. C was easier than B for me.
 » 4 weeks ago, # |   +12 MikeMirzayanov There were a few people who read , coded and submitted about 2-3 problmes within a first few minuites, I feel thy already knew the problems. Please do us a favour and disqualify them.
•  » » 4 weeks ago, # ^ |   +38 They have been removed.
•  » » » 4 weeks ago, # ^ |   0 Thanks!
•  » » » 4 weeks ago, # ^ |   +2 I submitted A within 7-8 min but the page wasn't loading so I resubmitted it on m1.codeforces. The same code without any change was submitted. Both the submissions passed but the later solution timing was considered and I was given some penalty for two submissions with exact same code. Check it and if possible resolve the rating changes.
•  » » » » 4 weeks ago, # ^ |   0 bro....I lost around 200 points due to this....
 » 4 weeks ago, # |   +6 Pathetic Contest for me IMO.. No offense to anyone
•  » » 4 weeks ago, # ^ |   0 For me I think the contest has been decided by A only and that too I was unable to submit quickly because the submission page wasn't loading ....
•  » » » 4 weeks ago, # ^ |   0 Which caused me almost a drop of 2-3k in rankings in my estimate and I think it's gonna be almost the same till end too....
 » 4 weeks ago, # |   +8 This is the actual power of your speed Rank 1591 with A solved Also Rank 9160 with A solved :D
•  » » 4 weeks ago, # ^ |   0 Yeah before I solved B I was once 3300 while others who only solve A too got rank 500...
 » 4 weeks ago, # |   0 in problem b when i 1st time submited it gives me RE..i tried to find error but couldnt find it..so i tried to submit the same code added some comment line(because you cant submit same code)..and i got WA for same code..What happening :")?
•  » » 4 weeks ago, # ^ |   +8 Submit again , you might get AC :D!
•  » » » 4 weeks ago, # ^ |   0 by mistake i locked my wrong solution instead of write due to technical glitch during start of contest will i get points of problem A as there is correct one but locked one is wrong please respond whosoever knows????
•  » » 4 weeks ago, # ^ |   0 if you have written on c++, it's probably undefined behavior
 » 4 weeks ago, # |   0 by mistake i locked my wrong solution instead of write due to technical glitch during start of contest will i get points of problem A as there is correct one but locked one is wrong please respond whosoever knows????
•  » » 4 weeks ago, # ^ |   0 Yes, if it passes the system test.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -25 a
 » 4 weeks ago, # |   0 hardforces!! ( atleast for me don't know about others )
•  » » 4 weeks ago, # ^ |   0 Yes!!
•  » » 4 weeks ago, # ^ |   +30 For $Div.1$ it was more like implementation-forces
 » 4 weeks ago, # |   +23 Really nice problems, no idea how to solve them though lol
 » 4 weeks ago, # |   0 I want to clarify 1 one thing,i made submission of problem A at 7 min from m1.codeforces ,and after submitting B from codeforces.com,i saw A has not been marked green ,while its pretests are passed,again i submitted from codeforces.com,then WTF,my score was reduced from 486 to 218,seriously dude,is this fair??
•  » » 4 weeks ago, # ^ |   0 And there is one more strange thing-I submitted A and B both in m1.codeforces.com and I found that A didn't mark green(Passed pretests) but B did. Now I'm worried that if I won't get any scores in A :(
•  » » » 4 weeks ago, # ^ |   +4 See standings page to confirm. That page was working fine.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah but the only problem is that I can't lock my problem :(
•  » » 4 weeks ago, # ^ |   +2 Mine is also not marked green. It must be a technical glitch, but you should not submit it again. This problem may be happening with many others.
•  » » » 4 weeks ago, # ^ |   0 So you can't resubmit it during the game, right?
•  » » » » 4 weeks ago, # ^ |   0 You can submit as many times as you want. But you should not, as it leads to increased penalty also.And ya, the same code can not be submitted multiple times.
•  » » 4 weeks ago, # ^ |   +1 Most recent submission time is taken into account.If pretests are passed and you submitted again then it counts as "Some edge cases striked you ,which now u think your submitted code wouldnt pass system test and thats why u resubmitted" and thats why most recent time is taken into account,it seems.
•  » » 4 weeks ago, # ^ |   0 same :(
•  » » 4 weeks ago, # ^ |   +2 Due to technical difficulties, some problems may be shown as unsolved. However, on the tab "My submissions" you still was able to see your submissions.
•  » » » 4 weeks ago, # ^ |   +20 but I wasn't able to lock the problem for hacking due to that :D
•  » » 4 weeks ago, # ^ |   0 I'm the same way.
 » 4 weeks ago, # |   -18 I don't know if it's just me, but it was not a balanced contest.
 » 4 weeks ago, # |   +15 I submitted A at 14 minutes 50 second and italso passed pretests, but it doesn't show green colour and option to lock in Dashboard. Though, it is there for other 3 problems.
 » 4 weeks ago, # |   +26 Problem D: fix a source vertex $u$ and let $M = \max_v l$ over all triples $(u, v, l)$. Add an $(n+1)$-th dummy vertex to the graph, and for each triple $(u, v, l)$ add an edge from $v$ to the dummy vertex with weight $M - l$. Now an edge is useful if it is in a path of length at most $M$ from $u$ to the dummy vertex. Now the problem reduces to doing two Dijkstra's (one from $u$, one from the dummy vertex) and checking each edge. Since the graph is complete in the worst case, it was best to implement the $O(n^2)$ version of Dijkstra (heap-based version gave TLE for me). Final runtime $O(n^3)$.
•  » » 4 weeks ago, # ^ |   0 I used a somewhat different approach with the same complexity and was hitting some MLE problems because of heap instead of TLE.
•  » » 4 weeks ago, # ^ |   +26 Why not Floyd?
•  » » » 4 weeks ago, # ^ |   -6 Are you asking if there is an alternative solution using Floyd's, or saying there is one?
•  » » » » 4 weeks ago, # ^ |   +7 There is one.See my code for details.
 » 4 weeks ago, # |   -21 KAN What the hell is pretest 16 in D?
 » 4 weeks ago, # |   +6 How to do div2D?
•  » » 4 weeks ago, # ^ |   0 can you explain div2 B,C?
•  » » 4 weeks ago, # ^ |   0 Each elements is only removed at most once. Therefore, we keep two std::sets, one to keep track of the remaining elements, and one that keeps candidates for deletion. When deleting a vertex, we can do so by an upper_bound operation on the second set, update the next vertex that is not deleted.Complexity: $O(n \log n + n \log max(a))$.Code: 110638935
 » 4 weeks ago, # |   -8 Is it rated ?
•  » » 4 weeks ago, # ^ |   +9 for sure
 » 4 weeks ago, # |   +10 I literally wrote some random shit in C and it passed pretests. Waiting for fst :(
 » 4 weeks ago, # |   0 How to solve div2 B and C?
• »
»
4 weeks ago, # ^ |
Rev. 5   +3

# Problem B

If there is a solution, then, for all i > 1:

If ai-1 <= ai then ai - ai - 1 = c

If ai-1 > ai then ai - ai - 1 = c - m.

Let c1 = ai - ai - 1

If the values of c or c1 are inconsistent for different values of i then there is no solution.

If either is unknown (i.e. the array is monotonically increasing or decreasing) then any value of m works.

Otherwise the only possible value of m is c - c1. If this is greater than the biggest value in the array it is the solution; if it isn't then there is no solution.

 » 4 weeks ago, # |   +1 Any hints for Div2 D ?
•  » » 4 weeks ago, # ^ |   0 Linked list & TreeSet
•  » » 4 weeks ago, # ^ |   0 queue
 » 4 weeks ago, # | ← Rev. 2 →   +13 Duh, I got down to 107 queries in E >_> (worst result after simulating tens of thousands of random tests locally). Is 105 provably optimal (in which case I will admit I was not close) or did I lacked just a few small tweaks :|?
•  » » 4 weeks ago, # ^ |   0 I sincerely hope it wasn't, because otherwise I spent 1.5 hours for nothing :(((((( My approach was to find largest $t$ s.t. worst case asking $(l+r) \cdot t$ and always getting lower answer fits in current number of remaining questions. What was yours?
•  » » » 4 weeks ago, # ^ |   0 That's what I did as well. I passed pretests (who knows about systests...) by using this approach, running it on an interactor I wrote, and tweaking it in order to maximize the minimum number of queries left on $2^{46} - 1$, $2^{45},$ or $2^{46}.$
•  » » » 4 weeks ago, # ^ |   +18 On the beginning I tried doubling my budget till I hit first bust ("Fraudster" response). At that point my search space is of form $[L, R]$, where $2L \ge R$ (which means that after failed query I can regain a big part of my budget by asking L). Then I try to do skewed binary search. If I ask about midpoint of my interval then no matter what the answer is, I am left with interval of the same length, however in one of these cases I lost a lot of money, so this is probably not the optimal dividing point. I ask about $\frac{L \cdot \phi + R}{1 + \phi}$ (where $\phi = 1.618...$). I either end up with a longer interval after gaining money or shorter interval after losing money. Don't ask me why $\phi$, I just somehow felt it would be good and my experiments confirmed it was a sensible choice.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I was thinking that something like that might pass, but I was assuming that my apporach is a generalization of your's, therefore I would just write mine. I guess it turns out that my approach suffers greatly because of precision, therefore it didn't workupd: turns out $(l+r) \cdot t$ isn't equivalent to $\frac{(l \cdot t + r)}{1 + t}$.................
•  » » » » 4 weeks ago, # ^ |   +13 It seems that after raising number of testcases to a few millions my code got up to even 110 queries. However I added an opt suggested to me by kabuszki that if I have a lot of money I can ask closer to half, if I have not a lot, I ask closer to L (I threw in some random constants to quantify this) and after that it doesn't exceed 104 queries on a few millions of cases.
•  » » » » » 4 weeks ago, # ^ |   0 Yes, I passed with that idea.
 » 4 weeks ago, # | ← Rev. 2 →   +25 How to solve Div 2 E?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +32 We can do this with DP. Let $dp_i$ denote the maximum beauty you can get by taking photos of only the first $i$ buildings and $bef_i$ indicate the greatest index $j < i$ such that $h_j$ < $h_i$ or $-1$ if no such $j$ exists. Now the transitions are quite simple.$dp_i$ = $max(\displaystyle\max_{bef_i \leq j < i}dp_j + b_i, dp_{bef_i})$The first part is when building $i$ is in a different photo than building ${bef_i}$, and since all buildings in the photo which the building $i$ is present are taller than it, we will only consider the beauty of this building. The second part corresponds to the case when building $i$ is in the same photo as $bef_i$. In this scenario, as all the building after $bef_i$ are taller than it, none of the buildings there will contribute to the beauty of the photo. You can implement this using segment tree. Also, make sure to handle the case where $bef_i = -1$
•  » » » 4 weeks ago, # ^ |   0 Can you explain what you will be using the segment tree for here?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +16 For the range max queries in the first part of the $dp_i$. If implemented naively it might end up with a $O(n^2)$ complexity. You can use a segment tree or you can use a stack as mentioned in the below comment.
•  » » » 4 weeks ago, # ^ |   0 I think it should be max( max ... )
•  » » » » 4 weeks ago, # ^ |   +10 Yep, thanks. Updated.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 Thanks for your solution.I implemented it without segment tree: maintain a monotonic stack. After each operation, the last item in stack stores $(i, \displaystyle\max_{bef[i] \leq j < i}dp_j)$, the second to last item stores $(bef[i], \displaystyle\max_{bef[bef[i]] \leq j < bef[i]}dp_j )$, and so on. It can reduce complexity to $O(n)$. Core codevoid solve() { int n = read(); vector h(n+1,0), b(n+1); vector dp(n+1,0); for(int i = 1; i <= n; ++i) h[i] = read(); for(int i = 1; i <= n; ++i) b[i] = read(); stack> st; // minh_idx, maxdp for(int i = 1; i <= n; ++i) { ll mxdp = dp[i-1]; while(st.size() && h[i] < h[st.top().first]) { mxdp = max(mxdp, st.top().second); st.pop(); } dp[i] = mxdp + b[i]; if(st.size()) /* j != -1*/ dp[i] = max(mxdp + b[i], dp[st.top().first]); st.push({i, mxdp}); } printf("%I64d\n", dp[n]); } 
 » 4 weeks ago, # |   +5 Today at starting site was again too slow and when i submitted A it does't reflect in submission so I opened lightweight version of CF and submitted there but later i came to know previous was also submitted ans 50 points got reducted for resubmission :/
•  » » 4 weeks ago, # ^ |   0 I did the same thing and gained -50 points. My bad :(
•  » » 4 weeks ago, # ^ |   0 Same thing happened with me
 » 4 weeks ago, # |   0 Can anybody give me some hints for B.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 This one passed pretests. Nothing much to explain. Spoiler int n ;read(n) ; vta(n) ;read(a) ; setpos,neg ; int mx =a[0] ; FOR(i,1,n){ if(a[i]-a[i-1]>=0) pos.insert(a[i]-a[i-1]); else neg.insert(a[i]-a[i-1]) ; umax(mx,a[i]) ; } if(sz(pos)>1||sz(neg)>1) pf("-1") ; int A=*pos.begin() ; int B=-*neg.begin() ; if(sz(neg)==0||sz(pos)==0){ pf(0) ; } if(A+B<=mx) pf("-1") ; print(A+B,A) ; } 
•  » » 4 weeks ago, # ^ |   +1 Hint: If an array is valid, then every subsequent difference d=a[i]-a[i-1] will be c if d is positive, and m-c if d is negative.
•  » » » 4 weeks ago, # ^ |   0 What about if the array has only negative delta, ie all steps are decreasing?
•  » » » » 4 weeks ago, # ^ |   0 then m can be largest possible
•  » » » » » 4 weeks ago, # ^ |   0 Example, a[]={ 5, 4, 2 }Which c, m would make this work?
•  » » » » » » 4 weeks ago, # ^ |   0 won't work. 4 — 5 != 2 — 4
•  » » » » » » » 4 weeks ago, # ^ |   0 Ok, what about { 5, 3, 1}?
•  » » » » » » » » 4 weeks ago, # ^ |   +3 (6, 4), (7, 5), (8, 6) and so on
•  » » » » » » » » 4 weeks ago, # ^ |   0 In this case the answer is 0.
•  » » » » » » 4 weeks ago, # ^ |   0 Suppose array is decreasing, then a[i — 1] — a[i] = di. And di is same for is i(otherwise answer will be -1), di > 0. Now d = di(any). also, d = m — c. Here m can be any value, c can have any value because d > 0. (so c can have value of [0, m — 1]). So we can any pair of m, c. So finally answer will be 0.
•  » » » » 4 weeks ago, # ^ |   0 It's still true. The next observation is that if either all are negative, all are positive, or all are 0, then there are no restrictions on m.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I couldn't solve the problem when array has only negative delta For example if the array is 10,8,6,2 like this.
•  » » » » » » 4 weeks ago, # ^ |   0 In that case, if adjacent differences are equal the answer is 0, otherwise -1.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 if d is negative, then why can't 2m-c, 3m-c or in general, Zm-c also one of the possibilities?
•  » » » » 4 weeks ago, # ^ |   0 In our case, the difference between every consecutive number will have magnitude at most m (since each number is between 0 and m-1). c
 » 4 weeks ago, # |   +167 The lightweight websites m1, m2, m3 were a bit too lightweight this time... Spoiler
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Same happened with me, but when I reloaded CF official page, it worked.
 » 4 weeks ago, # |   -9 Such hard problems.
 » 4 weeks ago, # |   +1 This contest was brutal(Donno about others but for me it was).. T_T :(
•  » » 4 weeks ago, # ^ |   0 I always like these type of contests which is based on some contests. They usually contain nice problems.
•  » » » 4 weeks ago, # ^ |   +1 Obviously problems were nice, but this type of nice problemset is inversely proportional to +delta. (atleast for me) T_T.
 » 4 weeks ago, # |   0 in div 2 e :for 4th sample why answer is 96?if we make photo in this way:1)1,2,3,4,52)63)74)8,95)10beauty is 100am i wrong?
•  » » 4 weeks ago, # ^ |   +3 yes beauty is -8 + (-16) + 4 + 12 + 3 and it's not equal to 100
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 1) 1,2,3,4,5 -> -82) 6 -> 43) 7 -> -104) 8,9 -> 125) 10 -> 3total beauty is 1
•  » » » 4 weeks ago, # ^ |   0 tnx
 » 4 weeks ago, # |   0 Why Div. 2 A was so easy?
•  » » 4 weeks ago, # ^ |   +6 it was a trap
 » 4 weeks ago, # |   +1 Does submitting two solutions incur a penalty? I don't know how maybe due to server issues my solution got submitted twice to problem A within 9 seconds and got a 50 point penalty. Any idea why?
•  » » 4 weeks ago, # ^ |   +2 Yes there is a penalty of 50 points for resubmission. You can message the contest setter telling him/her that it was by mistake you submitted the same code. He/She can help you.
•  » » » 4 weeks ago, # ^ |   0 If the code is exactly same, codeforces doesnt allow you to submit.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I will link to my submissions when codeforces removes the restrictions. Thats why I said it is most likely due to a server side bug. Here are the submissions : Submission1, Submission2
•  » » » » » 4 weeks ago, # ^ |   -7 Submitted exactly same solution ,lost more than 250 points
•  » » 4 weeks ago, # ^ |   0 Same thing happened with me
•  » » 4 weeks ago, # ^ |   0 Exactly same happened with me.
 » 4 weeks ago, # | ← Rev. 2 →   +17 My solution for D:Let $w_{uv}$ be the weight of the edge between vertex $u$ and $v$ (or $\infty$ if it does not exist), $d_{uv}$ be the shortest distance of $u$ and $v$ (or $\infty$ similarly), and $l_{uv}$ be the third element of one of given triplets that forms $(u, v, *)$ or $(v, u, *)$ (or $0$ if such triple does not exist).For each $(u, v)$ such that $u < v$ and $w_{uv} < \infty$, we want to check if there exists a pair of vertices $(a, b)$ such that $d_{au} + w_{uv} + d_{vb} \leq l_{ab}$. This is equivalent to ${}^\exists a,\; d_{au} + w_{uv} \leq \max_b ( l_{ab} - d_{vb} )$. We can precalculate $f_{av} := \displaystyle \max_b ( l_{ab} - d_{vb} )$ in $O(n^3)$ time, then check ${}^\exists a,\; d_{au} + w_{uv} \leq f_{av}$ in $O(n)$ time for each $(u, v)$. Therefore the problem has been solved in a total of $O(n^3)$ time.
 » 4 weeks ago, # |   +1 how sad it is when codeforces does not work:(
 » 4 weeks ago, # |   +86 Rounds for children are so bizarre, each time I participate in them it's such a disaster.The mice cried, pricked, but continued gnawing the cactus...
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +11 From Russian saying. Image
•  » » » 4 weeks ago, # ^ |   +8 Yes, it's from the anecdote where the mice wanted to become hedgehogs, or alternatively from the story in which a real cactus was hurt by hungry mice which weren't able to find some less painful comestibles.
 » 4 weeks ago, # |   0 Is this round rated?
 » 4 weeks ago, # |   +23 The problem E is a very great problem, especially limited the number of inquiries <= 10^{14} and let my multiplication get TLE(because of invalid queries) Thank you very much!
 » 4 weeks ago, # |   -20 BrokenForces ;)
 » 4 weeks ago, # |   +6 B > C. Just another day at CF.
 » 4 weeks ago, # |   0 Can't wait for editorial to see the intended solution for Div2 D. I couldn't do it in less than O(n^2)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I have ~ O(n) solution using vector of deques
•  » » » 4 weeks ago, # ^ |   0 would you mind sharing the idea behind it?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Let's consider sequence p[1], p[2], ..., p[k], where GCD(p[i — 1], p[i]) != 1 for each neighbor pairs. We can store this sequence as a deque. Let's simulate the process and parse the given array into these deques. Then we have obvious property: if you delete p[1], you start from p[2] and go until p[k], and for each neighbor pairs GCD is also > 1. We don't need to check it twice, let's just remove the first element from the deque. After that let's consider two neighbor deques q and p. If GCD(q.back(), p.front()) != 1, we can merge them(you can use small-to-large to do it more efficiently). You can do it while it is possible to remove at least one element. After few operations we'll get one deque, let's consider it as given array and do the same.
•  » » » » » 4 weeks ago, # ^ |   0 That's neat, I regret not being able to solve it
 » 4 weeks ago, # | ← Rev. 2 →   +1 geranazavr555 when will codeforces be fully open ?
•  » » 4 weeks ago, # ^ |   0 After the announcement of the results of the technocup is over.
 » 4 weeks ago, # |   0 Why is viewing user profiles blocked?
•  » » 4 weeks ago, # ^ |   0 I guess because of techno Cup
•  » » » 4 weeks ago, # ^ |   +5 And the rationale for this is what?
•  » » » » 4 weeks ago, # ^ |   0 Maybe because you can look at their solutions since it was a "different" contest.
•  » » » » 4 weeks ago, # ^ |   +11 To avoid leakage of technocup results
 » 4 weeks ago, # |   0 In Div2 C why it was not given that "nobody is chosen strictly more than " Ceil of m/2...I got wrong thrice on it due to assuming it to be rounded down :(
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I also get confused each time.. Remember in ceil, brackets are curved at top and in floor, they are curved at bottom..
•  » » 4 weeks ago, # ^ |   +3 It was mentioned
 » 4 weeks ago, # |   +36 My soln of D -Let d[u][v] be the shortest distance between u and v. O(n^4) soln - Let x,y,w be an edge. u,v,l is a triplet.x,y is good if d[x][u]+w+d[v][y]<=l <=> 0+w+d[v][y]<=l-d[x][u].Its equivalent to adding (x,v,l-d[x][u]) as new triplet. You can always remove duplicate triples by keeping the one with has l maximum.So you can use initial given triplets to generate O(n^2) new triplets.At last, for each edges just check triplets which have an endpoint common with the edge. Overall it takes O(n^3).
 » 4 weeks ago, # |   +25 Did someone else use flows on Div2C??
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 I did that too. I'm surprised so many people had greedy instead of this solution.
•  » » » 4 weeks ago, # ^ |   +5 how did you saw other people's solution ..I'm not able to see anyone's solution from standings??(its just loading..)
•  » » » » 4 weeks ago, # ^ |   0 From discussing with other people.
•  » » 4 weeks ago, # ^ |   0 Yeah! Dinic just worked fine. Was reluctant initially to implement as was quite sure it will TLE. Implemented it when the round was about to be over. Funny.
•  » » » 4 weeks ago, # ^ |   +7 Dinic on bipartite graphs works with complexity $O(|E|\cdot\sqrt{|V|})$.
•  » » 4 weeks ago, # ^ |   0 Yeah, I'm suprised that the Greedy apprroach work in this problem, my friends say that they use Greedy algo to solve without proof = )
•  » » » 3 weeks ago, # ^ |   +5 Really without proof ???
 » 4 weeks ago, # |   0 A was so easy, everyone signed up for the contest, but the surprise was B. oh shit, contest is not beautiful
•  » » 4 weeks ago, # ^ |   0 hello! it's beautiful. listen to me.
•  » » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   +194 This really makes me hate myself.
 » 4 weeks ago, # |   +128 div2 C problem: if he has only one friend, how can make other friends offended?
•  » » 4 weeks ago, # ^ |   +2 lol , nice one.
 » 4 weeks ago, # |   0 Any hints for div2C?
•  » » 4 weeks ago, # ^ |   0 one more
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -8 Greedy works. Initially, for each day, select any friend available that day. Let's call the most common friend X. If friend X is chosen more than half the days, iterate over all days where friend X is selected and select any other friend. It can be shown this will not increase the count of any other friend above half. Stop if friend X's count is no longer more than half the days. If friend X still appears too many times (because there were too many days with no other friend available), it's impossible.
•  » » 4 weeks ago, # ^ |   0 HINT 1:-if all friends appear in less than ceil(m/2) ... ans is pretty simpleHINT 2:-if any friend(let's call him x) appear more than ceil(m/2) times then invite this friend for ceil(m/2) times on days and for rest days invite anyone(except the one you invited ceil(m/2) times already). This will automatically obey the condition.Now on which days should invite x.Invite x on those days in which only he is allowed(let call this num y) and rest on any day in which x is allowed.if(y>ceil(m/2) then ans = "NO" ..... It is obvious.I hope this helps
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I will try to explain what I did... Firstly I choose those friends whose count in all games (i.e-in all m days) is less than max allowed, Max allowed is ceil(m/2).We can use these friends on all days wherever they are possible because they can all be used at once and it will always be optimal and it will not violate the maximum usage condition. Now you can now take all the friends whose count is greater than max allowed.Now the question arises which friend to use and on which days to use. So, for each friend you can choose the days where there are less possibilities and that particular friend is possible on that day.I hope you understand.Sorry for my poor grammar.
•  » » 4 weeks ago, # ^ |   0 One can use a greedy approach in this problem. Only catch is that we need to consider those days beforehand on which only a single friend is available and after that greedily allot friends having least count on remaining days. If on any remaining days, the friend having least count exceeds the limit, the answer is "NO".So, one can keep a count of frequency of friends used till now and min heap to obtain the least used friend on each day. Refer to my submission for more clarity :My submission. Hope this helps!
 » 4 weeks ago, # |   0 110670278 Can anybody tell me what is wrong in this code. Thank You
 » 4 weeks ago, # |   +8 I pass pretests in C, but why it doesn't turn green nor turn red?
•  » » 4 weeks ago, # ^ |   0 Does it mean FST?
•  » » » 4 weeks ago, # ^ |   +8 I had same issue with div2A. I got this reply : Some features may be disabled due to hosting Technocup, sorry for that. You got AC for A
•  » » 4 weeks ago, # ^ |   +3 Check the standings. For some reason, the problems page is bugged.
•  » » 4 weeks ago, # ^ |   0 Same happened with me for A, when CF was down my same solution was submitted twice, due to which got 50 points penalty ;(
 » 4 weeks ago, # |   0 I was able to solve A only :( ! Not sure why my C gave WA and now I am unable to reopen the contest.
 » 4 weeks ago, # |   +9 bring back the good old codeforces!!!
 » 4 weeks ago, # |   +12 Why haven't system tests started yet?
 » 4 weeks ago, # |   +61 But why does Div2 D/ Div 1 B have to be literal dog shit? It's almost like the people who proposed to let this kind of garbage appear in a Codeforces round don't want anyone to have fun participating it.
•  » » 4 weeks ago, # ^ |   +9 +++
•  » » 3 weeks ago, # ^ |   0 Could you please explain why it was a bad problem ?
 » 4 weeks ago, # |   0 any hints for ques div2-B ?
• »
»
4 weeks ago, # ^ |
0

According to statement of this problem "c is equal or less than m".

So by think logically result is has only two condition.

Let first value is x Following second value has only two condition.

# case 1. x + c >= m (x+c % m == x + c — m)

following number(x + c — m) is equal or less than first number. Because c <= m, so x + c — m <= x

So, this case could be find m — c value by deducting first number to second number.

# case 2. x + c < m

In this case, following number(x + c) is bigger than first number. So, this case could be find the c directly.

By doing this recursively.

If m, c is constant, c and m — c is must be unique if exist. If not, you must control exception handling.

•  » » » 4 weeks ago, # ^ |   0 Hey , can you explain why in the case 1, we haveI am going through the eqn. then how can we say that k is 1 ?
•  » » » » 4 weeks ago, # ^ |   0 We are interested in remainder not quotient.So you don't have to know exact value of quotient.It can be understood that the problem is to list the remainder divided by m in a arithmetic sequence with an initial term of s and a tolerance of c.Suppose that x modulus m is m1 (0<= m1 < m) By following case1, m1 + c is above m. So, it can be decided my m once more. Therefore, remainder is m1 + c — m. You don't have to what quotient is.
 » 4 weeks ago, # |   +84 I have some serious doubts about performance of Alan4ik. I don't believe that any purple user is capable of solving B and C significantly faster than all reds (he solved B at 0:03, A at 0:07 and C at 0:16) and this competition being a mirror of Technocup explains pretty well how it was possible
•  » » 4 weeks ago, # ^ |   0 some users in div.2 solved first 3 problems in starting 1 minute of the contest
 » 4 weeks ago, # |   -12 I Encountered some problem while trying to submit problem A, which led to a delay in submit time and a down my ranking in the standing list, and the resulting from it confusion prevented me from focusing on the rest of the issues. Which of you happened to him like this?
 » 4 weeks ago, # |   +40 Please add (n = 1) case to pretest in next contest. TY.
 » 4 weeks ago, # | ← Rev. 2 →   0 How sneaky is div2 B...
•  » » 4 weeks ago, # ^ |   0 noticing the gaps between the adjacent elements: there can only be c or c - msince c < m, c is positive and c - m is negativeif there only exists one positive value or one negative value, then any value would do
 » 4 weeks ago, # |   0 Me after FSTing on B : Hey cyan, here I come !
•  » » 4 weeks ago, # ^ |   +8 The rating predictor doesn't show anything for me. Strange!
•  » » 4 weeks ago, # ^ |   0 What does FST stands for?
•  » » » 4 weeks ago, # ^ |   0 Failed System Test
 » 4 weeks ago, # |   +2 Weak pretests are so common now in codeforces.
 » 4 weeks ago, # |   0 Nice Pretest for B :) . Bro I literally got a jump of 2k after FST on B .
 » 4 weeks ago, # |   0 in second test case of div2-B i am getting this result- ''wrong answer Jury has answer to test 34, but participant has not (test case 34)'' what does this mean ?
•  » » 4 weeks ago, # ^ |   0 you must be printing 0 or -1.
 » 4 weeks ago, # |   0 So painful to solve D just three minutes after the endYet so lovely that so many people got FST in B
•  » » 4 weeks ago, # ^ |   +1 I solved D on 2:14:58
•  » » » 4 weeks ago, # ^ |   0 Is your solution a Bruteforce ? What is its time complexity ?
•  » » » » 4 weeks ago, # ^ |   +3 Whenever I delete some index at most I recalculate for 2 value because things change just for this index's next and before indexes currently in the array so I recalculate them.We can delete at most N indexes. So total complexity is O(N) but I am also using set hence my solution is O(NlogN) but can improve to O(N)
•  » » » » » 4 weeks ago, # ^ |   0 Okay thank you ! Got it !
 » 4 weeks ago, # |   +99 I see that the blog is being downvoted. What was wrong with the problems? I've heard that in the statement of D it was unclear whether the pairs are ordered or unordered, but I don't know what else was the fault of authors.
•  » » 4 weeks ago, # ^ |   0 this is at least disrespectful to the author
•  » » 4 weeks ago, # ^ |   +6 D2B FSTs is the main reason I guess
•  » » 4 weeks ago, # ^ |   +47 My suspicion is that this is largely motivated by the first two Div 2 tasks--A is significantly simpler than past Div 2 A's, and there were a number of ways to attempt B that led to lots of nasty edge cases. That said, I thought the Div 1 set was pretty nicely balanced. It's perhaps a little unfortunate that the range of problems that matters most for the majority of contestants (B/C/D) leaned towards the DS side of things, with the ad hocs placed at A and E, but that doesn't seem like the end of the world to me, and neither B nor C required absurdly nasty implementation.Another plausible explanation is that there were a large number of FSTs. I see this as perhaps a more legitimate reason to downvote; FSTing is extremely frustrating and unfair, given that it represents a significant disadvantage over failing pretests in spite of the fact that the root cause of failing pretests and of FSTing is essentially the same (i.e., submitting a buggy solution), and consequentially, I think authors have an obligation to minimize the number of FSTs that occur.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -17 As far as I check all the problems either in div1/div2 had some people FSTed so I think that's the reason.
•  » » » 4 weeks ago, # ^ |   -23 Huh? That's actually great. For a long time cf pretests are going in the wrong way. People stopped even caring about their solutions after seeing that the pretests are passed, while they should carefully check their time, memory and time relative to other participants. Pretests are here to help you catch bugs, but you should always be aware of on WA/TLE/RE on systests and be ready to resubmit if your running time on pretests isn't good enough.Last times I've seen that after systests my running time sometimes decreases which means that most times all the strongest tests are included in the pretests, which is bad.
•  » » » » 4 weeks ago, # ^ |   +40 Isn't the point to construct as strong pretests as possible? I think pretests are here just to reduce the load on the judging servers, not to force participants to reread / test their solution after passing pretests.
•  » » » » » 3 weeks ago, # ^ |   +7 Actually I've never thought about pretests from this points of view, but probably this is the actual reason.Anyway, for me it always was another interesting feature of cf contests in comparison to other platforms, so I would've liked more tasks with weak pretests to make competition more interesting.
 » 4 weeks ago, # |   +2 Is the contest still rated? please, let me know.
 » 4 weeks ago, # | ← Rev. 2 →   +10 how n=1 is not in the pretest?
•  » » 3 weeks ago, # ^ |   0 it literally took me 1 minute to detect my error :(
 » 4 weeks ago, # |   +12 is CF-predictor working ??
•  » » 4 weeks ago, # ^ |   0 Nope. You can't visit other's ids. Maybe it is the case for the api as well. Cf tool must have stopped too i guess.
•  » » » 4 weeks ago, # ^ |   0 any reason for that
•  » » » » 4 weeks ago, # ^ |   0 I am not exactly sure how cf-predictor works but it should have to fetch some data for your account. Since visiting ids was blocked by cf till some moments ago, cf-predictor was not working. It should be working now though.
 » 4 weeks ago, # |   0 Editorial?
 » 4 weeks ago, # |   0 What should be output for this TC in Div2B 3 4 2 0
•  » » 4 weeks ago, # ^ |   +1 -1
•  » » » 4 weeks ago, # ^ |   0 Is this same case ? 3 829404334 757138662 684872990
•  » » » » 4 weeks ago, # ^ |   0 nevermind i was wrong if n=3 4 2 0 should give 2 4
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 c should be less than mEdit — if opp case then arr[1]!=m
•  » » » » » » 4 weeks ago, # ^ |   0 actually .. my first comment was right it shoud give -1 as for the second case it should give -1 too
•  » » » » » » » 4 weeks ago, # ^ |   0 see TC 2 of div2B it is showing 0
•  » » 4 weeks ago, # ^ |   +1 It should be 0. c = m-2 and m can be very large
•  » » » 4 weeks ago, # ^ |   0 ok thanks