Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### isaf27's blog

By isaf27, 9 months ago, translation, ,

Hello, Codeforces!

I'm glad to invite you to Codeforces Round #559 (Div. 1) and Codeforces Round #559 (Div. 2), which will be held on May/12/2019 17:35 (Moscow time). The round will be rated for both divisions (I hope).

All problems were written and prepared by me. Thanks to aleks5d, TLE, sunset, Sooke, Peltorator for testing problems and good advice, 300iq for round coordination and help with preparation and MikeMirzayanov for great systems Codeforces and Polygon.

You will be given 6 problems in both divisions and 2 hours to solve them. Please, read all the problems. Good luck, have fun and I wish everyone high ratings!

The scoring distribution will be announced closer to the beginning of the round.

UPD

The contest finished, contgratulations to the winners:

Div1:

Div2:

Editorial

• +233

 » 9 months ago, # | ← Rev. 4 →   +11 Orz Sooke, wish I will be red too!
•  » » 9 months ago, # ^ |   -46 Orz
•  » » 9 months ago, # ^ |   -24 memset0 can AK IOI!
 » 9 months ago, # |   -35 Orz Sooke
 » 9 months ago, # |   +104 I'm not Peltorator, I'm Isaf27_loves_me. Fix it, please.
•  » » 9 months ago, # ^ |   +137 No, the information in your nick is false.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +55 I don't really care. Orz isaf27
•  » » » » 9 months ago, # ^ | ← Rev. 3 →   -78
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   -49 Actually, I have just found out that orz iz not just a meme word that can be added to anything with no actual sense, it's a Japanese word meaning frustration: https://www.urbandictionary.com/define.php?term=orzSo don't repeat my mistakes and don't orz anything you want!
•  » » » » » » 9 months ago, # ^ |   +170 you are behaving like a granny who tries to use the Internet
•  » » » 9 months ago, # ^ |   +35 Here we see a Tsundere in his natural habitat﻿
 » 9 months ago, # |   +24 Please,No MathForces !!!
•  » » 9 months ago, # ^ | ← Rev. 4 →   -37 But why? Last Mathforces was quite good!
 » 9 months ago, # |   -41 UPD1: The round is carried over for 20 minutes.UPD2: The round is carried over for 15 minutes.UPD3: The round will be unrated.People who has +200: Why do I participate?
 » 9 months ago, # | ← Rev. 2 →   -99 Okay! Thank u for your unreasonable voting :V
•  » » 9 months ago, # ^ |   0 I guess he will consider, if you give him some RAMADAN special biryani xD
•  » » » 9 months ago, # ^ |   -34 FYI Ramadan is not about eating but fasting. By the way, they don't eat Biryani in Russia :V
•  » » » » 9 months ago, # ^ |   0 Hahaha,can't see your message at all
•  » » 9 months ago, # ^ |   +74 It's hard if not impossible to consider the prayer time. Because the prayer time in every country are not same and people from all over the world participate here. And every minute is a prayer time in somewhere in the world. So when do you suggest to schedule the contest?Moreover, this platform have people from many religion, culture and region. The platform must not run by considering any religion, culture or region. The platform should be secularist and International.
•  » » 9 months ago, # ^ |   0 Obviously, every hour there is muslims have fast breaking in Ramadan
 » 9 months ago, # | ← Rev. 2 →   +4 I like the weekend contest, thank you isaf27.
 » 9 months ago, # | ← Rev. 3 →   +27 I hope this will be IMO contest from isaf27, not 2 problems like "write a segment tree" and 4 problems like "write a link-cut tree with operations ADD, FIND_SUM and REVERSE_ALL_BITS in $ne^{\sqrt{\log n}}$ time and $n\log^{2.39}n$ memory".
•  » » 9 months ago, # ^ |   +181 Hope is a good thing.
•  » » » 9 months ago, # ^ |   +40 maybe the best of things.
•  » » » » 9 months ago, # ^ |   +38 and no good thing ever dies.
•  » » » » » 8 months ago, # ^ |   0 Hope die the last)
•  » » 9 months ago, # ^ |   +59 I completely agree with you. Hope there will be some problems like find the equation of Euler line $\dots$
•  » » » 9 months ago, # ^ |   -61 Actually, I gave the problem about Euler line to isaf27 and he didn't solve it because of its extremely high idea level, so I don't think we'll see it in the contest.
•  » » » » 9 months ago, # ^ |   +74 Please, don't discuss the problem from some contest in the future
•  » » » » » 9 months ago, # ^ |   -68 Yes, I hope nobody runs into this discussion and sees any ideas of problems that are to be used in the future.Blah-blah, blah, blah, so, isaf27, does your last statement mean that we can find the optimal length of twix in $\mathcal{O}(1)$ time per query?
•  » » » » » » 9 months ago, # ^ |   +10 We should find a formula dependent on the volume of Lipton. I can't answer your question now, it's too hard.
•  » » » » » » » 9 months ago, # ^ |   0 what's twix? what's the volume of Lipton? Could you give some links?
•  » » » » » » » » 9 months ago, # ^ |   +1 Never mind, local jokes :)
•  » » 9 months ago, # ^ |   -13 Have I misunderstood you? Do you want Mathforces?
 » 9 months ago, # | ← Rev. 2 →   +15 Smh, All red contest. Hoping it will be balanced.
 » 9 months ago, # |   +18 Sooke is our red sun!
 » 9 months ago, # |   -65 I guess there will be a massive drop in participation from India due to the finals of IPL. (Once in a year).
•  » » 9 months ago, # ^ |   +353 Fortunately it won't affect div1 much.
•  » » » 9 months ago, # ^ |   +29 Good one
•  » » » 9 months ago, # ^ |   0 nice one!!
•  » » 9 months ago, # ^ | ← Rev. 2 →   -15 [deleted]
 » 9 months ago, # |   -22 I'm not gonna participate because i have final exams and I'm not gonna study because i wanna participate and I'm not gonna participate because i have final exams Sad ..
 » 9 months ago, # |   +8 looking forward to Sooke 's contest!
•  » » 9 months ago, # ^ |   +42 This is not my contest. I just test these problems for the correctness.
•  » » » 9 months ago, # ^ |   +36 Will your profile picture change to megagnar when you're angry
•  » » » 9 months ago, # ^ |   +5 Maybe he is looking forward to the one in the future.
 » 9 months ago, # | ← Rev. 2 →   -41 Bad schedule for Man City & Liverpool fans! :p
•  » » 9 months ago, # ^ |   +26
•  » » 9 months ago, # ^ |   +11 good schedule for CSKA and Zenit fans
 » 9 months ago, # |   -33 Tanmay Bansal will give contest today
 » 9 months ago, # |   -27 help me pls :(
 » 9 months ago, # |   -8 Wish my rating will up up QAQ
 » 9 months ago, # | ← Rev. 6 →   +63 Am I the only one who is facing problem accessing the problems and submitting the solution? Each time I submit the solution I am getting the verdict "You have submitted the same code before" but in "my submission" tab I am not able see the submission :(It's almost half way and I am facing same problem now even! Can't submit my solution for A and B (or don't even know if they has been submitted successfully or not?) Doesn't matter which problem I am going to submit, I receive the same verdict all the time :(
 » 9 months ago, # |   +61 unrated? site was down for the first 30 minutes for some people
•  » » 9 months ago, # ^ |   +30 Maybe we can finally switch to using dynamic cloud providers instead of fixed hardware in the ITMO basement?
•  » » 9 months ago, # ^ |   -21 and Div2C was unclear for the 90 minutes for lot of people
 » 9 months ago, # |   +69 Why is it impossible to register on m1.codeforces.com? I tried to register 10 minutes before the contest but the main site was down so I couldn't. And I can't even read the problems if I'm not registered. :(
 » 9 months ago, # |   +101 I'm doubtful if the round should be rated. Quite a lot of people throughout the world experienced traffic issues. I think that absence of the score distribution in the round announcement post at this moment (45 minutes have passed) indicates the severity of the problem.Everyone knows that the problemsetters, the coordinators and the Codeforces Headquarters endeavored to deliver the best contest. The same applies to the current participants, who tried to solve the prepared problems despite of the mayhem. But is there any reason to persist a rated contest if the impact of the techincal issues is apparent, for the sake of sportsmanship? Unrated contest is not a total failure; there are things to gain and learn, and the efforts of the contest managers do linger.
•  » » 9 months ago, # ^ |   +78 Sorry about the technical issues, it seems some misconfiguration happened in process while I jump between servers. I work hard to diagnose and fix it.The notice about the micro-sites (green information bar in the header) appeared about 1 hour before the contest. Also I remind it in the official Telegram channel. Am I right that m1/m2/m3 work good without technical issues? I think it means if you follow recommendations you was able to read and solve the problems without any timeouts.
•  » » » 9 months ago, # ^ |   -23 Not everyone saw that notice. I tried to login 5 minutes before the contest starts and the site was already down.
•  » » » 9 months ago, # ^ |   +10 But i wasnt able to know scoring distribution, and i couldn't view standings.
•  » » » » 9 months ago, # ^ |   +20 Neither was anyone else, which at least is fair.
•  » » » 9 months ago, # ^ |   +56 m1/m2/m3 worked perfectly for me. It loaded almost instantly.
•  » » » 9 months ago, # ^ |   0 It was fine, i didn't know what to do the first 2 minutes but then it was fine just like a regular contest.
•  » » » 9 months ago, # ^ |   +5 Yes , light weight sites worked good ...i submitted 3 problems from there without any unnecessary delay. Thank You!
•  » » » 9 months ago, # ^ |   +10 You can't log in to m1/m2/m3 sites with a google account because of which I couldn't submit for the first 15 minutes.
 » 9 months ago, # | ← Rev. 4 →   +16 MikeMirzayanov crashed his scooter into a rack of servers,so site was down for 30 minutes .Is the round still rated?
 » 9 months ago, # |   +110 There is no reason to make the contest unrated. The technical issue was in the beginning of the contest. Everyone could use m1 m2 or m3.codeforces.com. Participants who didn't use those sites and therefore lost time could still decide not to submit and don't participate in the round. Submitting code means you could use the system well or you accepted that you lost time. Everyone who submitted code made the decision to participate in the rated contest.
•  » » 9 months ago, # ^ | ← Rev. 2 →   -14 .
•  » » » 9 months ago, # ^ |   +61 Main site was down at the start for less than 10 minutes. All the mirrors were still up. Rounds have been rated in more drastic cases, if I remember correctly. So please make this rated, even if the participant count was lower than usual because of technical issues.
•  » » » » 9 months ago, # ^ |   +13 Last week we got an unrated round because of weak pretests on problem A lol.
•  » » » » » 9 months ago, # ^ |   +17 That round being unrated was one of the worst disappointments I have ever faced
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +4 I agree. That contest was all right except problem A.
•  » » » » 9 months ago, # ^ |   0 for me the page didnt work normaly for like 45 min
•  » » » » » 9 months ago, # ^ |   0 That's unusual. I had no downtime on the mirrors and only like 10 minutes on main site.
•  » » » 9 months ago, # ^ |   +8 Neither did anyone else.
 » 9 months ago, # |   +17 The main problem was even though I tried to use m1/m2/m3, somehow I wasn't registered(though I was), so I had to wait for 20 minutes to register and then submit solutions to m1. I guess I'm not the only one, who was unregistered without knowing.
•  » » 9 months ago, # ^ |   -6 Then why didn't you register in advance? It is not that the site has been down for the whole time it has been able to register.
•  » » » 9 months ago, # ^ |   +12 I was registered in advance, but then system unregistered me, so I couldn't enter the contest on m1/m2/m3.
•  » » » » 9 months ago, # ^ |   +3 There are almost 24 hours that can register. When did you register?
 » 9 months ago, # |   +9 Someone posted the solution to div2 A in the blogs already lol.
 » 9 months ago, # |   +104 Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.
•  » » 9 months ago, # ^ |   +28 Thank you. I was sure that I saw this problem in some contest but couldn't remember the exact contest.
•  » » 9 months ago, # ^ |   +24 The bounds is not important. I'm sure that almost people have the same solution for both.
 » 9 months ago, # | ← Rev. 3 →   +16 Good tasks, thanks!)
 » 9 months ago, # |   +12 TIL you can submit in the mini-sites. I just read the problems :/Doesn't matter much for me though since it took me so long to solve A that the servers were up when I was ready to submit
 » 9 months ago, # | ← Rev. 3 →   +54 Me: Reading the problem statement of Div 2 C made wild assumptions and passed for some reason
•  » » 9 months ago, # ^ |   +14 Can you please explain why it was so hard to understand? It got two clarifications and I could not understand why.
•  » » » 9 months ago, # ^ |   +21 The statement was confusing. The word "some" was somewhat misleading. I would have separated the key sentence into two sentences as follows: "Boy i gave at least b_i sweets to each girl. Girl j received at most g_j sweets from each boy."
•  » » » 9 months ago, # ^ |   0 In theory everything was written in the statement, but for example I thought that each boy has to give at least $b_i$ sweets each girl and I couldn't get it right without asking a question to first sample.
•  » » » 9 months ago, # ^ | ← Rev. 4 →   0 I thought bi is the upper limit for the number of candies the girls received from each boy. Then I figured out that is wrong, so i thought it means the upper limit for the total number of candies receivedActually the main reason for the problem should be my poor English...There isn’t any actual problem about the statement, everything should be alright after reading the samples I guess
 » 9 months ago, # |   0 How to solve C?
•  » » 9 months ago, # ^ |   0 Hint: Solve the problem assuming there are no missing values, after that it will be easy to extend it to the general case.
•  » » 9 months ago, # ^ |   -31 You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. 54046042
•  » » » 9 months ago, # ^ |   0 got it
•  » » » 9 months ago, # ^ |   +1 You uploaded Div2 C code, but T1duS399 asked Div1 C.
•  » » » » 9 months ago, # ^ |   +1 I already got it. I forgot that there is a div1 in the same with div2
•  » » 9 months ago, # ^ | ← Rev. 3 →   -8 Build a graph for relative order of p : if p[i] < p[j], there is an edge from i to jIf there is a valid topsort order, there is the answerWe build an edge from i+1..next[i]-1 to i and an edge from i to next[i].However, there are O(n^2) edges.To solve the problem, use segment tree to represent a range of nodes build two edges from [l..r] to [l..mid] and [mid+1..r] so there will only be O(n) number of nodes (not more than 4*n)EDIT: Hope I won't get TLE on systest :CEDIT2: Accepted :D
•  » » » 9 months ago, # ^ |   +13 I think there is an easier solution. For any -1 in the input, use i+1 (point them at the next node); this should not change the existence of a solution. As you read the nodes, keep track of the previous nodes that point at following nodes with a stack, and make sure they nest properly. Finally, sort the nodes using (next_i, -i) and assign values according to this order. I think this works . . .
•  » » » 9 months ago, # ^ |   0 It is sufficient to add edges of two types: i to next[i] the first index j to the left of i such that next[j] > i (if it exists), where we add an edge from j to i So there are only O(n) edges anyway. (Code)
•  » » 9 months ago, # ^ |   0 Couldn't get an AC in the contest. I used a greedy algorithm.Let us try filling the array smallest to largest.We can observe that if next[i] = j, than for any x, i < x < j , next[i] <= j.Also, permutation[x] < permutation[i] < permutation[j] . We can just fill the subarray (i+1 to j-1) first, and then fill i.We can then go on working on array starting from j. int small = 1, flg = 0; void solve(int st, int en) { if(st > en || flg) return; if(nex[st] == -1) { ans[st] = small++; solve(st+1, en); return; } if((nex[st] > (en + 1)) || (nex[st] <= st)) { flg = 1; // determines invalid case return; } solve(st+1, nex[st]-1); ans[st] = small++; solve(nex[st],en); } 
 » 9 months ago, # |   -65 How about making the round rated for only positive rating changed users? (This happened previously in codeforce)
•  » » 9 months ago, # ^ |   0 When? I think this would cause huge inflation.
•  » » 9 months ago, # ^ |   +18 That would lead to rating inflation.
•  » » 9 months ago, # ^ |   +5 This has never happened before
•  » » 9 months ago, # ^ |   0 Why? The only upside is that it would make everyone "feel good".
 » 9 months ago, # |   +16 Div 2E seems to be easier than Div 2D.
 » 9 months ago, # |   +3 How to solve Div2D?
•  » » 9 months ago, # ^ |   +16 Try to write a brute force and observe patterns. ;)The key is the number z = (n — k) / 2.You build a string with [z zeros, a one, z zeros, a one, ...]e.g. n = 14, k = 10, 00100100100100
•  » » 9 months ago, # ^ | ← Rev. 2 →   +7 You can repeat the pattern 0000...001 over and over up to n length. The number of zeros in the repeating pattern is (n-k)/2.I am actually surprised why there has not been more solves. Makes me doubt the solution
•  » » » 9 months ago, # ^ |   +4 I couldn't figure out this pattern by myself. What was the idea behind it to came up with this idea?
•  » » » » 9 months ago, # ^ |   +14 Tried some things with pen and paper, observed the pattern, coded a brute force solution and observation proved valid for all n upto 20. So, went for it : P
•  » » » 9 months ago, # ^ |   0 Even in the examples, u can see the patterns...
•  » » 9 months ago, # ^ | ← Rev. 3 →   +8 Say you are given $n$ and $k$. Set $d = \frac{n-k}{2}$, $l0 = floor(\frac{d+2}{2})$, $l1 = floor(\frac{d+1}{2})$. Now the string of $l0$ zeroes, $l1$ ones, repeat works. The special case is $k=1$, in which case you can only have one 0 or 1, and can use 0111... as your string.This works, since the string is cyclic with length $l0 + l1 = d+1$, and the start-point x (zero-indexed) of some substring mod $d+1$ uniquely determines its content, and the content for all residues is different. Therefore WLOG $x \leq d$. Let $s$ be the length of the substring. We must also have $x + s + (d+1) > n$, since otherwise the string occurs again $d+1$  characters later. So now we have: $s \geq n - x - d \geq n - 2d = n - (n-k) = k$Completing the proof.Submission: 54040228 (function count is unused, I just used it to test the code)
•  » » » 9 months ago, # ^ |   +8 Is the formula $n + 1 - 2 \cdot (\frac{n-k}{2} + 1) = n + 1 - (n - k + 2)$?
•  » » » » 9 months ago, # ^ |   0 You're right, the inequality should have been strict. Fixed.
•  » » » » » 9 months ago, # ^ |   0 Besides, do we really need to treat k=1 as a special case? I just use the overall implementation and i still got an accepted.
 » 9 months ago, # |   +4 I can not access the site util the contest had passed 20 minutes. Stabilize the main site plz.
•  » » 9 months ago, # ^ |   -8 and problems need clarification too!
•  » » 9 months ago, # ^ |   0 Smh, the issue has been already raised almost 10 times before your comment.
 » 9 months ago, # |   0 How to solve C?
•  » » 9 months ago, # ^ |   -17 I repeat my comment, but anyway : "You can see my greedy solution (but i cannot prove it). Answer my comment if you have questions. " 54046042
•  » » » 9 months ago, # ^ |   0 Maybe he means Div1 ???
•  » » » 9 months ago, # ^ |   +4 If you see a purple or a red guy asking for C, its probably not Div2 C that he's asking for.
•  » » 9 months ago, # ^ |   0 make $nxt_i = i + 1$ for each $i$ $(nxt_i = -1)$
 » 9 months ago, # | ← Rev. 2 →   0 When I asked why Div2C sample3 's note said the first boy presented 1,2,1 sweets instead of 1,1,2 it just replied me to read the global announcement :((The problem has been fixed without announcement during the content.)
 » 9 months ago, # |   +24 How to solve div1D?
•  » » 9 months ago, # ^ |   0 Problem D is Windy Path (Problem L) from the 2016 ACM-ICPC Pacific Northwest Regional, with slightly higher bounds.
•  » » 9 months ago, # ^ |   0 I think traversing convex hull and recalculating it after removing a point each time should do the trick.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +35 Lemma: Given any point $P$ on the convex hull, there always exists a solution that starts at $P$.Proof: We use induction (with the algorithm below).Clearly we can do it for $N = 2$. For general $N$, let $X$ and $Y$ be the points adjacent to $P$ on the convex hull. Because the entire set of points lie on one side of both the lines $\overleftrightarrow{PX}$ and $\overleftrightarrow{PY}$, we choose $X$ to be our next point if the first direction is to turn left, otherwise $Y$ if we want to turn right. Then we can remove $P$ from the set of points and continue by induction on $N - 1$ points, as $X$ and $Y$ will still remain on the convex hull after removing a point.Time complexity is $O(N^2)$. You don't need to find the entire hull; you can find $X$ and $Y$ in linear time using one step of gift wrapping.
 » 9 months ago, # |   +161
 » 9 months ago, # |   0 If I make 2 submissions for a question, both correct.. will the first solution be checked?
•  » » 9 months ago, # ^ |   0 I think olny the last one accepted in pre test.
•  » » 9 months ago, # ^ |   0 the first sumbissions are skipped, only the last one is valid.
 » 9 months ago, # |   -29 Very Unfair Contest. First Server problem,then Div 2 C not clear and also announcement were not upto the mark.It should be unrated.
•  » » 9 months ago, # ^ |   +37 I did terribly, but I still think it was a good contest. Although CF going down all the time is really annoying, there are m1/m2/m3 sites that work pretty consistently. Also div2c/div1a wasn't that unclear. They explained anything that might be confusing under the samples.
•  » » 9 months ago, # ^ |   0 Learn Russian :)
•  » » 9 months ago, # ^ |   -7 div2c was rather clearbut there are some noobs who cant read
•  » » » 9 months ago, # ^ |   0 It seems that the English version was more ambiguous than the Russian version.
•  » » » 9 months ago, # ^ |   +6 Hello, non-master
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +2 hello, geylord
 » 9 months ago, # |   +5 I am a newbie. How to solve Problem(B) Div 2.?
•  » » 9 months ago, # ^ |   0 https://codeforces.com/contest/1159/submission/54032077A tutorial will probably come in a few days describing exactly how to solve it, but if you can understand this code, then that's all you need. I personally tried a lot of greedy solutions and I would have never thought about this one. I don't even know why it works to be honest. Anybody have an explanation ?
•  » » 9 months ago, # ^ | ← Rev. 4 →   0 This is how I solved it. First of all, notice that we can rewrite the $k$-extension condition for a pair $(i,j)$ to the following: $k \leq \frac{\min(a_i,a_j)}{|i-j|}$The important observation is that the right hand side of that equation does not depend on $k$, so for every pair we have an upper bound to the value of $k$. Since this must hold for every pair $(i,j)$ such that $1 \leq i,j \leq n$ and $i \neq j$, we conclude that an upper bound for $k$ is $\underset{ 1\leq i\neq j \leq n }{\min} \frac{\min(a_i,a_j) }{|i-j|}$, since $k$ should be less than all those upper-bounds in order to be a $k$-extension. Moreover, by definition we have that all $k$ that are less or equal than that number work. By choosing the biggest $k$ as possible (which is the smallest upper bound) we have our answer. Now that we know what the answer is, the remaining question is how to calculate it efficiently. An idea to do this is to find a small amount of candidates for those pairs and calculate the upper bound only for those pairs. To do this you can prove that the pair that attains such minimum must necessarily be paired with either $a_1$ or $a_n$, this gives us only $2n$ candidates and we can simply try all of them.
 » 9 months ago, # | ← Rev. 3 →   -23 1159D - Минимальная уникальная подстрокаWhat is wrong??54043161 int solve(int n,int k){ lint p=0; if(n==k){ rep(n)cout<<'1'; return 0; } rep(k/2+1)cout<<"10",p+=2; while(p
•  » » 9 months ago, # ^ |   +3 Maybe I am wrong as I am from Phone, but it seems for 9, 5 it would give 101010111, which has shortest unique 3
•  » » » 9 months ago, # ^ |   0 omg its true... Thank you for the information!
•  » » 9 months ago, # ^ |   +3 Had the same idea, but realized it would fail for larger n values...
•  » » 9 months ago, # ^ |   0 I think that in the future, you should preview your question before posting it, it is badly formatted.
 » 9 months ago, # |   0
 » 9 months ago, # |   +35
 » 9 months ago, # |   +6 You think the geniuses are those who prove the Fermat's theorem? No, the geniuses are those, who made div2 D )))
 » 9 months ago, # |   +15 This round in a nutshell : "I'm just gonna make some crazy assumptions and hope they pass the tests." Also, the difference between C and D was too much.
•  » » 9 months ago, # ^ |   0 D was not that difficult. If you can brute force, you will easily find the pattern.However, if you are talking about clarity in problem specification, I agree 100%
•  » » » 9 months ago, # ^ |   +14 You've got a good point, perhaps I_Didn't_Do_Enough_Things_For_WA
 » 9 months ago, # |   0 How to solve div1C pls?... :)
•  » » 9 months ago, # ^ |   +3 In this task we just need to check, that topsorted-order of vertices is correct.
 » 9 months ago, # |   +3 Can we see the tests pls?
 » 9 months ago, # |   0 Hello，I got some questions with problem C (Div2)for 2 10 01I think the answer should be -1.right?I missed this situation during the contest.And I think my solution 54038745 will be WA after system test，but it's still accepted Σ( ￣□￣||).
•  » » 9 months ago, # ^ |   +3 The minimum value of N and M is 2.
•  » » » 9 months ago, # ^ |   0 thank you
•  » » » 9 months ago, # ^ |   +8 That single constraint snatched all my hacks
•  » » 9 months ago, # ^ |   0 I think that case is not valid, n and m must be at least 2
•  » » » 9 months ago, # ^ |   0 thank you
 » 9 months ago, # |   0 How to solve Problem B?
•  » » 9 months ago, # ^ |   0 for every item in the array, the value of k for that specific item = value/distance, where distance is maximum distance possible i.e either from 1st or from the nth item, now from all these values of k the minimum one is the answer. Pseudo code : i from 1 to n k=min(k,a[i]/max(n-i,i-1) print(k)
•  » » » 9 months ago, # ^ |   0 I am not getting why we are taking individual values min(k, a[i]/max(n-i, i-1) ? aren't we supposed to consider the every pair? i.e.min(k, min(a[i], a[j])/|i-j|) ?
•  » » » » 9 months ago, # ^ |   0 We can take individual values because in min(a[i],a[j]) if we take individual values it won't affect our answer in the end, because even if we calculated for the bigger value also, when taking min(k,a[i]/dist) that value will automatically be eliminated .
 » 9 months ago, # |   0 Can you tell me why my submission to Div.1B got WA on test 22? Test 22 is $(n, k) = (5783, 2359)$, and my output is '0{$1067$}10{$2357$}10{$2357$}' (0{$n$} means $n$ zeros) Judge says minimal unique substring for my output is 1069.
•  » » 9 months ago, # ^ | ← Rev. 5 →   0 Edit nvm I read it wrongas tfg said 0{1068}1 i completely overlooked that mybad
•  » » » 9 months ago, # ^ |   0 For t="0{$1067$}", I think we have at least two $l$s in problem statement, $l=1$ and $l=1069$...?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 0{1067}10 appears more than once
•  » » 9 months ago, # ^ |   0 0{1068}1 happens only once.
•  » » » 9 months ago, # ^ |   0 Thats it
 » 9 months ago, # | ← Rev. 3 →   0 In Div2E/Div1C.Does anybody know why this 54049263 gives MLE? When I change stack to set I get AC in this 54047364 My Approach: Construct a directed graph where edge (u,v) means a[u] < a[v] and then do topological sort on that graph. The way I construct it is if nxt[i] = j that means there is an edge(i, j), also there is an edge between all elements [i+1, j-1] and i since all of them must be less than i. I only keep track of the least previous element. Here's an example where ix, jx means nxt[ix] = jx:i1 i2 i3 ... j3 j2 j1. Edges are (i1, j1), (i2, j2), (i3, j3), (i2, i1), (i3, i2). I don't add (i3, i1) since it's redundant.In a case like i1 .. i2 .. j1 .. j2 In the MLE submission I exit immediately and say that it's impossible. In the AC submission with set I let the topological sort handle it.
•  » » 9 months ago, # ^ |   +3 Change vector> Pop(n); to vector>> Pop(n); and MLE should be gone. This is happening because when you pop elements from the stack, the underlying container (deque is the default) is not actually freeing up space. deque will hold the allocated space during the entire runtime of the program. So just change the underlying container to list, which on the other hand frees up space when an element is removed from it. Now you are maintaining $N$ stacks which can have upto $N$ elements, thus requiring too much space if space is not freed when elements are popped off the stacks. list will free-up space and your program wouldn't run into MLE. Also, set will free-up space as soon as your erase from it. Thus your second program doesn't run into MLE.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Thank you so much for the answer! I've changed the internal container fromvector > Pop(n) to vector > > once and to vector > > once and both got AC without changing the other stack to set.However I've got 2 questions. 1- Shouldn't my total amortized memory be N not N^2? at each iteration I do at most one push_back in some deque in Pop[i]? even if I don't free up memory shouldn't that be fine because the total number of elements in all N deques will still be N? specially since AC solution passes in 27~35KB so I'm not on the edge of running out of memory. 2- Why does changing the underlying container to vector still pass although the vector doesn't shrink the capacity with the pop_back() calls either? I know that deque requires more memory than vector but is it really that much more? Please note that I've only changed the underlying container in Pop. I haven't changed the other stack to set, neither have I changed its underlying container either. I've only made changes to vector > Pop(n).Here's the latest 2 submissions: 54094520 , 54094473
 » 9 months ago, # |   +22 OMG finally purple! Gonna try not to lose this next contest lmao
•  » » 9 months ago, # ^ |   0 and 2019 congrats man!
 » 9 months ago, # |   0 Thank you for your contest !!!!!!!!!!!!!!! I very love it
 » 9 months ago, # | ← Rev. 2 →   +1 Please translate the tutorial to English isaf27, can't understand google translation of 1159D - Минимальная уникальная подстрока's solution
 » 9 months ago, # |   0 I tried solving Div2 E with a solution of complexity O(t*nlogn) and am getting a TLE. Can anyone suggest why? Submission link — https://codeforces.com/contest/1158/submission/54055728.I basically replace all -1's with a positive value in the following manner ~~~~~ int o = n+1; for(j = n-1; j>=0; j--) { if(inp[j]>0) o = inp[j]; else inp[j]=o; v.push_back(make_pair(inp[j],o)); } ~~~~~ I then sort this v vector and construct the answer array by using the values in the inp array. Finally, for any element if according to the input array, the first element greater than the current element(stored using a stack and array) is at an index before than that in the input array, then the answer is -1. The sorting step might be the time consuming step but I don't get how I am violating the time limit.
•  » » 9 months ago, # ^ |   0 I think your problem might be this line: `while(z
 » 9 months ago, # |   0 Can someone help me with Div2-D ? Not able to figure out the greedy approach.
 » 9 months ago, # |   0 English editorial anywhere?