atodo's blog

By atodo, 5 months ago, In English

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.

1638A - Reverse

Hint 1
Hint 2
Hint 3
Tutorial
Feedback

1638B - Odd Swap Sort

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

1638C - Inversion Graph

Hint 1
Hint 2
Hint 3
Tutorial
Feedback

1638D - Big Brush

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

1638E - Colorful Operations

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Feedback

1638F - Two Posters

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.

 
 
 
 
  • Vote: I like it
  • +160
  • Vote: I do not like it

»
5 months ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

Thanks for fast editorial and the wonderful round! This is the fastest editorial I've ever seen.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      I also can't click on submit sometimes and during hacking, each submission takes around 30 seconds to load which is annoying.

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

:holyfrick: That was lightining fast .. Thnx for the hinted editorial !! helps a lot in upsolving :)

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Can someone give reasons for why D was a bad problem?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    couldn’t solve = bad ig. I liked it, felt it was interesting

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked the idea of voting the favourite problem. Cool idea!

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thanks to codeforces for providing fast editorial I was waiting for a solution to problem D

Valentine Day with codeforces has its own joy

»
5 months ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

I spend Valentine's day with codeforces but failed round. That is unrequited love((((

»
5 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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???:(

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me how did you make the edges in merge sort algo

»
5 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Where is editorial of problem A & B? Please, check tutorial section of A & B.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you to all of you. The contest was so fun and challenging for me. The editorial is lighting speed too!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Actually, $$$N = 10^4$$$ means to me that "only" $$$O(N^2)$$$ pass.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

python IO screwed me for D :(( limits were pretty rough

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same solution as editorial, just didn't use FastIO library. unfortunate

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The text is the editorial. It explains the solution of the problem.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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....

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I think this is a simpler approach for problem C:

Spoiler
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    double check problem D

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ah it's C... my bad. Thank you man.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You mean problem C

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That does work.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

VIDEO EDITORIAL FOR PROBLEM B : VIDEO_LINK

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone help me find why I got TLE for problem A in this solution 146366602.

Unwanted info
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    scanner?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ?

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            When I changed from Scanner to BufferedReader, it passed. Submission — 146445635

            Thank you vdxz for your reply.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    My DSU solution passes, you can check it here 146394231

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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'.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solve() have difficult O(n ^ 2)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can this be proven somehow? Even I passed it using this but still have no idea why it works.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used DSU and merge_sorting.Here is my AC code 146425315,which is O(nlogn).Hope it will help you.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are getting TLE not because of DSU, but because of nested for loops.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is a similar problem that everyone (basically) use topo sort. Strange Printer II

      Mainly 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hackforces...

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Shit happens:

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think, when you change color you should utilize lazy array and add its value on a given interval which you consider.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

O(n) solution for B problem still failed with PyPy3? Tight constraints requires an extended limit for heavy languages such as python.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The intended solution for C is really cool.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C-Inversion Graph using Segment tree link

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Problem D had weak pretests

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain A? I'm dumb

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, You're not a dumb. You are just a beginner.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem C short solution -

Solution

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.)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this works like magic but my brain could never think an implementation like this :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you give me any logic behind this implementation??

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      For me personally, looking at the diagrams given in the problem's test case helped.

      Problem statement
      Example - to get familiarised with this problem:
      Important example that helped me get this idea:
      So,
      Additional examples to try, to make sure this works:
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C can be solved using sparse table 146448264

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Creating sparse table is actually not required. Since, you are always calculating minimums for a suffix, you can precompute all suffix minimums.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

A possible solution of C without using graphs or DSU or Stack or anything, just pure observation

solution
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it passed all the test cases if acc to you it will fail on any case then do let me know.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Only if connected components is 1 and n = 10^5. Use long instead of int.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

FML

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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].

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please, someone help me find why this code is giving RE? Here is the submission link: https://codeforces.com/contest/1638/submission/146451668

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the tips! It would be great if you can share the name of your IDE :)

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Qt Creator. But I think any modern IDE will have similar functionality.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's my C solution, O(n) time O(1) space: 146453148

Logic : 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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???

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've never thought that i will get the editorial this much fast.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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 
    
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
5 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem C is just a sub problem of 1270H - Количество компонент

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Good contest , especially considering no matter what you do you will always pass pretest C

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 :)

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial came out so fast! thank you!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
**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.com/contest/1638/submission/146382565)
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved the contest, Big Brush was a really good problem.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody help me why my program is giving TLE in test case 4 ?? program link 146482560

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    instead of endl use "\n", TLE is due to slow output, my solution was also getting TLE due to same issue.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Loved C because it was misleading to use dsu at first

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is an my solution to C without dsu or stack

https://codeforces.com/contest/1638/submission/146419135

Intuition :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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1638/submission/146489157

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B solution is very very good ! thankss

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give me simple and understandable code for problem B

»
5 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem B can be solved by finding the minimum on the suffix.

Submission: 146422034

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest!! really nice problems. Short story and clear statements.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com

Problems 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.

»
5 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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
»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Did I miss something? I'm talking about problem E.

SegTree

What's wrong with this solution? It's not cool, when you face with this kind of "problems" :/

P.S. tight TL for SegTree?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.com/contest/1638/submission/146576523

Edit: there is a smart optimization for this but its still kinda cool my brute force passed

Edit 2: i appreciate the hack :D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, are "dead ends" not possible? We can choose every possible square on each step?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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): 146596576

No 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 ✌️✌️

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Instead of using fast i/o you've mentioned, there is ultra light weight version (but slower a bit): 146387910

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

have any one could prove why must have the special square and then have ans?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Interesting E & F

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1638/submission/146658516

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

146678558

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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<MinB. Ok so if we imagine a split with a prefix and a suffix, if we have it split on a segment then we know that the max of the prefix must be > 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.

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Two alternative solutions for 1638E - Красочные запросы. (in some sense harder than in editorial!)

Solution 1:

Hint 1
Hint 2
Key insight
Hint 3
Hint 4
Solution 1

Solution 2 will require Hint 1, 2, Key Insight.

Hint 5
Key insight of Solution 2
Solution 2

By the way. Has anyone been able to pass following 'naive' solution?

naive solution
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cool solutions, but, to my mind, they are definitely harder than editorial one (:

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Additional optimization
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this worked (in c++) http://codeforces.com/contest/1638/submission/147594491 but this did not (in java) (getting TLE) : http://codeforces.com/contest/1638/submission/147593720 Same logic

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E can anyone tell me prove of time complexicity when we use on segemnt tree and stop at node of only on monochrome segments.

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For Problem D ( Big Brush ), Why am I getting TLE in Test Case 4?

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone help me understand lexicographical order in A? suppose n = 11, and these 2 permutations:

A:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

B:[1, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10]

isn't B lexicographically smaller than A? if we are using dictionary ordering 1 comes before 2, so putting 11 at index 1 should result in a smaller order, no?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got a idleness limit exceeded in C can someone help me My Submission

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

.........