### Ormlis's blog

By Ormlis, history, 13 days ago, translation,

Hello!

Right now happens the first tour of the Open Olympiad in Informatics, and tomorrow will be the second one. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852).

Open Olympiad consists of the most interesting and hard problems that are proposed by a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen on Mar/09/2023 12:35 (Moscow time) and will be based on both days of the Olympiad. Note the unusual time of the round. Each division will have 7 problems and 3 hours to solve them.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems of this competition were prepared by Mangooste, Artyom123, teraqqq, Ziware, vaaven, Tikhon228, Ormlis, Kirill22, ViktorSM, isaf27, DebNatkh and DishonoredRighteous guided by grphil and Helen Andreeva.

Thanks to Aleks5d for the round coordination, statement translation and preparation of problems for the second division, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD1: Please note the number of problems and the duration of the round have been increased for each of the divisions.

UPD2: Great thanks to the testers of the round: BucketPotato, valeriu, 4qqqq, Aaeria, FedeNQ, olya.masaeva! As well as the testers of the main Olympiad: Siberian, Maksim1744, antony191, Kapt, Pechalka, alexxela12345, Be_dos, princebelkovetz, Jatana, KiruxaLight, cute_hater!

UPD3: Scoring distribution:

Div.2: 500 — 750 — 1250 — 1750 — 2000 — 2500 — 3500

Div.1: 500 — 1000 — 1250 — 1750 — 2500 — 3500 — 3500

UPD4: Editorial, we apologize for the delay:(

• -1032

 » 13 days ago, # |   +164 Waiting for Div. $0.5$, Div. $1.5$ round
•  » » 13 days ago, # ^ | ← Rev. 3 →   -32 /
•  » » » 12 days ago, # ^ |   +23 Worst Contest I Have Ever Seen!..
•  » » » » 12 days ago, # ^ |   -52 WORST CONTEST I HAVE EVER SEEN!..
•  » » » » » 12 days ago, # ^ |   -35 Worst Contest I Have Ever Seen!..
•  » » » » » » 12 days ago, # ^ |   -29 WORST Contest I Have Ever Seen!..
•  » » » » » » » 12 days ago, # ^ |   -24 WORST Contest I Have Ever Seen!..):):):):):):):
•  » » » » » » » » 12 days ago, # ^ |   -48 WORST Contest I Have Ever Seen!!!!!!
•  » » » » » » » » » 12 days ago, # ^ | ← Rev. 2 →   -17 Loved it
•  » » » » » » » » » 12 days ago, # ^ |   -56 WCIHES
•  » » » » » » » » » 12 days ago, # ^ |   -73 WORST Contest I Have Ever Seen! WORST Contest I Have Ever Seen! WORST Contest I Have Ever Seen!
•  » » » » 12 days ago, # ^ |   +5 That's why you're blue
•  » » » » » 12 days ago, # ^ |   +52 that's why you're color blind
•  » » » » » » 12 days ago, # ^ |   +1 that is why weirdly enough i was at peak rank performance during this contest
•  » » » » » » 12 days ago, # ^ |   -29 That's why you're blind
•  » » » 12 days ago, # ^ |   0 Why the round is showing unrated???
•  » » » » 12 days ago, # ^ |   0 I'm afraid it'll be unrated for you
•  » » » » » 12 days ago, # ^ |   0 why
•  » » » » » » 12 days ago, # ^ |   0 you'll see
•  » » » » » » » 12 days ago, # ^ |   0 but what is wrong with today's round
•  » » » » » » » » 12 days ago, # ^ |   0 nothing's wrong
 » 13 days ago, # |   +118 Finally a new round after 5 days :)
•  » » 12 days ago, # ^ |   +8 LoL now we got more depressed because of this round!
 » 13 days ago, # |   +64 Why the cat in Kirill22's profile is looking sad? ⚫⁔⚫
 » 13 days ago, # | ← Rev. 5 →   -24 Good luck guys :) ♡
 » 13 days ago, # |   +14 I really love the contests you hold.Sadly, this is the second time I can't participate because of the time of the contest
•  » » 12 days ago, # ^ |   0 Why the round is showing unrated
•  » » » 12 days ago, # ^ |   0 where?
 » 13 days ago, # |   -10 the round will probably be heavy on math problems
 » 13 days ago, # |   -74 Please, change the time. Unusual for weekdays.
•  » » 12 days ago, # ^ |   0 Usual for weekdays, but the time is good because not 22:35 :)(But the problems...)
 » 13 days ago, # | ← Rev. 2 →   +31 make 2A easy pls, so you don't scare participants away. The timing already reduced the amount of participants, and you wouldn't want to reduce that further (
•  » » 12 days ago, # ^ |   +2 bruh!
•  » » 12 days ago, # ^ |   +16 They got scared :(
 » 13 days ago, # |   -71 I am still relatively new, why are there so many contests on weekdays? Feel like Leetcode does this so much better (2 contests 12 hours apart from each other on weekends).
 » 13 days ago, # |   +6 Timings for India are just after lunch. Perfect.
•  » » 12 days ago, # ^ |   +30 You seem to be in Australia though.
•  » » 11 days ago, # ^ |   0 After lunch if you manage not to sleep in the contest then it's perfect XD. And yes summer days another catalyst for sleep during afternoon.
 » 13 days ago, # |   +12 So goooood time don't need to stay up late
•  » » 12 days ago, # ^ |   0 hello ，lampland
•  » » » 12 days ago, # ^ |   +8 Hi， Duck
•  » » » » 12 days ago, # ^ |   +1 What is duck , i guess you are 骂 me . QWQ
•  » » » » » 12 days ago, # ^ |   +3 a letter for a letter lol
•  » » » » » » 12 days ago, # ^ |   0 oo,I understand it , my english is a little poor.lol
 » 13 days ago, # |   +154 I'll be taking this contest on a plane... Hopefully it's my highest placement ever.
•  » » 13 days ago, # ^ |   +8 good luck!
 » 13 days ago, # |   0 Best of luck everyone
 » 13 days ago, # | ← Rev. 2 →   0 Best of luck to all!
 » 13 days ago, # |   +9 Just noticed it is 3 hours long contest.
 » 13 days ago, # |   -56 Looking forward to my first Div.1 contest on Codeforces. Hope it be good!
•  » » 12 days ago, # ^ |   -56 Now I am back to Div.2. Thanks a lot. :(
 » 13 days ago, # | ← Rev. 2 →   0 Best luck to all wish you all gain a good rating ;)
 » 12 days ago, # | ← Rev. 2 →   0 Perfect time for Asian region. It's 1801th contest in CF. Great!
 » 12 days ago, # |   +99 Ouch, I was looking forward to the contest but will skip the round because of the increased duration :( We need shorter rounds, they are more fun!
•  » » 12 days ago, # ^ |   -67 Increase stamina bro xD
 » 12 days ago, # |   +29 It would be nice if duration change is not announced last minute.
 » 12 days ago, # |   +44 Just when did it become 3-hours-and-7-problems instead of 2-hours-and-6-problems?Really guys, increased duration in a non-standard time slot announced in the last minute is quite some combo :( .
•  » » 12 days ago, # ^ |   +12 The announcement letter, 14 hours ago, still says "2 hours duration".
•  » » 12 days ago, # ^ |   +5 longer round because multiple harder problems time slot related to the olympiad it's mirroring the announcement was late but I saw it scheduled for around a week already
 » 12 days ago, # |   +59 Task D1G, the very first line of the statements: "Philip is very fond of tasks on the lines."Google translate, is it you? :D
 » 12 days ago, # |   +80 I'm from future, this contest is FST, and I will failed main test in problem 1801C
•  » » 12 days ago, # ^ |   +3 How were you so sure that you will get FST on 1801C?
•  » » » 12 days ago, # ^ |   +2 Because I'm YugiHacker
 » 12 days ago, # |   -8 Thanks for great contest, i think a lot of people get possitive rank:)
•  » » 12 days ago, # ^ |   0 The round is showing unrated bruh!!!
•  » » » 12 days ago, # ^ |   0 it takes time for the rating to change... 24+ hours
 » 12 days ago, # |   +9 Div2B is a terrible problem
•  » » 12 days ago, # ^ |   +12 Terrible problem description.
•  » » 12 days ago, # ^ |   0 It's nice. The statement sucks
•  » » » 12 days ago, # ^ |   0 What's nice about it?
•  » » » » 12 days ago, # ^ |   +3 Well not really nice, but it isn't terrible either. It's an average problem
 » 12 days ago, # |   +11 I will never take part in div1 again.
•  » » 12 days ago, # ^ |   0 lol
 » 12 days ago, # |   +11 Very hard contest
 » 12 days ago, # |   +22 div2 C is very very annoying (╯°□°)╯︵ ┻━┻
•  » » 12 days ago, # ^ |   +4 It's annoying until you reach the insight: treat columns and rows separately. You can use for example first 10 bits to encode the row and the last 10 bits to encode the column. The solution is basically 1 line a[i][j] = ((i<<10) + j). Also, writing a checker to validate solutions was simple and very helpful for me.
•  » » » 12 days ago, # ^ | ← Rev. 3 →   0 [spoiler] https://codeforces.com/contest/1802/submission/196648450 [/spoiler] can u please tell me error in this approach I have almost used same logica as urs
•  » » » » 12 days ago, # ^ |   0 Just validate your answers. See my solution (auto Check).196626502
• »
»
11 days ago, # ^ |
Rev. 2   0

Until you notice the pattern in 1st and 3rd testcase.

Set a[0][0]=548 and traverse over rows and columns separately and proceed like below.

Code
 » 12 days ago, # | ← Rev. 2 →   +5 D was out of mind .. don't know how it crossed 1200+ submissions
•  » » 12 days ago, # ^ |   +1 Idk, it was pretty standard. If you have two things, sort by the first one, iterate over it in ascending order and select the second in a proper way using some data structure (in this case just [multi]set).
 » 12 days ago, # |   0 Why fixing a maximum does not work in D?
•  » » 12 days ago, # ^ |   0 It kinda works actually. But you need to iterate over all possible maximums (for A).
•  » » » 12 days ago, # ^ |   +20 Sad u and me both got FSTed. Still a little smile to get FSTed on test 69.
•  » » » » 12 days ago, # ^ |   +2 I don't even have this, mine is FST 70 :(
•  » » » » » 12 days ago, # ^ |   0 I got an FST at 71 :( Probably the dumbest mistake I could have ever made. I don't know how the hell it passed 70 other test cases.
•  » » » » » » 12 days ago, # ^ |   0 what was your mistake? im stuck at 71 test
•  » » 12 days ago, # ^ |   0 It works ig, U need to sort first element and iterate over first and check best for each first using a multiset.
 » 12 days ago, # |   0 In D, do we need to use binary search on answer ?
•  » » 12 days ago, # ^ |   +9 No
 » 12 days ago, # |   +60 Oh no... I didn't receive a notification that my solution in C was hacked, and I didn't notice it until the contest ended ;(
 » 12 days ago, # | ← Rev. 8 →   +53 First time solved div1 A-D (div2 C-F) in contests. I've tried a dp solution for F but got WA on pretest 15. Hoping for no FST and positive delta this time!D1A(D2C): Let's solve a stronger version of the problem: Build a matrix A with size (1<R, we must put b[i] in s2, so m2>=suf[R+1]. If suf[R+1]>=m1, then when m1=a[L], all gift combinations will have abs(m1-m2)>=suf[R+1]-m1. Otherwise, we can add some value b[i] to s2 for i1, we can also add b[i] for L<=i<=R) Therefore, we can use a ordered set to maintain candidate values for m2, and use binary search to find the nearest to m1.D1C(D2E): DP. First we can remove useless elements in every albums and make them strictly-increasing. Then we can let dp[i] be the maximum length of all possible strictly-increasing coolness subsequences in which the maximum value is no more than i. By checking every albums with maximum coolness i, if there's a song with coolness j, and there are k songs with coolness >=j in this album, we can get dp[i]>=dp[j-1]+k.D1D(D2F): First because n<=800, we can calculate dist[i][j] by dijkstra for every pairs (i, j), and assume there is direct edge (i, j) if i can reach j. Then we can solve by greedy: In any optimal solution, assume the amount of coins we get by performance is w1, w2, w3..., it must be a non-decreasing sequence. So we can sort cities by w[i] (and discard cities with w[i]
•  » » 12 days ago, # ^ |   +1 Hey can you please tell how did you solved Div2 D ?
•  » » 12 days ago, # ^ | ← Rev. 3 →   +8 YocyCraft: finnaly +ve delta in a div1 contestDiv1B: hold my beer
 » 12 days ago, # |   +38 How to solve Div1D?
•  » » 12 days ago, # ^ |   +6 SpoilerMain idea is that you can "retroactively" perform in a city that you've already been to. You should choose the one with the most profit.Create $n^2$ nodes, label each with an ordered pair $(i, j)$, meaning "you are at node $i$, and among the nodes you've been to, the one with the most profit is node $j$". If you want to move from node $(i_1, j_1)$ to $(i_2, j_2)$, and you don't have enough money, add a performance at $j_1$ until you have enough. Then dijkstra should work, with the distance being number of performances, and ties broken by number of coins.
•  » » » 12 days ago, # ^ |   +3 Hey, if possible, can you please have a look at my this submission https://codeforces.com/contest/1802/submission/196657563, I did the exact same thing which you are telling but got TLE.
•  » » » » 12 days ago, # ^ |   0 The greater<> comparator is prioritizing the least number of performances first, then the least number of coins (it should be the greatest number of coins). You can fix it by inserting negative values for coins on the priority queue.AC submission
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   +3 Hi, thanks for your reply. Silly mistake :( got ac now.But I still have a doubt: why was it giving tle, basically if I am preferring lesser number of coins (with that mistake) then why would it give TLE and when I prefer more coins then it's within the TL. Update: got the reason that actually, after a (i,j) pair is popped out of the priorioty queue, after that if we get more number of coins possibility with the same number of performances then we will again push it into the queue and it will again be processed. So tle.
•  » » » 12 days ago, # ^ |   0 Ahh that makes so much sense. Thank you.
•  » » » 12 days ago, # ^ |   0 Why is it always optimal for a node to choose a pair with the least amount of performances?
•  » » » » 12 days ago, # ^ |   0 Because in an optimal strategy, the cities you perform must have increasing profits (if you perform in a city with less profit than some city $C$ you have been, why not do the performance in $C$ instead).So if you perform in a later city you can gain more with each performance, and you should try your best to "delay" the performances to a later city. So the least amount of performances is always optimal.
•  » » » » » 12 days ago, # ^ |   0 I tried to create a counterexample, but eventually it helped me to understand your reply. Thanks!
 » 12 days ago, # |   +2 How to solve Div 2. C ?? Any hint?
•  » » 12 days ago, # ^ |   0 Look at the test cases and observe diff between a[I][j] and a[i-2][j]You will get a hint
•  » » 12 days ago, # ^ |   0 make every 2*2 block xorsum equals zero
•  » » » 12 days ago, # ^ |   0 I tried this but didn't got how to do it. Can you explain your solution?
•  » » » » 12 days ago, # ^ | ← Rev. 4 →   +5 one observation is that 0^1^2^3=0so in my solution, i tend to make a matrix like this first: $\begin{bmatrix} 0 & 1 & 0 & 1 & 0 \cdots \\ 2 & 3 & 2 & 3 & 2 \cdots \\ 0 & 1 & 0 & 1 & 0 \cdots \\ 2 & 3 & 2 & 3 & 2 \cdots \\ 0 & 1 & 0 & 1 & 0 \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix}$and the later code is just make them different. though the impl contains some magic number, but the idea is keep the two least siginificant bits and change the higher bits. like xxxxx[00~11]also, if we "seperate" the origin matrix every 2 rows/cols, there are some 2*2 blocks "cross" the seperator. so this case we'd better make the modification only depends on row number(in my code (i / 2) << cnt) or col number(in my code (j / 2) * 4).and i recommend you to see jiangly's code, much simpler
•  » » » » » 12 days ago, # ^ |   0 UUUnmei I tried doing this but can't think of encoding in order to make all different and also still satisfy the condition.
•  » » » » » » 12 days ago, # ^ |   +8 well, you can run my code and output the result after each step and do some obsversation. think first two rows for a start, and modify them based on coloumn number. each result col will be like (0 2)(1 3)(4 6)(5 7)(8 10)(9 11)(12 14)... in other words, add 00000,00100,01000,01100.. to every 2 coloumn respectively. this is keep the two least siginificant bits and change the higher bits. we do so for all coloumns.then we modify by row number. the idea is same. but we have to keep not only two least siginificant bits unchange, but more. this is exactly what code while(t<2*m) t*2, cnt++ does — count the number of bits. and finally add on a proper number like (i/2)<
•  » » » » 12 days ago, # ^ |   0 i tried to make 0 in 2 by 2 blocks and then put in out matrixhere my code for that   ll ans[n+1][m+1]; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ans[i][j]=512*(i)+j; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<
•  » » » » » 12 days ago, # ^ |   0 You are under my genjutsu
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 isn't all elements of the matrix being == 0 a possible answer? or am i missing something? nope thats not it i misread
•  » » » 12 days ago, # ^ |   +13 you need to maximize different colors(values in matrix). All elements must be as much different as possible. Taking all zeros make it only 1color
•  » » » 12 days ago, # ^ |   0 Nope we can't make all elements 0 as the arrays needs to have as many distinct elements as it can have to achieve all the conditions
•  » » 12 days ago, # ^ |   0 I just fixed the 1st 2*2 box as 8192 8193 8194 8195Then I just filled the next 2nd box as 8196 8197 8198 8199Just like this I filled the first 2 rows and then from the 2nd row considering 0 based indexing I just did a[I][j] = a[i-2][j]+8192
•  » » 12 days ago, # ^ |   +5 generate a matrix of 256*256 and fill it with natural numbers (0,1,2,3,4,5.......). then print the the first n*m matrix for each test case. Done..
•  » » 12 days ago, # ^ |   -8 What I did is Spoilerjust filled the matrix with random numbers, then for every 4x4 matrix I can adjust lower right number to make xor of all 4 numbers equal to the xor of 4 numbers in the matrix that is 1 cell above it. In the end all of 4x4 matrices will have the same xor
 » 12 days ago, # |   +125 Trash round.The pretest is so weak.And there are too many hacks.
•  » » 12 days ago, # ^ |   0 +++
•  » » 12 days ago, # ^ |   +3 Indeed.And the example of Div2 D is so weak.
 » 12 days ago, # |   0 Participated after such a long time and clutched D , ahh feels good to get back to that feeling again
 » 12 days ago, # |   0 I made the following two submissions on D2D, the first one sorts a vector, and the second one set. Overall time complexity should be $\mathcal{O}(n \log n)$ acc to me.Basically, I want to know why did the second with sets TLEd ?
 » 12 days ago, # |   +4 How to come up with div 2C other than guesswork?
•  » » 12 days ago, # ^ |   0 Notice that in each 4x4 matrix we use 2 rows and 2 columns. And each is used twice. Solve for row and columns separately, use non-intersecting bits (for row and columns).
•  » » 12 days ago, # ^ |   +3 Hint : BinaryFor every 4 elements in a quad, try and keep the XORs for every digit of the numbers to be 0.To be more precise -> { 1100 1101 1110 1111 }0th digit -> 0 ^ 1 ^ 0 ^ 1 = 0 1st digit -> 0 ^ 0 ^ 1 ^ 1 = 0 2nd digit -> 1 ^ 1 ^ 1 ^ 1 = 0 3rd digit -> 1 ^ 1 ^ 1 ^ 1 = 0Try and build upon that
 » 12 days ago, # |   0 How to Solve DIV2 B
•  » » 12 days ago, # ^ |   0 mainatain a counter variable initially 0, notice that if your a[i]==1 then it means just add 1 to your counter because if you buy a new pig then u will be needing an extra cage as you dont know the gender. when a[i]==2 assume that half of them are males and other half females (any one can be assumed to be one greater in number in case counter is odd). why half of them and why not all same? because then you would be needing just (counter+1)/2 cages which is not the maximum considering the presence of 2 genders in the distribution. further, just divide the animals and calulcate the max no of cages required considering (counter+1)/2 and counter/2 males and females resp. it will turn out to be (2*counter+5)/4. update it and store the maximum of all of them.196612008
 » 12 days ago, # |   +15 Very bad statements ):
 » 12 days ago, # |   -9 Bforces
 » 12 days ago, # |   +14 The descriptions of problem Div2 A,B are terrible.
•  » » 12 days ago, # ^ |   -6 please all of DIV 2 participants put a dislike to this round as the statement of Problem B was totally misleading and wrong.. i wasted 2hour just to think on it..and statement changed in the last one hour of round ...
•  » » 12 days ago, # ^ |   0 Can't agree more, I originally thought Div2 A was asking for the max/min possible votes for each position i.
 » 12 days ago, # |   +46 The most difficult part of this round is to understand statement
 » 12 days ago, # |   +18 Tired of reading long and unnecessary statements
 » 12 days ago, # |   0 Failed to solve C again. Expert is waiting for me:(
•  » » 12 days ago, # ^ |   0 And you got runtime error in B. Sad noise
•  » » » 12 days ago, # ^ |   0 Pain...So much pain...
 » 12 days ago, # |   +3 C The matrix in the error report after submission starts from 0! This doesn't match the question! This took me an hour!
 » 12 days ago, # |   +16 How to solve div1F?
•  » » 12 days ago, # ^ | ← Rev. 2 →   +8 Let $\displaystyle f[i][r] = \max\left\lbrace\prod_{j=1}^{i}(\frac{1}{a_j}\lfloor\frac{a_j}{b_j}\rfloor) : \left\lceil\frac{k}{b_1b_2\cdots b_i}\right\rceil=r\right\rbrace$Then we can use $\displaystyle f[i][r]*\frac{1}{a_{i+1}}\lfloor\frac{a_{i+1}}{b_{i+1}}\rfloor$ to update $\displaystyle f[i+1][\left\lceil\frac{r}{b_{i+1}}\right\rceil]$Take notice of: There are no more than $2\lfloor\sqrt{n}\rfloor$ different numbers in $\displaystyle\lbrace\left\lfloor\frac{n}{1}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor,...,\left\lfloor\frac{n}{n}\right\rfloor\rbrace$And $\displaystyle \left\lceil\frac{n}{i}\right\rceil=\left\lfloor\frac{n+i-1}{i}\right\rfloor =\left\lfloor\frac{n-1}{i}\right\rfloor+1$So all possible $\displaystyle r\in R=\left\lbrace\left\lfloor\frac{k-1}{i}\right\rfloor+1 \bigm| i\geq 1 \right\rbrace$ and $|R|\leq 2\lfloor\sqrt{k-1}\rfloor+1$If we want to update $f[i+1][t+1]$ with $f[i][T+1]$, it is optimal to choose the smallest $b_{i+1}$ satisfying $T/b_{i+1}=t$. Then we can solve the problem in $\displaystyle O(nk^{\frac{3}{4}})$ time
•  » » » 12 days ago, # ^ | ← Rev. 6 →   +8 I suppose you mean $f[i][r] = \max \prod\limits_{j=1}^i$ instead of $f[i][r] = \max \sum\limits_{j=1}^i$?Could you explain more on the complexity? It seems to me that you're updating $f[i + 1][r']$ with $f[i][r]$ where $r, r' \in R$, so the complexity should be $\mathcal{O}(n \times |R|^2) = \mathcal{O}(nk)$. Why is it $\mathcal{O}(nk^\frac{3}{4})$?You might say that the complexity is $\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}))$, but as far as I remember $(1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}) \approx 2\sqrt{k}$ (reference) so it is still $\mathcal{O}(nk)$.Update: OK I understand where I missed. The complexity is actually $\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{2\sqrt{k}}}))$ because there are at most $2\sqrt{k}$ elements in $R$. So the complexity is $n \times \sqrt{k} \times 2\sqrt{2\sqrt{k}}$, that is $nk^{\frac{3}{4}}$.
•  » » » » 11 days ago, # ^ |   +8 OK. QwQIf we always simply enumerate all $r\in R$, it will take $O(|R|^2)=O(k)$ and get TLE.Again, for each $T$, the number of possibly $t$ is $O(\sqrt{T})$. If we enumerate $t$ for $T$ by the same way as enumerate $r$, we will take $\displaystyle \sum_{r\in R}\sqrt{r}\leq \sum_{i=1}^{\sqrt{k}}(\sqrt{i}+\sqrt{\frac{k}{i}}) \leq 2\sum_{i=1}^{\sqrt{k}}\sqrt{\frac{k}{i}} \leq 2\int_{0}^{\sqrt{k}} \sqrt{\frac{k}{x}}\text{d}x =4\sqrt{kx}\bigm|_0^{\sqrt{k}}=4k^{\frac{3}{4}}$
•  » » » » 11 days ago, # ^ |   +8 For each i, we need to compute $f(i, x)$ for each $x$ in the form of $\lfloor{k-1\over j}\rfloor$ with a complexity $O(\sqrt x)$. You can see that the total complexity for each stage is $\sum_{j\leq \sqrt{k-1}} \sqrt{k-1\over j} + \sum_{j\leq \sqrt{k-1}} \sqrt j = O(k^{3/4})$.
 » 12 days ago, # |   0 like a fish
 » 12 days ago, # |   +3 Annoying and useless statements :(
 » 12 days ago, # |   +5 My idea for $D$:Let $dist[v][s]$ is the minimum number of representations if we finished in vertice $v$ and the best representation cost is in vertice $s$ which is on path. Let $rem[v][s]$ is the number of coins at the end in this answer.I do Dijkstra, since the edges values are $\ge 0$. Fix vertice $v$ and best representation cost $w[s]$. Look at neighbour $to$. If $w[to] > w[s]$, then we go to $s_{new} = to$, otherwise $s_{new} = s$. Then if $rem[v][s] < cost$ then I add $ceil(\frac{cost - rev[v][s]}{w[s]})$ to number of representations.Answer is $dist[n - 1][i]$ for some $i$.However, I get $WA19$. Is this idea correct?
•  » » 12 days ago, # ^ |   +10 Maybe you should also use $rem[v][s]$ in your priority queue, as a tie breaker.
•  » » » 12 days ago, # ^ |   +13 Thanks, yes, this is incorrect, as it can be, that there are two pathes to some vertice with same "best representaion cost", but different edges cost, and I will propagate less $rem$ further. (Interesting, that it got wrong answer only on 19th test)
 » 12 days ago, # |   +8 Why is the time limit in Div1C set to 1 second? What solutions did you try to cut off? Why not set 2 seconds?
•  » » 12 days ago, # ^ |   -15 Why they should? 1 second is standart time limit and there no reasons to increase it more.
 » 12 days ago, # |   +8 div2 B English statement make me so confused
 » 12 days ago, # |   +40 The duration increase was a total bs, 2h -> 3h is a massive change and it only happened just before the start. This was only communicated in this post, so some people could easily not see that (myself included).
 » 12 days ago, # |   +65 Pretests for D are so weak that I don't even know if there are any pretests
 » 12 days ago, # |   +23 I spend 30 minutes in reading problem statment of 2a.
 » 12 days ago, # | ← Rev. 2 →   +64 FST.Pain.R.I.P. +264 Delta and 7thupd: why +274 with 10th
 » 12 days ago, # | ← Rev. 4 →   -6 Nice pretests, excellent excercise for debugging, dry-running and hacking! Makes the contest results a rng! Lots of suspension and surprises!
•  » » 12 days ago, # ^ |   +8 I remember in the old days every second contest was like this. But tbh I do not miss those times.
 » 12 days ago, # | ← Rev. 2 →   0 Please share some more problems like Div1 D.
•  » » 12 days ago, # ^ |   +3 Recent USACO Silver Moo Route II is a bit similar http://www.usaco.org/index.php?page=viewproblem2&cpid=1304Also maybe this? https://codeforces.com/contest/59/problem/E
•  » » 12 days ago, # ^ |   -13 Maybe you can try this. https://atcoder.jp/contests/arc073/tasks/arc073_c
•  » » » 12 days ago, # ^ |   +11 Sorry I mistook Div1 D for Div1 B.
 » 12 days ago, # |   +5 Nice pretests！
 » 12 days ago, # |   +32 Very weak pretest for D1B and D1C. Welcome to Hackforces.
 » 12 days ago, # |   +16 f**king pretests of B.
 » 12 days ago, # |   0 Inappropriate time
 » 12 days ago, # |   +45 does case like31 74 19 5intentionaly removed? I can't imagine these case doesn't appear if case was randomly created. If it was on purpose, I can't believe power of multi-testcase any more...
•  » » 12 days ago, # ^ |   +4 For D1C they didn't add pretest like 100 1 2 3I guess there were no pretests :)
•  » » 12 days ago, # ^ |   0 My D1B solution fails on a test22 48 3Like, n is 2...
 » 12 days ago, # |   +29 One more day at Codeforces! Spoiler
•  » » 12 days ago, # ^ |   0 Today is a nice day to drop out of masters...
 » 12 days ago, # |   0 Second time I solve Div2ABCD. Thanks for the round!
•  » » 12 days ago, # ^ |   0 whoa noice
 » 12 days ago, # |   +16 very bad statement for B ):
 » 12 days ago, # |   +283 So I guess people will be hating the round because of very weak pretests in C (and also B and maybe D I guess, I'm testing right now and more than 10% of random testcases make my solution fail, so the fact that there are $11$ pretests, each with $t \geq 1$, is very strange), but that's not the case. It isn't bad that the pretests are weak, the problem is that their strength is inconsistent between rounds.This inconsistency actually randomizes the contest, as people have to guess between "if it passed the pretests then there's no reason to look into this problem anymore" and "pretests don't mean anything and I have to decide myself on how much extra time I should spend". It's coordinator's job to keep the things right and imo this time this job was done poorly. The fact that the problems were "ready", as they were used on some olympiad, doesn't mean that there isn't much to do. You still have to check if everything fits codeforces standards.Also, scoring distribution totally sucks, as you can see in the standings. Idk who came up with it.
•  » » 12 days ago, # ^ |   -42 No matter what it's abnormal that over half of contestants on a single page of the scoreboard get FST.
•  » » » 12 days ago, # ^ |   -8 Even tourist got FST
•  » » » 12 days ago, # ^ |   +54 Yeah, "abnormal" is a word connected to the word "inconsistent". Many years ago it was totally fine and people were simply using different strategy, but as cf evolved this strategy was being punished -- there's usually no need to waste time if your solution passed the pretests and that's fine, the contest became more "comfortable".Yeah, by saying more I'd start repeating myself.
•  » » » 12 days ago, # ^ |   0 what is FST
•  » » 11 days ago, # ^ |   +11 I've Just submitted 1D (not participated in the contest), and got WA on test 84 (out of 85!!!). IIRC it's my record for the largest failing test so far. The test is clearly seem to be designed specifically for the type of mistake I've made (which is: sometise user-defined infinity not infinite enough). Not sure whether it is authors' generated tests, or tests from the successful hacks are added to the final test set. But if it is authors' generated, I'd move it to pretests.
 » 12 days ago, # |   0 In a single page of standing there are 12 FSTs on the scoreborad. How crazy it is!
 » 12 days ago, # |   -87 The authors should be banned, and the round should be made unrated
 » 12 days ago, # |   0 It it to difficult.
 » 12 days ago, # |   +2 Can pretests be stronger?
 » 12 days ago, # |   +2 weak pretests
 » 12 days ago, # |   +33 My GM :(
•  » » 12 days ago, # ^ |   0 ccccccccorz KOT
 » 12 days ago, # |   +13 Really disappointed in the contest dear Sir.
 » 12 days ago, # |   +132 Hello!In contest I passed E with 43 pretests in 3385ms.And now I received TLE on test 30 in final test.After contest I submitted again and passed all tests.Could you please deal with this Ormlis MikeMirzayanov?Thanks!
•  » » 12 days ago, # ^ |   +11 gyh bot/cf
•  » » 12 days ago, # ^ |   0 I got TLE in F on systests and now submitted the same code and got AC :(
•  » » 12 days ago, # ^ |   0 This blog had the similar situation before, but got many downvote. Why this comment got so many upvote?
 » 12 days ago, # |   0 OMG, 2 FST QAQ
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 introspectionWA in D because not handle the edge case(when i==n-1) correctlyWA in E because not realize the huge memory cost when multiple test cases.sad
 » 12 days ago, # |   +48 Forgot to add 1 line, lost 200 ranks, thanks pretest!
 » 12 days ago, # |   +45 Here is one solution for Div2C that does not require you to think too much (unless a probability calculation is "thinking too much")Fill the first row and column with fully random numbers in the range of $[0,2^{63})$. After that, fill the rest of the grid as $arr[i][j]=arr[i-1][j] \oplus arr[i-1][j-1] \oplus arr[i][j-1]$. Now all submatrices with size $2 \times 2$ have a XOR of $0$. Probability of a collision will be at most $\frac{40000}{2^{63}} \approx 4 \times 10^{-15}$. I believe that there is a tighter bound of the probability but I am lazy to prove it.
•  » » 12 days ago, # ^ |   +29 I was even lazier and stress test all the cases before submitting :)).
•  » » 12 days ago, # ^ |   0 even simpler. a = [[ j ^(i<<10) for i in range(m)] for j in range(n)]
•  » » » 12 days ago, # ^ |   0 yes that is indeed simple but I am lazy to think
 » 12 days ago, # |   0 Happy Newyear!
•  » » 12 days ago, # ^ | ← Rev. 2 →   +1 I think the pretests are constructed to make participants get FSt.
•  » » » 12 days ago, # ^ |   +4 And FST on Test 69 was intentionally created to tease the participants xD
 » 12 days ago, # |   0 Why am I getting Runtime error https://codeforces.com/contest/1802/submission/196666198 ?
•  » » 12 days ago, # ^ |   +1 Never call erase() method of a container while using its iterator, store elements need to be erased and call erase() after iteration instead.
 » 12 days ago, # |   0 can anyone share an intuitive idea of div2 C ...waiting for editorialI am guessing some property of xor of consecutive number has to be utilized, couldn't figure out :(
•  » » 12 days ago, # ^ |   0 i made xor of all elements of each square 2 x 2 equal zero
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 Try to assign some bits to each row and each column such that no row's bits are same as any columm's, and to get value for an element of matrix, sum up it's corresponding row's and column's values. In each 2*2 matrix, we have we have even elements corresponding to a row and a column so their individual xor becomes 0. Reason behind separating bits is that addition doesn't make any bits to get carried further. Like: $a_{ij} \ = \ 512 \cdot i + j$
 » 12 days ago, # |   +50 I've said this before, and I'll say it again. Aleks5d is not a good coordinator.
 » 12 days ago, # |   +21 This contest gives GreenGrape contests vibe.
 » 12 days ago, # |   +3 FST-forces
 » 12 days ago, # |   +343 Thanks to Aleks5d for the round coordination, statement translation Probably should have chosen someone who knows English. And can coordinate rounds.
•  » » 12 days ago, # ^ | ← Rev. 4 →   -60 I believe that contestants should just learn russian. It is statistically proven that it increases rating (and you maybe just found out why)upd: idk why I'm downvoted that much, my comment was obviously irronical and not serious
 » 12 days ago, # |   0 Div2-D had a very weak pretest. I got a WA in actual testing. It was : 1 2 10 100 10 100 Which cost me +ve delta.
 » 12 days ago, # |   +17 I have an FST, but my place became better)
 » 12 days ago, # |   +1 Not good! The f**king English statement in B confused me a lot. I literally spent about 30-40 minutes on it just to understand the statement and, respectfully the test cases! And in C, the test cases are hilarious! Abused the fckn time + delta! Unfair and unbalanced round!!! Please consider these problems next time!!!
 » 12 days ago, # |   0 Hardest Div2B I've ever faced.
 » 12 days ago, # |   0 Kirill asks you to help her weave a very beautiful blanket, and as colorful as possible!He gives you two integers n and m
 » 12 days ago, # | ← Rev. 2 →   +37 The system test is weak too.My solution for Div.1 D is wrong with the following input: hack1 5 5 0 1 99 1 5 1 1 2 1 1 3 1 2 4 500 3 4 1 4 5 5 My output:7 Answer:3Can't believe that it really passed system test.
•  » » 12 days ago, # ^ |   0 lol
•  » » 12 days ago, # ^ |   0 Bruh moment
•  » » 12 days ago, # ^ |   0 Luckily my solution can't be hacked by this input.
 » 12 days ago, # |   +13 A really simple solution for Div1A / Div2C: SpoilerRound up m to the next power of 2 and start each row with that number's multiples. Then, for any 2x2 square, the high-order bits in the top two and the bottom two spots cancel. Similarly, the low-order bits in the left two and the right two spots cancel. Hence every 2x2 square has xor 0.  0 1 2 3 4 5 8 9 10 11 12 13 16 17 18 19 20 21 In the square with upper-left corner 10: The 1's — 4's bits of 10 = 01010 and 18 = 10010 cancel. The 1's — 4's bits of 11 = 01011 and 19 = 10011 cancel. The 8's — 16's bits of 10 = 01010 and 11 = 01011 cancel. The 8's and 16's bits of 18 = 10010 and 19 = 10011 cancel.
 » 12 days ago, # |   0 vector> a; sort(a, a + n, [](vector x, vector y){ return x.back() < y.back(); }); Why this got TLE? Since cmp is O(1) and swap is also O(1), I think the time complexity is correct.
•  » » 12 days ago, # ^ |   +16 this has to copy construct two vector as parameters every time.try use const vector&
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 Oh, thanks a lot. Another question is, does copy construction affect to the time complexity or it's just a huge constant?
•  » » » » 12 days ago, # ^ |   +1 It just copies every time, which takes too much time and memory to copy every time. It is not a constant if I am not mistaken.
•  » » » » 12 days ago, # ^ |   0 It depends on the sorting method we are using. Suppose we have $n - \sqrt{n}$ vectors of size $1$ and $\sqrt{n}$ vectors of size $\sqrt{n}$, and we are doing quicksort on them. We randomly choose one vector and compare it with all other vectors, so there is a $1/\sqrt{n}$ probability to cost $O(n\sqrt{n})$ time on this step.Similarly we can construct a testcase to let merge sort run in $O(n^2)$. Heap sort seems to have a correct time complexity, but I am not sure.
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   +8 i think it will affect to the time complexity, because the time of memory allocation must be proportional to the size. very roughly O(n) time.we usually neglect this because problem will guarantee "the sum of n over all test case is no more than 2e5(for example)". so we can write something like for each testcase read n vector a(n) and we will just use O(2e5) memory in total, and it is kind of inevitable.but say if you write something like for each testcase read n vector a(MAXN) then it will certainly TLE/MLE if there are many testcasesand copy is another part of cost which won't be less than allocation
•  » » » » » 12 days ago, # ^ |   +6 Memory usage isn't a concern here unless you do something weird with the vector like moving it to the heap. It will be deallocated when you get to the end of the scope it's declared in, so it won't ever take up more than about MAXN*sizeof(int) bytes at any one time. TLE is definitely an issue though.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +8 Vector by copy i guess.Maybe sort(a, a + n, [](const std::vector &x, const std::vector &y){ return x.back() < y.back(); });
 » 12 days ago, # |   +13 This blog is getting downvoted a lot, problem A story gonna become real kekw
 » 12 days ago, # |   +1 if my mom saw the div2B she would be disgusted and will forbid me from ever participating in codeforces rounds.
 » 12 days ago, # |   0 Better edu rounds than weak pretests.
 » 12 days ago, # |   0 seriously, I don't understand how hard it is to create strong pretests. If you have a good amount of testers, you can notice the test where they fail on, and prioritize those testcases. Except, you're making the pretests weak intentionally.
 » 12 days ago, # | ← Rev. 2 →   0 I solved E as we were allowed to skip any index we want but still passed the pretests x_xmy solution was failing at this case:1 3 3 1 2
 » 12 days ago, # | ← Rev. 2 →   +3 Why not put some of the corner cases in the pretest???
 » 12 days ago, # |   +52 Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests!)
•  » » 12 days ago, # ^ |   +7 Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests, Unclear Problem Statements!)
 » 12 days ago, # | ← Rev. 2 →   +3 Maybe not the worst contest as some comments mentioned, but why is E much harder than F?By the way, the pretest of B is too weak that I and most of my classmates got FST...Note that I participated in Div.1.
•  » » 12 days ago, # ^ |   0 My friendlist is basically a full of systests on d1 B :clown:
 » 12 days ago, # |   +13 The statements made me feel dyslexic
 » 12 days ago, # |   0 Loved Problem C But Hate Problem B
•  » » 12 days ago, # ^ |   0 No one is asking for an INF amount of pretests. But there are some stupid solutions that shouldn't even pass pretests.
•  » » » 12 days ago, # ^ |   0 I mean if you get WA because you guess some random stuff and implement it without having any proof, you can't complain about getting systested...
•  » » » » 12 days ago, # ^ | ← Rev. 2 →   0 That's not what I mean obviously, why would anyone just submit random things? I mean the pretests should be able to cover details in the problem statements. In this contest it was possible to misread the problems and still pass pretests.
•  » » » » » 12 days ago, # ^ | ← Rev. 2 →   +7 Yes I updated my initial comment because I learned someone has been systested on div1 B for not seeing each friend should have at least one gift...
 » 12 days ago, # | ← Rev. 2 →   +1 I thought just i screwed up D in system testing.But there are many participants whose code passed pretests but failed in main testing in D. Hope you guys make better Pretests next time. Negative Delta coming towards me. Anyhow i enjoyed the round. xD
 » 12 days ago, # |   0 I thought with 11 pretests for 2D my solution would surely pass but nopeLuckily my delta is still barely positive
 » 12 days ago, # |   0 What's up with E's statement ? At first I though they can change the prices each year, the problem will be unsolvable then unless they pulled some Chinese data structure. This problem is easiest in last 4 problems and could've got hundreds more of submission if not for the statement.
•  » » 12 days ago, # ^ |   0 I've misunderstood it too. If each of equality constraints are independent, the problem will be unsolvable. But if the (i+1)-th constraint is laid over previous constraints, we only need to keep components by DSU (and calculate the intersection of valid price ranges when merging 2 components).
•  » » 12 days ago, # ^ |   +24 I understood the statement and came up with a solution, but that's like an hour of coding for me. "Hundreds more submissions" seems too hopeful
 » 12 days ago, # |   0 why are the problems not accsesible right now?
 » 12 days ago, # | ← Rev. 2 →   +3 Nice contest
 » 12 days ago, # |   +16 Is this round gonna be unrated?
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 Nope, ratings will be updated soon. Happens a lot in CF.
 » 12 days ago, # |   0 why everyone hated problem b ?? its a very nice problem .
•  » » 12 days ago, # ^ |   0 Well, many contestants were not able to understand the problem statement. Because simpler cases were explained, but tough ones weren't explained. So its obvious many hated the problem B for that :)
•  » » » 12 days ago, # ^ |   0 even those simpler cases are not understandable
•  » » » » 12 days ago, # ^ |   0 Well problem was medium but explanation wasn't up to the mark for majority, that's all I can say then hehe :)
 » 12 days ago, # |   +1 Why they write in problem C bitwise exclusive or instead of bitwise xor.I was confused.
•  » » 12 days ago, # ^ |   +1 oops, I just saw it was xor not or.LOL
•  » » 12 days ago, # ^ |   +1 The symbol of XOR was given so i didn't even read the above part XD
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 I don't know symbol of xor that's why i said!
•  » » » » 12 days ago, # ^ |   0 I did same mistake in Div 3 this year and got 9 wrong submissions on problem B only. Can feel u from deep of the planet Saturn
•  » » » » » 12 days ago, # ^ |   0 I also did this Div 2 in problem C.
 » 12 days ago, # |   -21 Why so many downvotes ?The contest was difficult but interesting (even though I could solve only first two).The setters deserve respect
•  » » 12 days ago, # ^ | ← Rev. 2 →   -10 Because statements are very bad and unclear. Pretests were very weak. Many people got FST, but passed pretests.
 » 12 days ago, # |   +6 It's ok to comment to help the setters improve but I don't think that it's fine to downvote just because you got FST on d1 B/d2 D...
•  » » 12 days ago, # ^ |   -10 That's way problem setters need to control the amount of FSTs by prepare pretests carefully.
•  » » » 12 days ago, # ^ |   +2 Don't forget increasing the duration by an hour right before the contest.
•  » » 12 days ago, # ^ |   0 didn't you read the problem statements, can't you see how bad they are?
 » 12 days ago, # |   0 not able to figure out what is wrong with my div2 D solution, here's the code
•  » » 12 days ago, # ^ |   +1 Try using a multiset
 » 12 days ago, # |   -24 Idk if i feel happy i didn't experience this clowning or sad that i didnt capitalize on the fsts for infinite delta
 » 12 days ago, # |   +9 I don't get the downvoting. Yea there were fsts but the tasks were nice
 » 12 days ago, # |   +32 It's sad when one person who published a post gets a negative contribution because of mistakes by the team and the coordinator in particular.
 » 12 days ago, # |   0 So, is the contest going to be rated? $5$ hours have passed since the end of the contest and yet no news have been published regarding the situation.
•  » » 12 days ago, # ^ |   +42 why in the world it can be unrated?
•  » » » 12 days ago, # ^ |   -16 I mean, yeah, (possibly intentionally) weak pretests shouldn't be a reason to make a contest unrated, since there have already been a few rated contests with extremely weak pretests in the last couple of years (and I have a positive delta, so I want it to be rated)0). However, the rating change hasn't happened yet and that's why I'm asking it here.
•  » » » » 12 days ago, # ^ |   +31 My guess is that there is no rating changes, because people who can do it are busy with on-site contest. I will be very surprised if the round is declared unrated due to weak prеtests, correct me if I am wrong, but there has never been such a precedent in the history of codeforces.
•  » » » » 12 days ago, # ^ |   0 rating change has happened if you click on all contests it saying unrated contests.
•  » » » » » 12 days ago, # ^ |   +3 it shows like that on all the contests whose ratings haven't been updated
•  » » » » » » 12 days ago, # ^ |   0 Okay
 » 12 days ago, # |   +9 C>D>E
 » 12 days ago, # |   0 is this round rated?
•  » » 12 days ago, # ^ |   0 yup, if it wasn't rated they might have added another update that round will be rated and why? But since no such update is there, it's definitely rated and ranks will be updated too :)
•  » » 12 days ago, # ^ |   0 I think yes.But it's taking a lot of time in giving the final rating changes.
 » 12 days ago, # |   0 Can someone help me find out the mistake in my solution for Div1C/Div2E ? https://codeforces.com/contest/1802/submission/196698368
•  » » 12 days ago, # ^ |   +3 1 4 1 1 3 5 1 3 1 5 2 4 5
 » 12 days ago, # |   +9 Why is it taking so long to publish the rating changes ??I guess the round is rated !
 » 12 days ago, # | ← Rev. 2 →   0 Me: Seeing likes of this post.All others: Taking Div2 — A problem seriously
 » 12 days ago, # |   0 This doubt is related to Problem div2E I have a doubt regarding how inbuilt sort function works. I actually want to sort a vector of vectors on the basis of the last element of the vector. First I implemented an comparator function but It gave TLE on some testcase. For more details please check my submission 196715506Then I made a map of > and then reconstructed the vector of vectors in a sorted fashion by simply iterating over the map. For more details check my submission 196715303The only change between both the submission is of the way I choose to sort my required vector of vectors. Can anyone explain the TLE in first case??In advance Thanks a lot for your help :)
•  » » 12 days ago, # ^ |   +33 You have used copy construct function in your sort part:  sort(all(v), [&](vi a, vi b) { return a.back() < b.back(); }); This copy construct funcition takes O(size) time. and std::sort method will compare one element with others at most O(n) times. That's a O(n^2) method. Just modify like this:  sort(all(v), [&](const vi &a,const vi &b) { return a.back() < b.back(); }); const is not least but suggested. In the implement in map, the compared method takes O(1) time, either the swap method.
 » 12 days ago, # |   0 can anyone help me find the mistake here..verdict is: " wrong answer 42nd numbers differ — expected: '1', found: '0' " 196716275
•  » » 12 days ago, # ^ |   0 Find any correct solution and look in the tests for example test N36. For example you have the wrong answer on that one:)
•  » » » 12 days ago, # ^ |   0 thanks
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 Try testcase: 1 3 0 0 0 0 1 1 Correct answer should be 1
•  » » » 12 days ago, # ^ |   0 thanks
 » 12 days ago, # | ← Rev. 3 →   +14 Totally didn’t FST on Div1B / Div2D :( Spoiler