#  User  Rating 

1  tourist  3805 
2  maroonrk  3637 
3  Benq  3513 
4  ecnerwala  3506 
5  MiracleFaFa  3466 
6  slime  3428 
7  jiangly  3415 
8  Radewoosh  3399 
9  greenheadstrange  3393 
10  djq_cpp  3391 
#  User  Contrib. 

1  awoo  192 
2  isthisfft  191 
3  Monogon  185 
4  Um_nik  182 
4  YouKn0wWho  182 
6  maroonrk  170 
7  antontrygubO_o  167 
8  errorgorn  166 
8  kostka  166 
10  SecondThread  165 
+102
Hi, I wrote problems B, C, E. Thank you all for your participation!! 
+63
Why is it that every time I see a blog like this, it has existed for 9 hours, unanswered, last comment in 3 hours. Then when I start writing my response suddenly there are already 2 comments explaining the solution. 
+54
If we consider directed edge (i>xi), then each vertex will have out degree of exactly 1. Because of that, if we consider one graph such that all xi != 1, then each component will have at most one cycle if there are any. No. of connected components = No. of vertices — No. of edges + No. of cycles Initially we will have n components in which no edge is added. We will start adding edges one by one. Adding each edge will reduce the component by one unless we are already in a same CC in which it won't reduce. All such edges will have one to one mapping with cycles. So we can count cycles instead. Now if we consider the graph with X array given in the question. We will get some components. Each component will have at most one xi = 1. We only consider the component with xi =1 as we are interested only in cycles. Let the size of components be A1,A2...AM where M are the number of component which have xi = 1 Consider the cycle formed from component set {A1,A2,A3...AK}. We can permute them in (k1)! ways. And then we connect the edges. There are A2 edges we can direct of comp1 to comp2, A3 edges we can direct from comp2 to comp3 ... and A1 edges we can direct from compK to comp1. Then we can choose remaining edges arbitrarily. So we multiply N^(Mk). Thus for component set {A1,A2...AK} we have (k1)! * A1 *A2...*Ak * N^(Mk)ways to form a cycle. So we can use NTT to find Summation of product of (A1*A2*A3..AK) for each k. 
+52
Hello there, I'll try my best to give a clear explanation about the solution. first of all, let's assume that the given array contains no 1 (in other words, all edges are given). By looking at a single component of the graph, you can see the number of edges in it are equal to the number of nodes, since as given in the input there is a single edge having a starting point at each particular vertex. Therefore, for every graph built in the same manner as the problem asks, it is enough to count the number of it's cycles and add these numbers up to form the answer. So from now on, we forget about the main problem and solve the new one, which is counting the number of cycles of all the graphs that can be built. Array A may contain values equal to 1, let's see how the graph will look if we forget about these edges. There will be a bunch of components, each one having at most one cycle since there is at most one vertex in each with no edge starting at it. Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. Think of a cycle which there are T other values equal to 1 in A other than those used to make the cycle. Then there are n^T graphs containing the cycle. So if there already exists a cycle in a component of the given graph, just add n^(the number of 1s) and forget about these components. What is left, is a group of components, each looking like a tree, with exactly one node in them that you can add an edge from it to any other node to make your cycles. Consider a cycle using components with size B_1, B_2, ..., B_x. Then there are exactly
cycles that can be formed since you can put these components around a circle and then connect each component to the next one. So now you just have to calculate sum of the given expression for all components, which can be done using dynamic programming. Here's also my code for better understanding of the solution Code
I hope this helps :) 
+49
If all array elements occur at least $$$k$$$ times, then the answer is $$$n1$$$. Otherwise there is an element that occurs less than $$$k$$$ times and we will "split" the array into subarrays that don't contain that element and recursively solve those. Store all indices of all array elements in a We will write a function $$$solve(l,r)$$$ that calculates the maximum answer on the subarray $$$a[l,r]$$$. We will use a 2pointer trick with divide and conquer to achieve a good time complexity. Move the $$$l$$$ pointer to the right and the $$$r$$$ pointer to the left until we find an element that occurs less that $$$k$$$ times, and recurse if necessary. The code will look something like this
if we recurse on index $$$i$$$, then the recurrence relation is $$$T(l,r) = T(l,i1) + T(i+1, r) + O(min(il,ri)*log(n))$$$ The solution to this recurrence is $$$O(n*log^2(n))$$$, which is the overall time complexity. 
+41
Yes, this problem can be solved in $$$O(n \log n)$$$. First, let's assume we have a function that tells us whether a given subarray $$$l \ldots r$$$ is suitable and if not, tells us the position of an offending element, i.e. one that appears in this subarray more than 0 but less than $$$k$$$ times. Later we will discuss how to implement this efficiently, i.e. in time $$$O(\log n)$$$. To solve the problem:
The complexity is $$$O(n \log n)$$$: every element is crossed off at most once as the subarrays you recurse on are always distinct. Now let's discuss how to check if a subarray is suitable. First, we calculate values $$$\mathrm{need}[i]$$$: suppose $$$a_i$$$ is the $$$j$$$th occurrence of $$$a_i$$$ in the array. Then $$$a_{\mathrm{need[i]}}$$$ should be the $$$jk+1$$$th occurrence of $$$a_i$$$ in the array. If $$$j < k$$$, then set $$$\mathrm{need}[i] = \infty$$$. In other words, $$$\mathrm{need}[i]$$$ is the rightmost possible left endpoint of the subarray if $$$a_i$$$ is included and it is the last of its value in the subarray. How to calculate $$$\mathrm{need}[i]$$$ is left as an exercise to the reader but it is straightforward. Now we build a persistent segment tree that stores pairs, supports range minimums and point updates. Initialize it with everything set to $$$\langle \infty, \infty \rangle$$$. The $$$i$$$th revision of the segment tree is built as follows based on the $$$(i  1)$$$th revision:
To check if subarray $$$l \ldots r$$$ is suitable, take range minimum on the segment tree on the range $$$l \ldots r$$$ and revision $$$r$$$. If the first element is $$$\ge l$$$, the subarray is suitable. Otherwise, the second element tells you a faulty position. 
+37
the base case is you getting so bored that you close the tab 
+23
And here the government ?? What kind of brainwashing Ukrainians ?? We live here, we see without the government what is happening in our country, we see which "peace and freedom" russia brings. So if the russians really support their country, they in turn support the killing of children, women, and thousands of innocent civilians. No adequate person will support this, they are just all brainwashed and they believe that russia is a "liberator". You can say that Ukraine is throwing hundreds of fakes and all this is a lie, but in addition to the "Ukrainian government", there are thousands of foreign military journalists in Ukraine. Most of them have also seen all the horrors of the "russian peace". So if you still believe that the whole world is wrong, and russia alone knows what to do — I wish you to follow the ship) 
+18
Thank you so much for creating such great problems. Problem B is a nice practice for greedy algorithm, and I think there are several corner cases which one should take care of. As for Problem C, I missed the simple solution in editorial and used a more complicated one, but anyway, I have learned a lot of exciting ideas from your problems, thanks a lot! 
+18
B and C maybe a bit simple for me. Thanks for Problem E. I took really much time in it in the contest (sadly didn't solve D or E), and was happy when I could explain and proof the solution clearly. Really a nice construction round, thank you again. ;) 
+18
gaurav172, vivace_jr, shaanknight, Asia West, India, IIIT Hyderabad 
On
antontrygubO_o →
Invitation to CodeChef May Lunchtime (Rated for all)  15th May 2022, 32 hours ago
+13
Is there any particular reason that some submissions run faster in C++14 compared to C++17 on the judge ? 
+13
MatheusLealV, NaimSS, tdas, Latin America, Brazil, UNICAMP 
+12
i think you are the one who needs to solve problems. 
+12
Everything will be OK bro, just don't worry enough, I know it hurts, but You have not come this far to come this far. 
+12
You learnt to learn and learnt to problem solve. Web development is relatively easy in comparison. You'll be able to learn it much faster than those who only learnt that and then you'll surpass them in no time. 
+12
Man. I get the whole visible/hidden thing adding excitement but this was a contest that just rewarded giving up on large solves. I was bitten in the backside for sticking too long with B large because it appeared highly likely I'd need it; turns out I could've just brute forced C small and been fine. I don't feel like brute force solving should be deciding things at this stage in the competition (though I wish I had done it). 
+11
Thanks Jacob! Looking forward to it! 
+11
you overcomplicated the code for ifel you can just do this Spoiler

+11
My situation is exactly same but I will continue doing CP because I didn't start it for job. Was also not able to clear coding rounds of many companies because there were people who simply copy pasted from online. 
+10
I can't do better with a square board, but I think $$$625\times 650$$$ is possible. Identify the labels with elements of the finite field $$$\mathbb{F}_{25}$$$, the rows with ordered pairs $$$(u, v)\in \mathbb{F}_{25}^2$$$, and the columns with tuples $$$(a, b, c)\in \mathbb{F}_{25}^3$$$ where $$$(a, b)$$$ is restricted to the set $$$\{(1, x) \mid x\in \mathbb{F}_{25}\}\cup \{(0, 1)\}$$$. Then the label at the intersection of $$$(u, v)$$$ and $$$(a, b, c)$$$ is $$$au+bv+c$$$. Let's choose distinct rows and columns $$$(u_1, v_1), (u_2, v_2), (a_1, b_1, c_1), (a_2, b_2, c_2)$$$ and suppose that the corners all have the same label. If $$$(a_1, b_1) = (a_2, b_2)$$$ then $$$c_1\neq c_2$$$, so $$$a_1u_1+b_1v_1+c_1 \neq a_2u_1+b_2u_1+c_2$$$, i.e. the corners don't have the same label. Otherwise, $$$(a_1, b_1)\neq (a_2, b_2)$$$ so then $$$(u_1, v_1)$$$ is uniquely determined by $$$a_1u_1+b_1v_1+c_1$$$ and $$$a_2u_1+b_2v_1+c_2$$$. However, $$$(u_2, v_2)$$$ is determined by the same constraints so we would get $$$(u_1, v_1) = (u_2, v_2)$$$ contradiction. Also, by a counting argument, $$$625\times k$$$ is not possible for $$$k > 650$$$. 
On
antontrygubO_o →
Invitation to CodeChef May Lunchtime (Rated for all)  15th May 2022, 35 hours ago
+10
got it thanks :D 
On
rajkumar62506 →
Trilogy Innovations(CodeNation) 15th May 2022 Test. Solved 2 / 3.Very interesting problems to solve, 23 hours ago
+10
I had not participated in it. Was it some open contest like Codeagon? I went through the problems, here are my observations/approach, please correct me if I am wrong: 
+9
oh man you're paying way too much for bungee jumping, who's your bungee jumping guy 
+8
there's also a closed form (Binet's Formula) 
+8
Thanks Rishi! Looking forward to it! 
+8
Thank you so much for your detailed reply and paticient help, and I have learned a lot from your words. I think I have missed at least two important observations that prevent me from solving this problem. The first one is, if we ignore all 1, the left nodes will form several connected components, and each of them either contains a cycle or looks like a tree. If it already has a cycle, then we don't need change it, while if it is a tree, then we should add one more edge to it, and this is what we should compute. The second one is, as you said, "Now instead of counting for each graph the number of cycles it contains, we can count for each cycle the number of graphs which contain it and sum these values up. ". This is an important "transformation" of the original problem which makes the calculation available, and this is very tricky! Thank you so much again for your help, and hope that one day I could handle such problem on my own. 
+8
I solved ~330 tasks from acmp.ru and after that i became cyan. 
+7
with Treeset, there isn't besides doing linear, however you could implement our own binary tree and use binary search to localize the element. Another option would be use FendWick Tree 
+5
I got it, Thanks my friend for helping me ^_^. 
+5
If you don't know segment tree, you can also solve it by just using set ( one for column and one for row ) , let the set store the rows for which cnt[i]=0 , so if we remove a rook with {x,y} , we can add x back to row set if we have 0 rook in x row , and if we add a rook to set , we can erase x from row set , same goes for column set . 
+5
Se da un sir de cifre separate prin operatori '*' sau '+'. Avand voie sa faci maxim K interschimbari intre operatori, aflati valoarea maxima a expresiei. 
+5
I hope the "support" of Ukrainian IOI participants translates to you donating to them. As for the other point, there would be millions of people willing to discuss with you privately whether bombing civilian and spreading blatant lies and imprison people with opposite views is wrong or not. 
+4
Actually, unordered_map gives us an amortized constant time insertion and lookup. Notice that I've highlighted the term 'amortized'. It means that it doesn't always take O(1) to insert and look elements up, it's just that in the vast majority of the cases this is so; that means that there are cases — although very rare — when it doesn't take O(1) to lookup. In such cases, it can actually take upto O(n) to look elements up. map, on the other hand, gives us a worst case timecomplexity of O(log n) in any possible case. So, what seems to have happened is that you've hit the extremely rare case when unordered_map takes something like O(n). Hope this answers your query. :) 
+4
Results of this match: Both players managed to solve problems A and B, but Arun_bro1 beat Omar_Hafez by placing 647 ranks higher and solving problem C, which Omar_Hafez failed to solve. Although Arun_bro1 received quite a few Wrong answers on problem A and B at the beginning, he made a comeback by solving problems B, C, and then finally problem A about 70 minutes after the contest. This definitely gave Omar_Hafez some room to make his own comeback by solving problem C, which may have given him the lead due to his lower penalties. Winner of this match: Arun_bro1 
On
rajkumar62506 →
Trilogy Innovations(CodeNation) 15th May 2022 Test. Solved 2 / 3.Very interesting problems to solve, 30 hours ago
+4
Anyone solved all the 3 problems?? 
+4
Haha, I thought the same! At least the solutions are a little different 
+4
I think almost everyone in India who was too devoted to CP and expected something out of it without putting time anywhere else ended up in a similar situation (including me). For a while, I did share similar sentiments but to be honest I never did CP really for jobs. (It was a nice side benefit to have companies ask us in online assessments but I think CP is just like a challenging game to me. (even though it gets stressful at times) To put some weight on my point I actually play a game called osu! even during college (which has a huge skill curve too and while it's very challenging just like CP I play it for similar reasons.) What I mean to say is all challenging tasks are fun in a way and you shouldn't feel bad about doing CP. (maybe it was a mistake to devote too much time to it and yes you could have put your time into doing 'industry relevant' stuff but why do you think you can't come out of this peril. You made it to expert and 5 stars, they are not insignificant accomplishments. Just steel yourselves and fight your way out and you will get somewhere for sure. Sorry for the slight motivation rant in the end but I can relate to the blog too. Also don't consider dev to be a burden, I know it's pretty ironic considering my profile but if you put in sufficient time you will find it to be equally fun and challenging in its own way. 
+4
YES WE DO. 
+3
Please see the posted tutorial, thanks! 
+3
Refer to this 
+3
Thank you very much. It really helped. 
+3
"Ek hi to Dil hai Ivan Ji kitni baar jeetoge" it means in english "There is only one heart. How many times will you win? " <3 Thank you so much bro 
+3
Seems the bug has been fixed now. 
+3
1718 include problems solved in gym section and private mashups but 1698 does not include them. You can also change the settings to show all the problems solved including mashups. 
+3
Auto comment: topic has been updated by loser_iitian (previous revision, new revision, compare). 
+3
Yes, you are correct. This way of iteration of states is also known as "bottom up".
It is also possible to solve it in a way called "top down" but I felt it was easier to understand and explain the bottom up approach. 
+3
Wow, did you just come online from the big hiatus of codeforces due to this comment or do your frequently lurk? 
+3
I suggest practising the ABCD problems in the Atcoder Beginner Contest 
+3
Thank you very much ivanilos, you replied to a blog written 6 years ago. I was not hoping but really thanks for taking out your time and clearing the doubt. 
+3
Did you have hands 20 days ago? 
+3
Care for the disabled, start with you and me. 
+3
`` 
+3
afaik number of spots are not fixed. 
+2
I usually need motivation to play a game... 
+2

On
lavish315 →
Subject: Invitation to CodeChef May Starters 39 (Rated for Div 2, 3 & 4)  18th May, 5 hours ago
+2
As a problem setter, I would encourage everyone to read and think on every problem, as they are very interesting. All the best!! 
+1
But it is not a knapsack, if you closely observe. Even if it is, tell me the weight of the knapsack and also tell me the type of knapsack it it pls. 
+1
I hope Ukrainian students can take part in IOI. God bless Ukrainian people. 
+1
there is no way 
+1
Interesting take. I found math courses, competition math (I wasn't ever good at it), and solving competition programming on CF and Project Euler trained me to think for hours or days on one problem. 
+1
Yes 
+1
Any hint on how the total number of problems for a given user is computed? I've used Codeforces API to check some stats and according to my computation I have 1718 solved problems but according to the stats on my profile I have only 1698 solved problems (i.e. 20 less). Of course, I did deduplication not to take into account problems that were ACed more than once. Can you please elaborate on what problems or contests might be disqualified from being counted in the overall stats? 
+1
I got it, thanks. But, if war ends (I hope) is there any chance to be onsite? 
+1
I don't know why this post was downvoted, I think that Rookie SRMs are a great initiative for beginners by Topcoder + you can win cute prizes 
0
I too had same idea but how you handled the farthest node and largest one, can you please share code? 
On
chokudai →
Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） Announcement, 2 days ago
0
In Problem E, I can't understand how the optimization is working. Can anyone help me. The optimization of DP We can find that the g(k) is in [2,3,4,5], so we can use fenwick tree to optimize it. There are n fenwick trees, the ith is called C[i]. For each i,j:

0
Did anyone get any prizes , or was anyone contacted ? 
0
Can anyone help in this question? I actually tried so hard in this but stuck with TLE in DP solution, may due to stack overflow. Please help me with question. My TLE solution:

Ahahah 
0
Yes, clearing the map takes $$$O(N)$$$, but it isn't $$$O(N+NQ)$$$, because sum of all sizes of map can be at most Q (at most 1 element can be added to map during each iteration). That is why this solution works in $$$O(N+QlogQ)$$$. 
0
No, Thank you, ScoobyDoo! lis05 
0
If you can get $$$625 \times 650$$$, you can also get $$$625 \times 625$$$ by cutting the board (?) 
0
Video Solution for Problem D. 
0

0

0
Um, actually the states are a bit wrong. If we do it in this manner we will end up with a TLE since the total time left can be of the order 4e6 so instead take out the minimum possible sum of bad luck due to chosen gems and subtract it from total bad luck. In this approach, the 2nd state will initially be at max 2e3 since we can have at most 2e3 nonchosen items. Transitions : $$$dp[idx][notchosen]=min(A[idx][1]+dp[idx+1][max(notchosen−A[idx][0]1, 0)],dp[idx+1][notchosen])$$$ base case is if notchosen $$$ == 0$$$ at idx == size return $$$0$$$ else return Infinity. Hopefully this is the proper solution. 
0
I have a similar solution 157331395 with the following differences: When generating rectangles for $$$c$$$, we can do a small tweak so no two rectangles intersect with each other, this will make the count easier. We use $$$(x1, y1, x2, y2), x1 \le x2, y1 \le y2$$$ to represent a rectangle. We do a sweep line over the $$$x$$$ axis, move $$$X$$$ from $$$1$$$ to $$$n$$$, we use two 1D segment trees: $$$F$$$: Count the cover of rectangles that are fully inside the current region, i.e. the rectangle's $$$x2 \le X$$$. Let $$$F_y = $$$ the number of covered cells $$$(x, y), 1 \le x \le X$$$. We just use the traditional "range add, query sum" segment tree. $$$G$$$: Count the cover of rectangles that are partially inside the current region, i.e. $$$x1 \le X \lt x2$$$. Each leaf node $$$G_y$$$ maintains: 1. $$$x$$$: $$$x1$$$ of the rectangle covering column $$$y$$$, or 0 if it is not covered. 2. $$$cnt$$$: 1 if column $$$y$$$ is covered, or 0 if it is not covered. Nonleaf nodes maintain the sum of $$$x$$$ and sum of $$$cnt$$$. It is a modification of "range set, query sum" segment tree. We need to add an extra field to indicate if the column is covered. For every rectangle whose $$$x1 = X$$$, add it to $$$G$$$. For every rectangle whose $$$x2 = X$$$, remove it from $$$G$$$ and add it to $$$F$$$. To calculate the number of covered cells inside rectangle region (1, 1, X, Y): Let $$$g$$$ = $$$G$$$.query(1, $$$Y$$$). The count = $$$g$$$.$$$cnt * (X+1)  g$$$.$$$x + F$$$.query(1. $$$Y$$$) 
0
Auto comment: topic has been updated by jacob.b.zhang (previous revision, new revision, compare). 
0
exciting!! 
0
Thanks it was informative 
0
Here is my solution with ternary search. 
0
Yeah...got a delivery agent suddenly deliver the smartwatch one day without any prior intimidation.. 
0
Thank you for the advice 
0
same, but i get absolutely terrified when delivery agent start intimidating me. 
0
Auto comment: topic has been updated by dukhi_insaan (previous revision, new revision, compare). 
0
Can anyone post the editorial for C in easy words? 
On
antontrygubO_o →
Invitation to CodeChef May Lunchtime (Rated for all)  15th May 2022, 37 hours ago
0
Here it is Editorial. 
0
No, sorry. It is unfortunately somewhat annoying to go between Kattis and CF/Polygon problem formats. 
0
If there is a query box with width W and height H, then to cover each cell there must be at least one rook in each row in the box, or at least one rook in each column in the box. So, if there is a row and a column in the box which don't have a rook in them, then there is a cell that is not covered. Otherwise, all cells are covered. We can do two(one for columns, one for rows) Segment Trees with checking, if there is a zero in the segment. If we add rook, we add +1 to the column and row in the trees. If we remove rook, than we add 1. 
0
Thanks Rishi! Looking forward to it! 
On
antontrygubO_o →
Invitation to CodeChef May Lunchtime (Rated for all)  15th May 2022, 36 hours ago
0
s=A1&A2&A3&A4......&An i dont understand why we need to make all element equal to s? any proof? 
0
https://codeforces.com/contest/1679/submission/157366338 can anybody tell me why this code is is giving WA For problem C 
On
antontrygubO_o →
Invitation to CodeChef May Lunchtime (Rated for all)  15th May 2022, 35 hours ago
0
Let's say if array is partitioned into $$$k$$$ parts,where each part contribute to each number in the final array, and bitwise AND of each part is $$$a$$$ (values in the final array). Bitwise AND of the whole (original) array is basically the bitwise and of all $$$k$$$ final numbers, which is $$$a$$$($$$a$$$ & $$$a$$$ $$$=$$$ $$$a$$$). So that is why we have to make all elements equal to $$$s$$$. 
0
Thanks Rishi! Looking forward to it! 
0
Try this snippet

0
Can someone elaborate upon this how to calculate dp g(u,v,x) as defined in tutorial of problem F(Trees)(Subtask 5) in quadratic time? Or any other quadratic solution to the problem. Best I could come up with was O(n^2logn) solution with help of convolutions. nvm I was using FFT for convolutions but starighforward all possible pair multiplication too leads to O(n^2) complexity overall removing the logn factor. gr8 problem thanks :) 
0
The board $$$625\times625$$$ can be achieved just by placing $$$x_1x_2+y_1+y_2$$$ almost like in the editorial, but picking $$$x_{1,2}$$$ and $$$y_{1,2}$$$ from $$$\mathbb{F}_{25}$$$ instead of $$$\mathbb{Z}_{23}$$$. The question is, can you do at least $$$626\times 626$$$? 
0
Done. 
Name 
