11

Codeforces Round #877 (Div. 2) Editorial

 1 year ago
source link: https://codeforces.com/blog/entry/116995
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

By jdurie, history, 9 hours ago,

9 hours ago, # |

fast editorial!

  • 7 hours ago, # ^ |

    fast comment to get fast upvotes!!

    • 63 minutes ago, # ^ |

      Fast reply to get fast upvotes!

9 hours ago, # |

very observational tasks....found c easier than a and b

  • 9 hours ago, # ^ |

    What's your output for 3 7 ?

    • 9 hours ago, # ^ |

      ← Rev. 2 →  

      +22

      n and m are bigger than 3

      • 9 hours ago, # ^ |

        Wtf!!!

        I have wasted more than a hour finding solution for this case.

        • 8 hours ago, # ^ |

          it happens :). I started writing down key points and constraints before attempting.

    • 9 hours ago, # ^ |

      although n,m>=4.

      i think there is no solution for 3 7.

      • 9 hours ago, # ^ |

        There is 1 2 3 4 5 6 7 9 10 11 12 13 14 8 17 18 19 20 21 15 16

        • 9 hours ago, # ^ |

          length should be 21

          • 9 hours ago, # ^ |

      • 8 hours ago, # ^ |

        The only sizes that aren't solvable are 2x2 and 2x3. Below are some solutions for other small sizes:

        2x4
        2x5
        2x6
        2x7
        3x3
        3x4
        3x5
        3x6
        3x7

    • 8 hours ago, # ^ |

      Making sure that columns with difference 3 aren't adjacent

      • 3 hours ago, # ^ |

        if any of the side has even size. answer is pretty easy. try to proveit for 9 * 3.

9 hours ago, # |

difficulty difference of C and D are so Huge

  • 9 hours ago, # ^ |

    I can't even solve C :(

    • 9 hours ago, # ^ |

      i have solve C before A.

      • 9 hours ago, # ^ |

        I spent about 1.5 hours, but I cannot come up with any ideas :(

        • 9 hours ago, # ^ |

          ← Rev. 2 →  

          +2

          sometimes it happen, like today i cannot figure out solution for A faster.

          • 8 hours ago, # ^ |

            Exactly in the same situation, A took me stupid amount of time to figure out, B was decent, C was very easy.

        • 60 minutes ago, # ^ |

          Same happened for me with B

      • 8 hours ago, # ^ |

        Sorry for my bad English. Can you please share some problems like today C. I always struggle in such type of question.

9 hours ago, # |

← Rev. 2 →  

+1

Forgot the case s[1] = ')' or s[n] = '(' ToT

9 hours ago, # |

Fast tutorial

9 hours ago, # |

fast editorial!!

9 hours ago, # |

Good contest and fast tutorial! But I can only solve one problem.

  • 9 hours ago, # ^ |

    ← Rev. 2 →  

    +1

    hope u will do better in upcoming contests.

    • 9 hours ago, # ^ |

      Thank you for your encouragement! I'll keep up the good work! I hope I can complete two questions in the next competition.

      • 8 hours ago, # ^ |

        I had exactly the same problem, I suggest you solve problems from other websites especially leetcode. Also learn about prefix arrays, and the very basics of DP and Graphs. Good Luck :)

9 hours ago, # |

fast editorial!

  • 9 hours ago, # ^ |

    need D and E.

  • 8 hours ago, # ^ |

    The title of B video is incorrect.

9 hours ago, # |

fast editorial!

9 hours ago, # |

I've had this argument with quite a number of people, but can you explain how you can approach C without brute forcing random patterns?

  • 9 hours ago, # ^ |

    ← Rev. 2 →  

    0

    make difference between adjacent numbers in every row is 1.

    for column, try to make difference a even number if any of n or m is composite otherwise multiple of m.

9 hours ago, # |

A good idea about solving problem D! I didn't expect the implementation of D to be so simple.

9 hours ago, # |

I found it cool that problems were not that standard, unlike usual div2s.

  • 9 hours ago, # ^ |

    Please show me a recent div2 that had "standard" problems.

    • 9 hours ago, # ^ |

      ← Rev. 3 →  

      +11

      Well, yesterday's contest for example (C was implementing a simple recursion and D was standard DP) and many others, and, in general, every educational round. I feel Div2 medium/hard problems are usually standard.

9 hours ago, # |

Short solution of A — E. Impressive

9 hours ago, # |

I enjoyed solving C most, it was a nice problem !

9 hours ago, # |

Hit or miss forces

  • 8 hours ago, # ^ |

    Yeah, same.

  • 8 hours ago, # ^ |

    yeah lgms just have better luck so they hit more often

  • 7 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Man went from 129th to almost 8000th in mere 24hrs dead emoji

    I felt the same, btw

    • 7 hours ago, # ^ |

      lol opposite for me :alive:

      • 7 hours ago, # ^ |

        You forgot to be become CM

      • 5 hours ago, # ^ |

        Well done!

9 hours ago, # |

Almost solved E once again :(. Didn't notice that you don't need the values of array to count . Enjoyed the round, although I can see there are not so many people who have the same feelings

  • 9 hours ago, # ^ |

    Yeah For D. almost solved.

9 hours ago, # |

Anyone please help me out how to solve B and C questions in Div2. I got stuck many times in it.

I had practice many questions but still am facing this issue.

  • 9 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Try participating in more contests and even virtual contests. And upsolve after the contest.

    • 9 hours ago, # ^ |

      ← Rev. 2 →  

      0

      Thanks a lot.

      Can you suggest some more tips to improve skills in CP and rating?

  • 8 hours ago, # ^ |

    I had exactly the same problem (I still struggle with 3 sometimes), I suggest you solve problems from other websites especially leetcode. Also learn about prefix arrays,modular arthimatic and the very basics of DP and Graphs. Good Luck :)

    • 8 hours ago, # ^ |

      Sure, I will learn and implement.

      Thanks!

9 hours ago, # |

Is D well known trick? Why so many ACs...

  • 8 hours ago, # ^ |

    editorial seems like magic but trust me its not

    if you try to consider what happens when (( occurs, its trivial

8 hours ago, # |

Was I the only one to submit a brute-force recursion-with-backtracking solution for problem C?

The worst-case time complexity is high, but it runs fast in practice because the problem is not very constrained.

8 hours ago, # |

Perfect editorial

8 hours ago, # |

Is it just me who enjoys Ds that are more algorithm and implementation heavy and not Ds that are like "because math something something cout << i-am-clown is always the correct answer"

  • 7 hours ago, # ^ |

    I too enjoy not thinking and getting my way through life as such. Unfortunately, this is often not possible.

    • 6 hours ago, # ^ |

      based reply, honestly these people make me so mad, they just dont want to think, and then get annoyed when problems need you to think

      • 6 hours ago, # ^ |

        Is there any problem that doesn't require you to think?

        • 6 hours ago, # ^ |

          i think you know what i meant "needs you to think".

          div2 abc problems that wud need ds would definitely need you not to think. (maybe if using easier ds)

          I cant find a segtree problem fit for div2C difficulty aside from the trivial ones.

          the core of the issue is : you cant have easy problems with data structurs because beginners should not be expected to have much knowledge of them. as maroonrk puts it, a problem should have thinking >>> knowledge. I would like to see a div2C in a 6 problem contest which uses ds and still follows that above principle

7 hours ago, # |

Can someone please explain why this brute-force idea for A is incorrect? 0) if there is a negative integer that is obviously the answer.

1) insert all the elements in the array in a set. This set keeps track of all the elements which is impossible to get through the absolute difference of any 2 elements in the array.

2) Use nested for loops(n^2) and iterate through the array(not set) and check the absolute difference of every 2 elements in the array. If this absolute difference is present in the set, remove this from the set.

3) the element still remaining in the set, this must be one of the possible answers because of the fact that this element was impossible to get through any 2 elements' absolute difference.

code link: https://codeforces.com/contest/1838/submission/208442311

  • 7 hours ago, # ^ |

    hello,

    first of all — set is not good thing if you have equal numbers.

    second, you should check in your solution that removed element is not the one of the elements that you have considered as a difference.

7 hours ago, # |

← Rev. 2 →  

+4

Here's my thought process for ABC, hopefully it helps people understand how to come up with the solution. Sometimes it seems unintuitive but it is possible.

A: We notice that negative numbers are abit sus from the sample testcases, how come theres only 1 or 2 negative numbers? Then realise because we are taking absolute difference the rest of the numbers are positive, so negative numbers can only appear at the very start => meaning, if we see a negative number we just print it. Else, there is no negative numbers, what to do? If theres no negative numbers, because we are taking absolute difference we can just take the maximum value in the array, as we can only get smaller values in the future by taking absolute differences. Therefore: if min < 0 print min, else print max

B: Ok we want to minimise the number of permutation subarrays => What is the minimum value? Can we always get 1 and [1...n] as the only permutations? Ok idk if its possible, let me check the testcase: It seems that this is always possible after checking all the testcase. Therefore, we want only 1 and 1...n as the permutations, how to do so? See that if we place 1 and n beside each other, it may be good because every subsequent subarray afterwards that contains [1,n] will never be a smaller permutation. However we see from the testcase that ...2 1 n is still bad, because we only need 1 and 1...n as the permutations. 2 is pesky, so let us place it away from 1 so that we can never get 1,2 as a subarray. Ok how to do so? realise that 1, n, 2 and 2, n, 1 will be correct, so let us just make this pattern and we can ignore the rest of the subarrays. We can ignore the rest because we will always have [1,n] together without any other permutations formed

C: Constructive, seems that many people are able to solve in the contest => Solution must be quite simple, aka spot the pattern or trick and the rest will fall out. Ok, seems that we need to find a simple solution, do not tunnel vision into the first approach you have! Try out a few different approaches and see which one is the most simple to implement and easier to extend: For example, I tunnel visioned into grouping all the even / odd numbers together, and then at the border of odd / even we need to make everything 1. Seems complex, so lets discard that idea (unfortunately I tunneled too hard into random ideas). Ok let us think of a very naive solution, for 4x4, we can try out 1 2 3 4 ... 14 15 16. Wow seems like it works, is it simple? yes, is it easier to extend? Hopefully. Realise that for 5x5 this doesnt work. Key insight: Think of why it doesnt work instead of just trying out other random approaches. Ok it doesn't work because the next row is +m, and m is 5. Ok so how to make the rows better? If we just think of why it doesn't work, can we possibly modify or extend this idea to make it work? Turns out, if we make the rows +2m +2m and so on, it will not be prime. So: we can place the even rows at the top and the odd rows at the bottom to make sure this difference is indeed > m and a multiple of m.

Hope this helps

  • 7 hours ago, # ^ |

    the point of "Don't tunnel vision into the same approach" is really important. I was lucky to have got the right approach on the first try, usually I tend to stick to one idea a lot ;)

    • 7 hours ago, # ^ |

      ← Rev. 2 →  

      0

      Unfortunately I had all sorts of weird ideas like boxing the last column into the last m guys, zig zag, spiral, diagonals, grouping even odds together and making the borders 1, trying odd / even in a way that if n,m is odd we make the border zigzagged, making +4 +4 +4 and so on. If only I thought of simpler ideas I might have gotten it during the contest. At least I learnt something new I guess.

7 hours ago, # |

← Rev. 3 →  

+15

My solution for 1838D - Bracket Walk:

Observation behind the approach

Any even length sequence of the form ((...)) is always walkable because the beginning and closing consecutive brackets can always be retraced to make up a valid bracket sequence, no matter the content inside. Also this is the only format of incorrect bracket sequence which gives correct path on a walk. So we can take the largest possible string of this type and just check for the correctness of the prefix and suffix bracket sequence.

Also, the prefix and suffix string should be exactly of the form k*() for k>=0. Otherwise some consecutive brackets will occur which can't be corrected in a walk because consecutive brackets of opposing type won't cover for them.

Implementation:

Maintain two sets l and r storing indices of consecutive opening (( and closing )) brackets. Also maintain a data structure (segment tree) over the an array having +1 for ( and -1 for ). For every query, check the i-1 and i+1 index for index i being updated and update the sets l and r and sum-tree accordingly. To find the answer for each query:

  • If n is odd, then answer is always NO as mentioned in solution.
  • If both of l and r are empty, then check the whole array (index 0:n-1) for correct bracket sequence. Answer YES or NO accordingly.
  • If one of l or r is empty, then answer is NO.
  • Else consider the first index where (( occurs -say x (first element of l) and the last index where )) occurs -say y (last element of r):
  • If x>y answer NO.
  • If 0:x-1 and y+2:n-1 are correct bracket sequences, then answer YES, else NO.

To check the correctness of bracket sequence i:j, following conditions need to be checked:

  • If j<i, then trivially correct.
  • If odd sequence, then trivially incorrect.
  • Else, check sum[i:j]==0 and i==1 using sum-tree in O(logn)
  • Also check that none of indices of set l or r lie in range i:j, checking first and last elements suffice in O(logn)

Time Complexity O((n+q)logn)

Here's my solution using this approach, although I wasn't fast enough to implement during contest time: 208516428

  • 7 hours ago, # ^ |

    I got the exact same idea while solving D, I also knew we should use a segment-tree to implement it, but I have never implemented a segment-tree before, just know the concept. I should start learning these advanced concepts soon.

7 hours ago, # |

Hey .. Can someone suggest me a video to understand D , having a hard time warping my head around it

4 hours ago, # |

Hi, is there to way to download the test data for problem C? Pretty sure the code should work for all inputs but it keeps finding an error, I often make some stupid mistake in code but already removed 3 problems from it and can't find another.

  • 3 hours ago, # ^ |

    ← Rev. 2 →  

    0

    The problem is that your code (in some cases) swaps rows and columns. For example on test

    The code should output a grid with rows and columns, but your code outputs the following:

    Since the checker doesn't care about whitespaces (spaces, linebreaks etc.) but it is expecting integers per line, your output gets interpreted as

    which is obivously wrong.

3 hours ago, # |

during contest:

WTF is this, I hate this contest.

After reading editorials :

what a beautiful problems. How much more stupid I can be !!!

  • 69 minutes ago, # ^ |

    For me, this contest was a reality check of how stupid I am.

88 minutes ago, # |

can someone explain solution for c

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK