atodo's blog

Codeforces Round #771 Editorial
By atodo, 3 years 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

Comments Comments (122)
| Write comment?
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
    • »
      »
      »
      3 years 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.

      → Reply
»
3 years 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 :)

→ Reply
»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
»
3 years 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

→ Reply
»
3 years 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((((

→ Reply
»
3 years 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???:(

→ Reply
  • »
    »
    3 years 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)

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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!

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years 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??

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years 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
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    double check problem D

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You mean problem C

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That does work.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how?

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        solution boils down to

        for(1...n)
{
max=max(max,a[i])
if(max==i)ans++
}
        → Reply
»
3 years 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
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    scanner?

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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.

→ Reply
»
3 years 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!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    My DSU solution passes, you can check it here 146394231

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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'.

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

          You hadn't used DSU. If you remove all the dsu parts the code still works.

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solve() have difficult O(n ^ 2)

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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)$$$.

          → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hackforces...

→ Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Shit happens:

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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$$$.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The intended solution for C is really cool.

→ Reply
»
3 years 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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Problem D had weak pretests

→ Reply
»
3 years 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.)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C can be solved using sparse table 146448264

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

FML

→ Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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].

    → Reply
»
3 years 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.net/contest/1638/submission/146451668

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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 :)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
3 years 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???

→ Reply
»
3 years 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)?

→ Reply
  • »
    »
    3 years 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
    → Reply
    • »
      »
      »
      3 years 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

      → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Problem C is just a sub problem of 1270H - Number of Components

→ Reply
»
3 years 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

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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 .

    → Reply
    • »
      »
      »
      3 years 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 :)

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years 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.

→ Reply
»
3 years 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
→ Reply
»
3 years 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
BIT

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

P.S. tight TL for SegTree?

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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.net/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

→ Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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 ✌️✌️

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Interesting E & F

→ Reply
»
3 years 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.net/contest/1638/submission/146658516

→ Reply
»
3 years 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

→ Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
»
3 years 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
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Additional optimization
    → Reply
»
3 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.........

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1638/submission/165944078

Here's my (probably overcomplicated) implementation of E using only a lazy segtree which ACs, centered around the intuition to keep track of maximal monochromatic segments. Though, I don't have a rigorous proof of its time complexity.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why my solution for B is failing? I am using the same logic as the editorial but the implementation is different. For each parity, I am checking if the current element is the greatest element of the current parity or not. If it is not, then the answer is NO, else the answer is YES. 172802388

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C. Inversion Graph — my DSU working approach 198748310

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved E using offline query. I iterate from 1st element to the )last element while maintain a set store about color changes from the first query to the last query. When moving to next element I update the set (add color or remove color, also update value for each timeline using fenwick tree) Complexity is about (n+q)log2(n)

→ Reply