atodo's blog

By atodo, 7 months ago,

I hope you enjoyed the problems! You can give feedback on each problem and also choose your favourite below. This could help me and other problemsetters understand what type of problems you want to see on Codeforces.

Hint 1
Hint 2
Hint 3
Tutorial
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Tutorial
Feedback
Hint 1
Hint 2
Hint 3
Tutorial
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Tutorial
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Feedback
Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Tutorial
Feedback

Now you can choose your favourite problem from the ones you solved during the contest or upsolved after it.

• Problem A
• Problem B
• Problem C
• Problem D
• Problem E
• Problem F

UPD: Don't forget to check out ak2006's video tutorials on his channel.

• +160

 » 7 months ago, # | ← Rev. 2 →   -35 Thanks for fast editorial and the wonderful round! This is the fastest editorial I've ever seen.
•  » » 7 months ago, # ^ |   +9 A little question about avoiding accidents: In this round I finished coding my solution to problem E in the last four minutes, but when I try to submit the code, I found I cannot do that. In some pages I can't click the bottom 'submit', and in somes others, I was told 'Put you source into the textarea or choose the file' although I have already choosen the file', it even return 403 error in one attempt. I think there is something wrong with my network, so I want to ask that have you ever encountered such a situation? How to avoid such a desperate situation?Forgive my poor English.
•  » » » 7 months ago, # ^ |   0 You are not alone comment, I also get 403 and white pages that don't reload... I started noticing this one year ago, more o less.
•  » » » 7 months ago, # ^ |   +23 I also can't click on submit sometimes and during hacking, each submission takes around 30 seconds to load which is annoying.
 » 7 months ago, # |   +18 :holyfrick: That was lightining fast .. Thnx for the hinted editorial !! helps a lot in upsolving :)
 » 7 months ago, # |   -6 Can someone give reasons for why D was a bad problem?
•  » » 7 months ago, # ^ |   +14 couldn’t solve = bad ig. I liked it, felt it was interesting
 » 7 months ago, # |   0 I really liked the idea of voting the favourite problem. Cool idea!
•  » » 7 months ago, # ^ | ← Rev. 2 →   -19 Was there in the last contest too...
 » 7 months ago, # | ← Rev. 3 →   0 Thanks to codeforces for providing fast editorial I was waiting for a solution to problem DValentine Day with codeforces has its own joy
 » 7 months ago, # | ← Rev. 2 →   +31 I spend Valentine's day with codeforces but failed round. That is unrequited love((((
 » 7 months ago, # | ← Rev. 4 →   0 Can anyone tell me why my merge_sorting& dsu solution to task C got TLE with code1 146412015,and after removing the array "rk" (code2)146425315 I got pretsets past???:(
•  » » 7 months ago, # ^ |   +9 Don't use "memset(rk,0,sizeof(rk));" for each testcase,if you do so,the time complexity of your code will be O(T*sizeof(rk)).But if you use "for(int i=1;i<=n;i++)rk[i]=0",the time complexity will be O(sum(n)),which can get pretsets past as well.(sorry for my poor English)
•  » » » 7 months ago, # ^ |   0 got it,thanks!
•  » » 7 months ago, # ^ |   0 Can you tell me how did you make the edges in merge sort algo
 » 7 months ago, # | ← Rev. 2 →   +9 Where is editorial of problem A & B? Please, check tutorial section of A & B.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +1 For b Push all odds into one array and all evens into another array if both arrays are not sorted print no else print yes the observation is if you start from sorted array and perform this swap operations and consider all possible arrays from these swap operations then you will see all even numbers are sorted in those arrays and also all odd numbers are sorted in those arrays
•  » » » 6 months ago, # ^ |   0 What a clever approach!
 » 7 months ago, # |   0 Thank you to all of you. The contest was so fun and challenging for me. The editorial is lighting speed too!
 » 7 months ago, # |   0 In F, I thought that for N up to 10'000 O(N^2) wouldn't pass. Looks like I should get better at judging constraints :P
•  » » 7 months ago, # ^ |   +28 Actually, $N = 10^4$ means to me that "only" $O(N^2)$ pass.
•  » » 7 months ago, # ^ |   +19 The strange limit for $n$ is for failing some heuristic that works like this: Find a wrong solution which finds an answer in $O(n)$ for a given starting position. Also have a brute force solution that finds the correct answer in $O(n^2)$ for a given starting position. Then, run the wrong solution on all positions and the correct solution only for the $30$ most promissing positions.Unfortunately, I could not find a pattern that would fail this, so we changed the limit for $n$. My solution runs in 748ms/2000ms.
 » 7 months ago, # |   0 python IO screwed me for D :(( limits were pretty rough
•  » » 7 months ago, # ^ |   0 same solution as editorial, just didn't use FastIO library. unfortunate
 » 7 months ago, # |   0 Could any one help me i am not able to find editorials , when I click on it it shows only some text, I can't find code any where??
•  » » 7 months ago, # ^ |   0 The text is the editorial. It explains the solution of the problem.
•  » » 7 months ago, # ^ |   0 For some contest, we don't get codes.. It depends on the author. In case you still need codes you can go and read submissions of others. To be precise you can follow SSRS_. He participates in almost all the contests and also his submissions are much similar to the editorial ones....
 » 7 months ago, # | ← Rev. 3 →   0 I think this is a simpler approach for problem C: SpoilerFor every $i$ that $a_1, a_2,...,a_i$ is a permutation of $1,2,...,i$ we have a new connected component.
•  » » 7 months ago, # ^ |   +1 double check problem D
•  » » » 7 months ago, # ^ |   +3 Ah it's C... my bad. Thank you man.
•  » » 7 months ago, # ^ |   +1 You mean problem C
•  » » » 7 months ago, # ^ |   +1 Yes, I made the edit.
•  » » 7 months ago, # ^ |   0 That does work.
•  » » 7 months ago, # ^ |   0 how?
•  » » » 7 months ago, # ^ |   0 Let us take an example of 3 2 1 6 5 4 , Here till the third index permutation of 3 is present so we could surely say that it will be a separate component which would not share any edge with 6 , 5 or 4 . But if we take an example :- 3 1 5 2 4 , Here till the third index we don't have the permutation of 3 this implies that there exists a number after third index which will share an edge with 3 and 5 both. Likewise we could calculate the number of connected components.
•  » » » » 7 months ago, # ^ |   0 brilliant!
 » 7 months ago, # |   0 VIDEO EDITORIAL FOR PROBLEM B : VIDEO_LINK
 » 7 months ago, # |   +1 Can anyone help me find why I got TLE for problem A in this solution 146366602. Unwanted infoSince I got TLE in it, I tried multiple different solutions, with similar logics, but got TLE in all those solutions as well. (146370431, 146389736, 146400809, 146425393)I spent more than 1 (or 1 and half hours) in problem A, and still couldn't solve. But was able to solve C in about 10 minutes. This made me feel that Problem C was much easier than problem A. (Don't downvote me for saying this)
•  » » 7 months ago, # ^ |   0 scanner?
•  » » » 7 months ago, # ^ |   0 For problems B and C as well, I use the same way to get the input using scanner. In those 2 problems, the value of n is a lot bigger than this.
•  » » » » 7 months ago, # ^ |   0 There are 500 tests and 500 n in problem A. It is 250000 elements. In problem B, for example, special limit on the amount of n: 50000. Scanner is slowly.
•  » » » » » 7 months ago, # ^ |   0 Oh. Didn't notice that.Just noticed this below statement in problems B and C, after reading your comment. It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.So, in problem A, it is max 250000 In problems B and C, it will be max 200000.I see the difference now. Thanks for replying.Any suggestions on how to get input, when the input is large ?
•  » » » » » » 7 months ago, # ^ |   0 When I changed from Scanner to BufferedReader, it passed. Submission — 146445635Thank you vdxz for your reply.
 » 7 months ago, # |   0 Problem C: Inversion Graph I got wrong answer on pretest 2 . DO you help me to get where is the problem and even this logic is it right ? 146422401
•  » » 7 months ago, # ^ |   0 Your merge function has a bug. if(parent[_x] != parent[_y]) shoulde be if(find(_x) != find(_y)) Though even after the fix the code will probably TLE.
 » 7 months ago, # |   0 For C I got Accepted with DSU while maintaining a set of maximums for components in the array's prefix. I believe it works in $O(n log n)$ amortized.
•  » » 7 months ago, # ^ |   0 After competition, we go 0 with DSU. Sed lyf
 » 7 months ago, # |   0 For problem C, can't we use DSU? I used DSU and got TLE!!! Can anyone explain why DSU is giving TLE?Thanks in advance!
•  » » 7 months ago, # ^ |   +6 My DSU solution passes, you can check it here 146394231
•  » » » 7 months ago, # ^ |   0 Thank you for sharing the submission. But, I didn't get what you did! It would be great if you could explain what was the approach and how that differs from my solution.
•  » » » » 7 months ago, # ^ |   0 See my explanation here. DSU is modified so that we maintain the maximum element of the set in the array 'm', similarly to the size of the set in the array 'sz'.
•  » » 7 months ago, # ^ |   0 solve() have difficult O(n ^ 2)
•  » » » 7 months ago, # ^ |   0 Nah it amortizes a lot. I think it's $O(n * log n)$ because when there's a bunch of maximums bigger than currently added value, they all get reduced to one component
•  » » » » 7 months ago, # ^ |   0 Can this be proven somehow? Even I passed it using this but still have no idea why it works.
•  » » » » » 7 months ago, # ^ |   0 Yeah, of course. I will refer to my solution 146394231. DSU technically isn't O(1) but for these constraints let's say it is.So let's consider the inner while loop. How many times the operations inside, which btw take constant time, will get executed (not in one iteration of for loop but for the duration of the whole solve())? For this let's consider the value of comp_maxes.size(). We see that for each iteration of for loop it increases at most by 1. So it cannot be greater than $n$, its size is linear. And in while loop it can't decrease by more than its size. Said differently, number of deletions (which is equivalent to number of executions of while loop) cannot be greater than number of insertions, which is linear. So body of while loop will get executed at most $n$ times overall. So the cost of solve() is $n$ times the cost of set::lower_bound() which is $O(log n)$.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Your implementation for dsu has an infinite loop. If s1 = s2 in the unite function, then value of dsu[s2] becomes positive and if you try to use find_set on any member of this component, it will never find an answer.
•  » » 7 months ago, # ^ |   0 I used DSU and merge_sorting.Here is my AC code 146425315,which is O(nlogn).Hope it will help you.
•  » » » 7 months ago, # ^ |   -8 Thanks, it helps me a lot.
•  » » 7 months ago, # ^ |   0 You are getting TLE not because of DSU, but because of nested for loops.
 » 7 months ago, # |   +8 In my opinion, Problem D is just a TopSort. The solution by using BFS is just implementing the TopSort using BFS, they are the same. Am I right?
•  » » 7 months ago, # ^ |   0 I'm not sure you can do it as a topsort directly, because there may be multiple different operations that "unblock" a position. However, you only need one operation to unblock a position, but the topsort will enforce that you do all such operations. Maybe there's a different way to frame it as a topsort, but I could not come up with one.
•  » » » 7 months ago, # ^ |   0 Here is a similar problem that everyone (basically) use topo sort. Strange Printer IIMainly 3 different points compared to this problem: 1. no 2x2 restriction 2. only use colour once. 3. Output result if valid.I believe the third one won't be hard, since we just record the result when the in-degree is 0. I am getting stuck when I try to resolve the 1 & 2.
 » 7 months ago, # |   0 Hackforces...
•  » » 7 months ago, # ^ |   0 To me it's more like SpeedForces...
 » 7 months ago, # |   +28 Shit happens:
 » 7 months ago, # |   0 For problem E, I don't understand why we need using a data structure such as Fenwick tree or segment tree.It seems that once we have the lazy[color] array, we don't need to do "range add" operations, we just need to deal with intervals.
•  » » 7 months ago, # ^ |   0 I think, when you change color you should utilize lazy array and add its value on a given interval which you consider.
 » 7 months ago, # | ← Rev. 2 →   0 .
 » 7 months ago, # |   0 Can anyone tell me how i got memory limit exceeded for this submission for problem B? I guess I messed something up but everything seems OK when I look at the code.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +3 If n == 1, you dont read in the only element in the array, which then causes it to become the n on the next pass. Try cin >> n; inside the if block.
•  » » » 7 months ago, # ^ |   0 Yeah, that's got to be it. Thank you.
 » 7 months ago, # |   0 I wonder why my solution for C worked. I counted all such indexes where the prefix sum is i*(i+1) // 2 (1 based index). Can anyone explain or hack my solution?
•  » » 7 months ago, # ^ |   0 You will need this observation: if $a_1,...,a_i$ is a permutation of $1,...,i$ then there is no edge from vertices from $1,...,i$ to the rest. Then, call $i_0$ the first index satisying our condition. It is clear that $a_1,...,a_i$ form a connected component. Then consider $i_1$ the next number. We have $a[1..i_0]$ is not connected to $a[i_0+1..i_1]$ and $a[1..i_1]$ is also not connected to the rest. So we can conclude $a[i_0+1..i_1]$ is also a connected component.So now we need to count number of $i_j$. Your implementation is correct because sum of $k$ distinct positive integers is $k\cdot(k+1)/2$ if and only if they are a permuation of $1,...,k$.
 » 7 months ago, # |   0 O(n) solution for B problem still failed with PyPy3? Tight constraints requires an extended limit for heavy languages such as python.
 » 7 months ago, # |   0 The intended solution for C is really cool.
 » 7 months ago, # |   0 Problem C-Inversion Graph using Segment tree link
 » 7 months ago, # | ← Rev. 2 →   0 I solved problem C using sets and Segment Tree which is overkill but can anyone help me calculate it's complexity I think it's O(n * log(n)) but not sure... Here is the link
 » 7 months ago, # |   0 I think Problem D had weak pretests
 » 7 months ago, # |   0 Can someone explain A? I'm dumb
•  » » 7 months ago, # ^ |   0 No, You're not a dumb. You are just a beginner.
•  » » » 7 months ago, # ^ |   0 No I'm stupid af. I feel frustrated and hate myself all the time while doing codeforces. I can't even solve ad-hoc (Div2 A/B) problems on my own without reading editorials, let alone more difficult ones that require DSA. The solutions are always tricky and appear out of nowhere. How can I improve? Pls help this dumbass.
•  » » » » 7 months ago, # ^ |   0 practice is the only true mantra
 » 7 months ago, # |   +5 Problem C short solution - Solutionint n = scanner.nextInt(); int max = -1, ans = 0; for (int i=1; i<=n; i++) { max = Math.max(max, scanner.nextInt()); // Update the max element iterated so far if (max == i) ans++; // Increment ans, if max element matches with the count of all elements iterated so far } System.out.println(ans); Submission — 146445712.Submission During contest — 146419476.(The only time it was helpful for me in not knowing a particular topic like Segment tree / DSU / Graphs / Etc.)
•  » » 7 months ago, # ^ |   0 this works like magic but my brain could never think an implementation like this :)
•  » » 7 months ago, # ^ |   0 can you give me any logic behind this implementation??
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 For me personally, looking at the diagrams given in the problem's test case helped. Problem statementWhenever we see an element, let's say x, then, all elements less than x which are on the right side of this element will be a single component. Example - to get familiarised with this problem:Eg. (Test case 5 in problem): 3 2 1 6 5 4. Here, when we are in number 3, we can see that, 3 2 1 will be of a single component, as they are to the right of 3, and which are lesser than 3. Similarly, for number 6, the numbers 6 5 4 will be a single component. Important example that helped me get this idea:The same way, if we try for Eg. (Test case 6 in problem): 3 1 5 2 4. We can be sure that, 3 1 2 will be of one component. But, the number 5 comes in between, that means, all elements below 5 and which are to the right of 5 will be of same component. So, 5 2 4 will be a single component. Since, 2 is part of both these parts, we can combine it into a single component. (That's how I formed this idea) So,So, we start with an element, and iterate till we find all elements below that number. In case we find a larger element, then, we iterate till we find all elements below this newly found larger element.If the count of elements visited so far is same as the maximum element found so far, that's when we can be sure that, there can't be anymore smaller element (than this max) to the right of this element. And that's when we can increment the answer (number of components). Additional examples to try, to make sure this works:3 1 4 2 6 5 7 and 1 2 3
•  » » » » 7 months ago, # ^ |   0 Great approach.
 » 7 months ago, # | ← Rev. 2 →   0 Problem C can be solved using sparse table 146448264
•  » » 7 months ago, # ^ |   0 Creating sparse table is actually not required. Since, you are always calculating minimums for a suffix, you can precompute all suffix minimums.
 » 7 months ago, # | ← Rev. 2 →   0 A possible solution of C without using graphs or DSU or Stack or anything, just pure observation solutionint i_sum=0; int v_sum=0; int ans=0; for(int i=0;i
•  » » 7 months ago, # ^ |   0 it passed all the test cases if acc to you it will fail on any case then do let me know.
•  » » » 7 months ago, # ^ |   0 Only if connected components is 1 and n = 10^5. Use long instead of int.
 » 7 months ago, # | ← Rev. 2 →   0 FML
 » 7 months ago, # |   0 Could someone help me understand problem E please?I understand that we keep contiguous intervals that have the same value and why that's o(q), I don't understand how we handle a value update query. The only possible way I see is going through all the intervals that have elements between l and r and individually updating those intervals, which is o(q). Do we have a bunch of seg trees of intervals? How does that work when the intervals are changing all the time?
•  » » 7 months ago, # ^ |   +4 Each interval has a color id. Let's keep two arrays: pendingColor[c], the updates pending for each color group, pending[sid], the updates delta pending for a particular segment id When updating a color, do it in O(1): pendingColor[c]+=x.When creating a new segment with a given color, I create it with an offset pending[sid]=-pendingColor[c].That way, the updates pending for a given segment ispendingColor[c]+pending[sid].
 » 7 months ago, # |   0 Please, someone help me find why this code is giving RE? Here is the submission link: https://codeforces.cc/contest/1638/submission/146451668
•  » » 7 months ago, # ^ |   0 for(int i = 0; i < vpe.size() — 1; i++){vpe.size() is unsigned int64. if size == 0, then it will not be i < -1, but i < max(unsigned int64).PS: I looked your code and can not find the error so I tried for myself and my IDE gave me the tips.
•  » » » 7 months ago, # ^ |   0 Thanks for the tips! It would be great if you can share the name of your IDE :)
•  » » » » 7 months ago, # ^ |   0 Qt Creator. But I think any modern IDE will have similar functionality.
 » 7 months ago, # |   0 Here's my C solution, O(n) time O(1) space: 146453148Logic : Keep the track of max value, and keep track of all the element that are less than that to make a complete permutation which ranges from 1 to max value found.
 » 7 months ago, # |   0 hey can anyone explain me that if the value of n<=10^5 is constraint of question B then then why there is a testcase n=86227?? is this under constraint???
•  » » 7 months ago, # ^ |   +3 Get your maths right.
•  » » 7 months ago, # ^ |   0 Obviously bro!!!! 10^5 is 100000 which is way greater than 86227.
 » 7 months ago, # |   0 I've never thought that i will get the editorial this much fast.
 » 7 months ago, # |   0 Fun fact about problem D (because I tested this round): its original constraint was N<=500, which let a relatively straightforward solution pass. The solution was "while any changes are possible, traverse the whole matrix and update every 2x2 square whose non-special cells are of the same color". Can you see why this always works in O(N^3)?
•  » » 7 months ago, # ^ |   +25 It doesn't seem like that's the case, what happens in a case like the following? 1 2 1 2 1 2 1 1 3 3 2 1 2 1 2 1 2 2 3 2 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 3 1 2 1 2 1 2 1 1 3 3 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 1 2 1 1 2 1 2 1 2 1 3 
•  » » » 7 months ago, # ^ |   0 Is the test idea that a BFS would traverse this in a zig-zaggy fashion with O(N^2) iterations in total? I guess that reduces my fun fact to "I was fooled to think my straightforward solution is O(N^3), and tests were weak" xD
 » 7 months ago, # |   +24 Problem C is just a sub problem of 1270H - Number of Components
 » 7 months ago, # |   +4 Good contest , especially considering no matter what you do you will always pass pretest C
 » 7 months ago, # |   0 YES the F one TWO POSTURES was stupendously written and i am still trying to solve this without seeing the Editorial,I hope that i can.
 » 7 months ago, # |   +1 Can anyone explain why my C worked, I observed it for few self generated tests and got AC. Can someone hack it or give a proof why it works ? Code : 146425328
•  » » 7 months ago, # ^ |   0 Each component is a segment of the array because consider a inversion with indices i, j then if a[k] < a[i] where i < k < j then it will have edge with index i else if a[k] >= a[i] then it will have edge with index j which means every element between index i,j will belong to the component of i,j. Consider two adjacent segments seg1,seg2 which are forming different connected components which means there is no edge from any element of seg1 to any element of seg2 which means that max element of seg1 is less than min element of seg2. If you consider a prefix till index i (one based indexing) and if it is containing all the numbers from 1 to i then max element of 1 to i is i and min element of remaining array is i + 1. So the sub segment till index i will increase num-of-connected-components by one which exactly your code is doing .
•  » » » 7 months ago, # ^ |   0 I understood first two paragraphs easily but I am having difficulty in understanding 3rd paragraph. Can you please elaborate on it.Thank you for your time :)
•  » » » » 7 months ago, # ^ |   0 Its like we are starting with all the indices in one component and then we are forming new component when prefix till i is disconnecting with suffix[i+1 .. n](which again may get split in future). And that happens when max(prefix till i ) = i, that is prefix till index i has elements from 1 to i.
•  » » » » » 7 months ago, # ^ |   0 Okay understood. Thanks
 » 7 months ago, # |   0 Editorial came out so fast! thank you!
 » 7 months ago, # |   0 can we do 3rd question using dsu if someone has done it using dsu ! pls tell me your approach cause I'm getting tle in 3rd test cases
 » 7 months ago, # |   0 very good editorial.. ideal for beginners like me. It should be like this with hints.. at least for div3 and div2 contests. Thank you for the nice editorial.
 » 7 months ago, # | ← Rev. 2 →   0 **A way to reduce C to a known problem : MERGE OVERLAPPING INTERVALS** While iterating over the array whenever we encounter the max element, we group the elements into a pair of (min, max). Now in the next pass, if the min of the current segment falls in the range of previous segment(s), they are part of one connected component. [Link to Submission here](https:/codeforces.com/contest/1638/submission/146422918) **A good observation for B :** If odds and evens in an array are sorted respectively, the answer would be yes, else no. If a pair of same parity comes together while bubble sorting, and if a_i > a_(i+1), the answer would be "No", else "Yes". [Link to submission here](https://codeforces.cc/contest/1638/submission/146382565) 
 » 7 months ago, # |   0 Loved the contest, Big Brush was a really good problem.
 » 7 months ago, # |   0 can anybody help me why my program is giving TLE in test case 4 ?? program link 146482560
•  » » 7 months ago, # ^ |   0 instead of endl use "\n", TLE is due to slow output, my solution was also getting TLE due to same issue.
•  » » » 7 months ago, # ^ |   0 Thank you bro it is submitted
•  » » » » 7 months ago, # ^ |   0 yeah, no problem!
 » 7 months ago, # |   0 Loved C because it was misleading to use dsu at first
 » 7 months ago, # |   0 Here is an my solution to C without dsu or stackhttps://codeforces.cc/contest/1638/submission/146419135Intuition :if at ith position the maximum is i, then from i+1 onwards there will not be any number lesser than i so no component can connected to this group
 » 7 months ago, # |   0 Very simple (just 5 lines) and interesting solution for Problem C — Inversion Graph. You just need to see one simple observation. do check it- https://codeforces.cc/contest/1638/submission/146489157
 » 7 months ago, # |   0 problem B solution is very very good ! thankss
 » 7 months ago, # |   0 can anyone give me simple and understandable code for problem B
 » 7 months ago, # | ← Rev. 4 →   0 Problem B can be solved by finding the minimum on the suffix.Submission: 146422034
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 I did the same thing but I am getting TLE. Solution with sorting working but still getting TLE My Solution: 146510364 If anyone have any idea why and how to fix this please help
 » 7 months ago, # |   0 Great contest!! really nice problems. Short story and clear statements.
 » 7 months ago, # |   0 If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.comProblems added: "A, B, C, D, E, F".If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
•  » » 7 months ago, # ^ |   0 This is super helpful! Thank you.
 » 7 months ago, # | ← Rev. 3 →   +8 Good contest. Some comments: Problem $C$ is one of my favorite easy problems. Problem $D$ is not original; I think it appeared in a past old USACO Gold contest. Nevertheless, it is quite a good problem :D
 » 7 months ago, # | ← Rev. 2 →   +3 Did I miss something? I'm talking about problem E. SegTree146566296 BIT146566646What's wrong with this solution? It's not cool, when you face with this kind of "problems" :/P.S. tight TL for SegTree?
•  » » 7 months ago, # ^ |   0 In regard to my implementation, BIT is almost 4-times faster than Segment Tree. So it is recommended to use BIT when both are options because it is faster and shorter.Another reason that leads to TLE is the excess time on IO. (n=10^6) You can use fread to get faster IO like 146629883. In my experiments, it save ~1600ms in this problem.
 » 7 months ago, # | ← Rev. 3 →   0 I think I kinda cheesed C lol (weak tests?) I used a DSU with a simple set. A element can only start its own connected component if it is the greatest in the set so far (if you sweep from left to right). Therefore any element smaller than that will auto join its connected component. In the set, I only kept the biggest values of each connected component and for each element, binary search and manually join the components with max values bigger than that element.Here is my code that passes in nearly 800ms lol https://codeforces.cc/contest/1638/submission/146576523Edit: there is a smart optimization for this but its still kinda cool my brute force passedEdit 2: i appreciate the hack :D
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 For Input n-1, n-2, n-3,... 1 it should fail, since it becomes O(n^2)I did nearly the same implementation, but deleted the unused elements from the set, then it is O(nlogn)
•  » » 7 months ago, # ^ |   +1 Hacked.
 » 7 months ago, # |   0 In D, are "dead ends" not possible? We can choose every possible square on each step?
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 I'm also thinking this thing while upsolving D. I had a blurred picture not super clear that if there might be a dead end it'll be reached in m*n steps and when we have a choice to form new special cells, we can go with any choice as long long it's creating at least 1 new special cell because choosing set A cells rather than B do not hinder our answer as set B can always be chosen later. I mean choosing one set of cells over another doesn't force us with restricted choice. Idk whether what I'm thinking is right or wrong.
 » 7 months ago, # |   +10 Just want to let you guys that I think it's almost impossible to get Accepted in problem B with Python3 with regular I/O, you will need some kind of fast I/O. I tried multiple submission and changed the solution for problem B, but alas the problem fast only I/O all along.Here's the difference Without fast I/0 (TLE): 146596308 With fast I/0 (Accepted): 146596576No offence really, but I also think it would be better if the problem setter take this kinda stuff in mind so it doesn't make Python coders in disadvantage. Or the admin could set difference time constraint according to difference language.Anyway, I'm not really angry that my solution didn't get Accepted in the contest. Just a little bit annoyed because the constraint, that's all, peace ✌️✌️
•  » » 7 months ago, # ^ |   0 Instead of using fast i/o you've mentioned, there is ultra light weight version (but slower a bit): 146387910
 » 7 months ago, # |   0 have any one could prove why must have the special square and then have ans?
 » 7 months ago, # | ← Rev. 2 →   0 Interesting E & F
•  » » 7 months ago, # ^ |   0 Div2 D
 » 7 months ago, # |   0 Question E last time can help me see why my code runs incorrectly. I have been debugging for a long time, but I still haven't found the error. https://codeforces.cc/contest/1638/submission/146658516
 » 7 months ago, # |   0 My solution for C. First build the graph and then run dfs to get the number of connected components. In order to build the graph, I iterated from left to right while storing the maximum. Then at each node i, I would store the minimum value in the range [i + 1, n — 1] using prefix sums. I would then add an edge between the current node and the maximum node, and the maximum node and the minimum value found with prefix sums. I used an adjacency set to weed out duplicate edges and then converted it to an adjacency list to run DFS on.
 » 7 months ago, # |   +1 Another way to do c:notice that if we have two elements where the left one is greater than the right one they are connected and all the elements in between them are also connected to them. Start from the left and keep the maximum element in the current segment and the minimum element in the remaining segment. If our maximum in the segment is less than the minimum in the remaining suffix then we must stop and create a new segment from the remaining suffix. Otherwise connect the minimum in the remaining suffix to our current segment and get the maximum of the updated segment
 » 7 months ago, # |   0 Another other way to do C: Notice that with any two adjacent segments a, b. MaxA < MinB. Also MinA < MaxA. Also MinB < MaxB. Basically this means we can be sure that for any segment A to the left of B MaxA min of suffix. Why? Well for anything to be connected between the prefix and suffix this must be the case since this is like worst case. And since we split on a segment they will be connected. But if we have max prefix < min suffix we cannot connect them. This means we must be splitting between two segments. Ok so for each prefix/suffix we can just check this condition and then our answer is just the number of these splits + 1.