When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

DishonoredRighteous's blog

By DishonoredRighteous, 22 months ago, In English

Hello, Codeforces!

I'm glad to invite you to Round 791 which will start at May/14/2022 12:35 (Moscow time). Please notice the unusual time.

There will be 6 problems in the round. Round is based on Team Olympiad in Lipetsk which is being held for the seventh time. Problems were proposed and prepared by iakovlev.zakhar, Kon567889, iura, andr1y, Masha237, welleyth and me. I would like to thank Aleks5d and KAN for CF round coordination and testers: Um_nik, 353cerega, errorgorn, Stepavly, divanik, nnv-nick, 4qqqq, to be continued...

Of course, I'd like to thank all Codeforces team for Codeforces and Polygon beautiful platforms!

I also would like to thank golikovnik, egneeS, dshindov and Inessa Shuykova (Lipetsk teams' coach) for preparing other Olympiad problems that haven't been taken for this round.

Thanks to NEAR for supporting this round, details can be found in this post.

Note that if you are an official participant of the Olympiad, you are not allowed to participate in this round.

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 3000$$$.

UPD.2 Congratulations to winners!

Official participants:

  1. xiaoziyaooo

  2. StickyFingers

  3. mybing

  4. huangweiliang

  5. NewPC2022

Unofficial participants:

  1. SSRS_

  2. leaf1415

  3. uwi

  4. maspy

  5. TripleM5da

UPD.3 Editorial is available here.

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

| Write comment?
»
22 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Team based round... interesting, will participate.

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

Users rated >= 2100 can't seem to register for the round?

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

I like when contests are at this time. (5:35 AM, Saturday for me) It forces me to not sleep in and be a lazy bum

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

hopeforces

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

Will the problems be a different style than regular rounds?

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

i see olympiad i upvote (unless its russian, then i just comment)

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

    It's a Russian olympiad. You didn't upvote?

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

CF 791 -> ABC 251 -> Code Jam Round 2

No clashes with 20-25 mins break each. Sweet. Thanks for the unusual time :)

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    In addition, there is a Leetcode contest at the usual time of codeforces rounds.

»
22 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Is it only me, or does everyone feel that contest at an unusual time has less participation than the usual time contest? Hence have less probability for the rating to increase. I know we should not give contest for rating, but still...

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

This round will be hard. Good luck everybody!!!

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

    Hard like the most of unusual time contests but the standing will be much greater then other rounds so rating will also increase more then other contests. Point to think! And Wishing good luck to you all

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

How to know if a contest is unrated for me, I am new to the cf and could not find any official post on this info yet ?

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

    For gray users all the rounds (expect Div.1, because you can't register for it + some rounds like april fools contest) are rated.

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

      thanks for the info! does that mean div 3 users can participate up to div 2 rounds and also not to div 4 rounds as well?

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

        See, as a grey coders can give div, 2, 3, 4, and all of these are rated for them. I think you are trying to think of these contests in terms of CodeChef contest, those two are pretty different.

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

The unusual time strikes back.

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Why so unusual time? anyone any idea

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

    There is olympiad in this time, round based on it. The unusual time is to avoid cheating

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

    There's also a codejam round on the usual time.

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

Please add the contest link in the blog.

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

If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking

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

    First,it's rating.It's because they would like to practice since there is no div.1 for it.

»
22 months ago, # |
  Vote: I like it -14 Vote: I do not like it

"i_am_completely_useless for being completely useless." -- Sakura :))xD

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

Thank you for the unusual time!

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

excited for this contest, go go go !

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Unfortunately, I need classes at that time, so I can't participate in this contest.

»
22 months ago, # |
  Vote: I like it -10 Vote: I do not like it

QueryForces

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

Pretests in C must be extremely weak

  • »
    »
    22 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    edge cases ?

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

      first q/2 queries of type 1 having x = i , y = i for i 1 to q/2

      Then next q/2 queries of type 3 having x1 = 1 , y1 = 1 , x2 = n , y2 = n .

      If somebody checked type 3 queries linearly from x1 to x2 , or y1 to y2 then Complexity will be O(Q*N) and there are many such accepted solutions

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

waiting for contest finish to get solution for problem E

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

    saw your dp solution of c question , edu round :) love u bro

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

    You can find contribution of each subarray.

    Let us focus on some subarray $$$s$$$. There exists a mask $$$m$$$ for $$$s$$$ such that $$$s$$$ will contribute to the answer iif mask of query is supermask of $$$m$$$.

    $$$m$$$ gets fixed because we have the restriction that if $$$s[l] != ?$$$ and $$$s[r]=?$$$, $$$s[r]=s[l]$$$ ($$$r=|s|-l+1$$$).

    Now for subarray $$$s$$$ to contribute $$$1$$$ to the answer, some $$$?$$$ get fixed and rest $$$?$$$ are flexible. Suppose we have $$$freq$$$ flexible $$$?$$$. Finally $$$s$$$ will be contribute $$$1$$$ to answer in $$$|t|^{freq}$$$ arrays.

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

      There are $$$2^{17}$$$ masks, and len $$$|t|$$$ is up to 17, and also we need to sum up all summasks foreach mask.

      All my tries did run like more than a minute...how to do that right?

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

        Say mask of query is $$$q$$$.

        Now you need to check contribution of all masks $$$m$$$ such that $$$q&m=m$$$. You can traverse over all submasks in $$$O(3^x)$$$ operations(here $$$x=17$$$).

        Suppose we have a $$$dp$$$ array, such that mask $$$x$$$ will contribute $$$dp[x][i]$$$ to the answer, if $$$q&x=x$$$ and $$$__builtin_popcount(q)=i$$$. So you calculate this $$$dp$$$ while traversing all subarrays(fixing middle position and moving sideways).

        You can precompute answer for all masks.

        My submission

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

          oh thanks! I forgot about this trick to iterate over submasks

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

          actually you can solve it in $$$O(2^{17}\times 17^2)$$$ by using SOS dp or fast walsh transform.The solution is similar to yours.

          My submission

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

Why Segment tree solution is giving TLE in C. :(

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

Used a single loop in Problem-B, still exceeded the time limit, is it me or python at fault here?

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

Thanks to iura for setting F! I really enjoyed solving it during testing. Here is my alternate solution to F that works for much larger constraints.

Let $$$S_i$$$ be sets containing all representatives of all arrays $$$a$$$ of size $$$i$$$ and $$$C_i$$$ be the set of cliques of size $$$i$$$. When we talk about clique, we are talking about cliques on the graph where we draw the edges as $$$(u_i,v_i)$$$. Also when we talk about arrays, we will basically refer to its equivalence class, so treat $$$a$$$ as the representative.

Take some array $$$a$$$ and let $$$s_a$$$ be the possible values of the first element of $$$a$$$ after some operations. Note that it is necessary that $$$s_a$$$ is a clique because otherwise, we are not able to swap all values in $$$s_a$$$ to the start of $$$a$$$.

Let us suppose that we know $$$S_j$$$ for all $$$j<i$$$ and now we want to find $$$S_i$$$. For all arrays $$$a \in S_{i-x}$$$ and $$$c \in C_{x}$$$,put $$$(c,a)$$$ into $$$T_{x}$$$. That is, we want to think about arrays $$$a \in S_i$$$ as the concatenation of some clique and another array. Unimportant remark: $$$c \subseteq s_{c+a}$$$.

However, the problem with this is that are multiple ways to make a certain array. As a simplest example, consider when we can swap $$$(1,2)$$$ only. To make array $$$[1,2,3]$$$, we can split it into $$$([1,2],[3])$$$, $$$([1],[2,3])$$$ and $$$([2],[1,3])$$$. Of course, we do not want to double count.

Let us consider some $$$a' \in S_i$$$ where $$$k=|s_a|$$$. There are $$$2^k-1$$$ combinations of $$$c+a$$$ that produces $$$a'$$$. Every subset $$$c$$$ of $$$s_a$$$ corresponds to a $$$(c,a)$$$ tuple, and there are obviously $$$\binom{k}{x}$$$ such subsets with $$$|c|=x$$$, so $$$\binom{k}{x}$$$ tuples in $$$T_x$$$ corresponds to array $$$a'$$$.

One can see that $$$|S_i|=|T_1|-|T_2|+|T_3|-\ldots$$$ by looking at the individual term of some $$$a' \in S$$$ and noticing when only considering tuples that correspond to $$$a'$$$, we have $$$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \ldots =1$$$ on the right hand side. Note that by definition, $$$|T_x|=|S_{i-x}| \cdot |C_x|$$$.

Let the number of digits be $$$d$$$. If we let $$$ans_i$$$ be the answer for length $$$i$$$, we have the explicit recurrence $$$ans_i=\begin{cases} 0,& \text{if } i < 0 \\ 1, & \text{if } i=0 \\ \sum\limits_{j=1}^d ans_{i-j} (-1)^{j-1}|C_ j| & \text{if } i>0\end{cases}$$$.

We can find all $$$|C_j|$$$ in $$$O(2^d)$$$ by brute force. To do this, we check if some mask $$$bm$$$ is a clique in $$$O(1)$$$ by taking an arbitrary bit $$$b$$$ from $$$bm$$$, checking if $$$bm \oplus b$$$ is a clique and that $$$b$$$ is connected to everything in $$$bm \oplus b$$$. Since we can solve linear recurrence in $$$O(d \log d \log n)$$$, we have total complexity of $$$O(2^d+d \log d \log n)$$$ but it probably does not matter what algorithm we use to solve the linear recurrence since there is no way it is going to dwarf the $$$2^d$$$ term.

Can we find all terms of $$$|C_j|$$$ faster than $$$O(2^d)$$$?

Code: 157227780

»
22 months ago, # |
  Vote: I like it -16 Vote: I do not like it

segment tree forces

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

    Which tasks required segment trees? I only looked at A, B, C and D and none of them required it (or anything similar like Fenwick)

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

      B and C were doable using segment trees

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

        My solution to C tle'd using Fenwick tree any suggestions ?

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

          ++ I used segment tree my solution got tle'd too. I don't know where did I go wrong . :(

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

            You should use int instead of long long whenever you can. Also it'll be good to use the fast I/O:

            cin.tie(nullptr);
            ios::sync_with_stdio(false);
            

            Finally if it doesn't work, use a fenwick tree as it's constant factor is way better than a segment tree's

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

          You can refer my submission: 157174605

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

            Hey winterfire can you check my submission and let me know what you think ? submission

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

              This solution would get WA even if it didn't TLE. Despite that, you need to use fast I/O. Try adding this:

              ios_base::sync_with_stdio(false); cin.tie(0);

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

                Oh lord thanks Restricted I am using this template from a long time never noticed fast i/o wasn't included that's why I was wondering my submission for B took 1.5 sec but is just simple operations..

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

          I did it using segment trees. Create two seg trees for handling rows and cols. If a rook is placed/removed at cell x, y then update the xth row and yth col. For query of type 3, if the bitwise AND of rows x1 to x2 > 0 or cols y1 to y2 > 0 then answer exists.

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

          Mine passed in 290ms 157157585

          I'll try to see why your sol TLE'd

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

          your solution is wrong

          Consider a case with a 5x5 grid

          RRRR.
          R....
          .....
          .....
          .....
          

          If I query on the whole grid, the answer should be No but your code will output Yes because you shouldn't add 1 everytime you place a rook. See my explanations here for more details:

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

            Thanks bestial I got it its wrong , I think TLE is because of fast i/o but if you see any other issue with BIT implementation let me know

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

              It seems ok but for more safety I would add ++index b efore computing any answer for queries (this is because the bit trick you use doesn't work for 0). Adding the ++index would allow you to use the BIT like it's 0-indexed if you want. You only need to make sure that you allocate extra memory but you already did that :)

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

        yes ofc you can use segment trees as arrays

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

        however actually B can be solved in $$$O(n+q)$$$ without using segment tree

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

      Maybe B and C.

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

n = 2 should have been in the samples in A :(
Btw, I wonder how many people solved B using segment tree

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

    I use segment tree with lazy propagation.

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

      You can do it in an easier way.

      You want to perform three types of queries

      • set all the elements to x

      • change the value of an element

      • compute the sum of the array

      If you don't have the "set all the elements to x" queries, you can just compute the sum at the beginning and when you change the value of an element you know how the sum will change.

      The only problem is that if you performed a "set all the elements" query, the value of the element might not be the one you stored in the array.

      To handle this, notice that the latest query will give the value of the element.

      So you just keep track of the time when the set query was applied and when the change query of each element was applied.

      Code: 157146130

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

      Overkill. Could be easily solved in O(n + q) via storing the last occurrence of updating the whole array and the last occurrence of updating an index for each index.

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

I tried to hack C with 2e5 queries and it said input cannot exceed 256kB, what T_T

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

    You can use a data generator.

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

      Will learn how to use that before the next contest, till then pain

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

        Hacking with a generator is quite simple. Just output the test case you want.

        For example, a test generator for B

        Some things to note are: Don't output any extra spaces or blank lines (e.g. after arrays), and the test case should always end with an endl character (e.g. cout << n << '\n'; instead of just cout << n;). Basically you should follow test standard practices strictly.

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

how to solve c ? some one pls tell me your approach :* (i've tried to do it with brute force by making maps in the last 10 min I was knowing that it gonna get me tle :D ) so how can we solve it:*

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

    If you have at least one rock in a row set the row's value to 1. If you you have at least one rock in a column set the column's value to one. Now you wanna know if the sum of the columns in [x1,x2] is exatly x2-x1+1 or if the sum of the rows in [y1,y2] is exactly y2-y1+1. This can be easily done with a segment tree

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

      hey bro just need a favor from you basically you are a specialist you might be having a good idea about cp so can you tell me after seeing my profile and rating that should I learn segment tree or not cause some of my seniors were saying to me that to learn segment tree your rating should be at least 1500 or something but from last few contest I'm seeing that there is one question of segment tree between a,b,c and you might remember that div4 contest which just held few days ago in it also h2 problem was solved using segment tree so can u suggest me,that when should I learn about it or i should wait for few months :*

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

        I don't see why not. It's not that hard of a concept and it makes you understand some other CP concepts better. At least know what it does and how to use it.

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

        You should learn to use ordered set. Today's C and div4's H2 could be easily done with ordered set.

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

          but in java there is nothing as ordered set:* can u suggest any alternative:D

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

            I don't think there is any alternative in java. You have to use fenwick or segment trees.

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

    Think of a way to maintain the empty rows/cols, after that when they ask you to check the subrectangle try to find if there is a row and a col that is empty and satisfy this condition: x1 <= row <= x2 && y1 <= col <= y2, if you found such a row and a column then the answer is no otherwise the answer is yes

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

      I solved it using sets and binary search

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

        but how who can we find it with bs:* can u elaborate

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

          Here's my solution https://codeforces.com/contest/1679/submission/157198959

          The idea is to keep track of the empty rows and empty cols, initially everything is empty so we will insert into our rows and cols the numbers from 1 to n;

          Rows = [1,2,3,...n] Cols = [1,2,3,...n]

          Now anytime we insert a rock to some (r,c) that means the row is no longer empty and the col is no longer empty, so we will remove r from our Rows set and c from our Cols set.

          Now, how can we know that this row/col is empty? we can keep track of the rocks count in each row and col, once the count for a row/col becomes 0, this means we need to insert it into the corresponding set.

          Take a look at my solution, and hopefully, you will understand what I mean.

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

        I used Ordered Set to solve C.

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

    When a rook is inserted on (r, c) notice that it covers all cells on row r and col c

    Let's store for each row if it's already covered by a rook Do the same for columns

    Now the subrectangle queries ask if for each cell, either their row or their col is covered

    A subrectangle query consider a range of rows and cols

    What happens if a column is not covered ? Basically you need all the rows to be covered for the cells of this column to be covered

    (same argument in reverse)

    This way we show that the answer is "Yes" iff all the rows or all the cols are covered

    Let's say we put a 1 when a row is covered

    We just need to range sum over the range of rows and make sure the sum is equal to the length of the range

    Same for cols

    To handle rooks removal, we count for each row the number of rooks covering it

    When this count reaches 1, we add one in our segtree/bit

    When it reaches 0, we add -1

    Code: 157157585

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

How to solve D? My idea is to go through the nodes in increasing order and activate them one by one. Once I activate them I want to know if a strongly connected compononeted is activated, this means that I am done regardless of what K is. This is easy to do. The hard part was knowing whether a path that is K long in is created. How do you do it?

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

    The idea for D is fairly simple (and a good learning exercise if you aren't familiar with the "trick"). You just need to combine 3 independent pieces: Binary Search on answer, Cycle detection and Longest path in DAG.

    Since we are asked to minimize the maximum value of some quantity, it's natural to think in terms of binary search. However, this can be a trap if the function is not monotonic. To work around it, a clever way to define the predicate is to use the at least keyword. Instead of asking whether an answer with value val exists, we ask

    Does an answer with value at least val exists?

    With this keyword, it's fairly obvious that existence of at least val implies the existence of at least all value less than val as well.

    To verify a predicate, you can ignore all vertices with value > val while performing a DFS. (You might've seen this in problems asking you to find the maximum value less than threshold on a path between 2 vertices in a tree). After ignoring these vertices, if the resulting graph contains a cycle, it means you can travel it infinitely many times. If not, it is a DAG. Then, you just need to find the longest path on this DAG and verify if it's at least $$$k - 1$$$.

    Note that you can do all of this in a single DFS (and without explicitly creating the new graph).

    Code

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

      Of course you do binary search how did I miss it. Eeh, I feel so dumb haha. Thanks a lot!

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

        You don't need to feel dumb, it happens not to be able to solve a problem!

        What you should learn from this is that problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)

        You can find some similar problems on usaco guide:

        Wormhole Sort

        MooTube

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

          That's so nice of you to say thank you! I will definitely be checking the problems you suggested later.

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

      Nice explanation. You made it look so simple. Thanks.

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

      damn I only knew binary search

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

      Amazing idea!!!

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

      thanks a lot

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

    Binary search for the answer. And for each check, we could search for cycle or a longest chain in the new DAG, which we needn't really create a new graph but just judge the number on each vertex

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

    What exactly D asks for?

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

      Given a directed graph, find paths such that there are K vertices in it. Choose a path such that the maximum value of the vertex is the minimum possible. Output this value.

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

    We can use binary search to find the answer.

    When we are checking if there exists a path of length k with nodes whose values are less than or equal to 'x'(current binary search value), we consider the subgraph 'C' formed by the nodes whose values are less than or equal to 'x'. Now we have two cases. 1. There is a cycle in this subgraph C, the answer is true for this x in this case. 2. There is no cycle => subgraph is a DAG. Find max path length using DP and check if the max path length is >= k. The answer is true for this x if that is the case.

    Steps 1, 2 are of O(n) complexity each. We do them for a total of O(log(max(a[i]))). Therefore total complexity is O(n*log(max(a[i]))). code.

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

What was the approach for problem A ?

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

    The max number of cars is calcualted using the maximum number of 4 wheel cars. The min number of cars is calculated using the maximum number of 6 wheel cars. We need to consider some edgecases, like odd numbers.

»
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

E was nice construction problem, I like it.

But whole contest was spoiled by unclear problem statements, except A there was not a single one I clearly understood. Had to decipher and guess the meaning of all texts, annoying.

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

me about to solve A in 6 mins.

1st error (Not considering the edge case of n == 2) be like: "I will make you pay"

2nd error (forgetting to return after printing -1) be like: "LMAO NOOB"

And that's how 'A' ruined my LIFE :)

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

Can anyone tell me why do i get TL in B

https://codeforces.com/contest/1679/submission/157177370 ?

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

    I guess tot = b[1] * n is $$$O(n)$$$

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

      It is just a multiplication of two integers.

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

        Sorry for the previous nonsense reply, I just read too fast and thought you were creating a list. I got your code accepted by reading the whole input at the start.

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

          Great. Is it fine though, that such optimizations are needed for code to be accepted. Or it is a problem of a contest?

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

            I agree this should not be needed. But I had a look at some of the accepted Python solutions and it seems they write at the start input = sys.stdin.readline which I guess is way faster. Using that your code also gets accepted, so you should write that and keep reading input as you did, which is not a big deal.

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

    Yeah this is frustrating. It's only a single linear loop. https://codeforces.com/contest/1679/submission/157146581

    I also tried the standard Python 3, it just barely passes the pretest but of course it is TLE again on the system test

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

thanks for the early end round,that i could see RNG's exciting game:(

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

This was a super cool round with nice algorithmic problems ! Congrats to the authors :D

Here is my advice about each problem

A
B
C
D

I didn't solve E/F so I don't really have an advice but they both look interesting

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

    how to solve d?

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

      Problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)

      So let's binary search over the maximum node you will walk on (I don't explain why you can binary search here but you can try to prove it as an exercise)

      Now we need to check if it's possible to find a path of length k (in terms of nodes) using only nodes with value <= MX

      Let's build a new graph. It'll be the same graph as the original one but only with nodes having value <= MX. We now want to find a path of length at least k. Notice that if the graph has a cycle, we can just keep moving in the cycle and get a path of length at least k. If the graph doesn't have any cycle, it's a directed acyclic graph and you can use dp to compute the longest path in it.

      Code: 157170838

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

Since I am poor in English, can anyone explain what is the difference between loops and cycles? Why "loop" is equal to "self-loop" instead of "cycle" in D?

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

Can anyone please explain a solution for Problem B? (without using segment trees)

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

    Yes! You can read about it right here

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

    hint: keep timestamp of modifing for each item

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

    Someone really wrote seg tree there?)

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

      Me who can't be bothered to think of a linear solution... I'm a simple man, I find any passable solution, I type it up

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

    Store the initial sum in s.No need to store the array.Maintain a map instead of all the type1 changes made to the array after the recent type2 operation.Maintain a variable l initialized to 0, to store the x value of the last type2 operation.So everytime you get a "1 i x" just look into the map if some change was registered at pos i by "m.count(i)", if it's not zero then update s as s+=x-m[i], else if no change was registered the cell contains the last type2 change hence s+=x-l.Now when you encounter type2 operation clear the map and update the variable l to the new x and the sum s to n*l. Link to my not so legible code

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

Can someone please explain why I am getting TLE in C? https://codeforces.com/contest/1679/submission/157197783 I am using hashing to figure out when to add/delete row/column in sortedset(made using Fenwick Tree). And to find out if the whole sub-rectangle is there, I just subtract indexes with lower_bounds of x1,x2 in row sortedset and y1,y2 in column sortedset and compare it with difference of x1,x2 and y1,y2. It should be O(nlogn) but sadly it's giving TLE:(

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

Testcase 41 is on fire

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

so many fst on problem C and D..

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

Several stupid mistakes on A and D led to the terrible penality and the rapid descent of rank.

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Sad to get FST on E :(

(my solution isn't the best solution so it got TLE on test 10.)

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

.

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

Problem E

Can any one explain why in input

2 ?? 1 ab

10 palindrome substring

(a, b, aa, bb, a, b which other?)

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

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

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

Can anyone tell me what's wrong with my code for Problem C. I was expecting a TLE but got a WA on the 27284th token!

It's in Go, but easy to understand. Uses 2 bool arrays for x and y and just loops over x1->x2 && y1->y2.

https://codeforces.com/contest/1679/submission/157188079

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

    If I add two rooks on same row and then remove one of them, in that case your code is considering that there is no rook on that row. Because of this

    mx[x] = false
    my[y] = false
    

    You should store frequency of rooks on particular row and col to resolve this

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

Can anyone tell what's wrong with my submission? Passed the pretests but failed on Test 10. https://codeforces.com/contest/1679/submission/157152675

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

    This test case will fail in your code:

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

write x<n instead of x<=n in the Fenwick tree and got fst on C. What a pity!

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

Problem b guarantees 1≤ai≤109 but why 0 appears in test6

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

Can anyone tell me why I got runtime error? my submissions

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    template <typename T>
    struct Fenwick {
        const int n;
        std::vector<T> a;
        Fenwick(int n) : n(n), a(n) {}
        void add(int x, T v) {
            for (int i = x; i <= n; i += i & -i) {
                a[i] += v;
            }
        }
        T sum(int x) {
        	if(x <= 0)return 0;
            T ans = 0;
            for (int i = x; i > 0; i -= i & -i) {
                ans += a[i];
            }
            return ans;
        }
        T rangeSum(int l, int r) {
            return sum(r) - sum(l);
        }
    };
    

    your code get an out of bound error when i == n (a[n] will out of bound).

    you should let your vector resize to n + 1.

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

      but I declare the structure Fenwick x(n + 1), y(n + 1) way.

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

        In your Fenwick n = n + 1 at the same time.

        for (int i = x; i <= n; i += i & -i) {
            a[i] += v;
        }
        

        In this for loop, the n is 1 larger than the n your input. So a[n] will out of bound even if you declare the structure Fenwick x(n + 1000), y(n + 1000).

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

      i also got runtime, when i initialize with n+1 i get RE when initialize with n+2 it passes and when i initialize with n+3 it again gives RE. i couldnt understand why edit: it gets accepted in c++20

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

Can anyone please find a test case where this code (157177615) fails. I have tried to come up with a failing test case but have had no success.

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

Why the system is testing again ?

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

What happened, why is task B being retested?

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

Thx the contest.Become Master at last!

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

who else had a rounding error in problem A haha

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

Thanks for the Problems . It was a pretty balanced round

»
22 months ago, # |
  Vote: I like it -19 Vote: I do not like it

我小号第一次进前一千!!!

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

Can someone see my solution for C I find nothing time consuming here. Can any minor changes make it acceptable.

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

    Aren't you iterating over rows and columns for each query though?

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

    I mean you have those two loops in your code:

    for i in range (q):
      for i in range (a[1], a[3]+1):
    
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! Can you also please suggest other efficient ways to do it with same logic(like checking if all any one of columns or rows are filled) if possible. Or is there any other logic for this

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

        fenwick tree or segment tree to check sum or minimum in the range.

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

        I've done this problem the same way as you (logic wise). You can look at my submission.

        However, I used C++'s set and its 'lower_bound' function. I guess you can find something similar in python :)

        Maybe there is even some simpler way to solve it but I can't think of anything.

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

can someone tell me how to solve D plz

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

    Binary search the answer, then you need to judge if there is a cycle or a path with a length of at least k containing vertices with number <= answer. You can do toposort or dfs. My submission

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

Imao the limit on C has been too tight. Whether solution is accepted or not is up to constants and the judging machine. These two submits differ only in a tab (begining of main), however only one gets ACC: 157217055 157214568

(Played with it after the round so there might be some diffrence but the point remains anyway.)

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

    you are returning a string level by level in segment tree, which could be much slower. Change it to an enum and it will finish in ~300ms.

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

Can someone please help me figure out what went wrong with my solution on problem C?

What i was doing is: - store how many free rows/cols we have upto a certain row lets say r and c (using 2 BITs)

  • when u place a rook at row r and col c, u reduce the number of free rows and cols at row r and c
  • when u remove a rook u add 1 free row/col
  • to check if all rows and cols in a certain range are under attack by a rook simply check if there are 0 free rows or columns in that range
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to consider the case where two rokes are in one row. After removing one of them the other one is still on that row.

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

    How to check if all rows and column in that submatrix is attacking by rook in log(n) time,beacuse it will take o(n) time

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

public class C {

public static void main(String[] args)
{
    FastReader sc = new FastReader();  
    int t = 1;
    while(t-- >0)
    {
        int n = sc.nextInt();
        int q = sc.nextInt();
        boolean rows[] = new boolean[n];
        boolean cols[] = new boolean[n];

        outer:while(q-->0)
        {
           int type = sc.nextInt();
           if(type==1)
           {
             int x = sc.nextInt()-1;
             int y = sc.nextInt()-1;
             rows[x] = true;
             cols[y] = true;
           }
           else if(type==2)
           {
             int x = sc.nextInt()-1;
             int y = sc.nextInt()-1;
             rows[x] = false;
             cols[y] = false;
           }
           else
           {
             int x1 = sc.nextInt()-1;
             int y1 = sc.nextInt()-1;
             int x2 = sc.nextInt()-1;
             int y2 = sc.nextInt()-1;

             boolean done = true;
             for(int i=x1;i<=x2;i++)
             {
              if(!rows[i])
              {
                  done = false;
                  break;
              }
             }
             if(done)
             {
              System.out.println("Yes");
              continue outer;
             }
             done = true;
             for(int j=y1;j<=y2;j++)
          {
              if(!cols[j])
              {
                 done = false;
                 break;
              }
          }
             if(done)
             {
              System.out.println("Yes");
              continue outer;
             }
             System.out.println("No");
           }
        }

    }
}

// Can anyone help me figure out the test case, where this solution would fail?

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

Can someone tell me why my solution of Problem C is giving WA on Test Case 3?

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

    And even if it passed test case 3 it will get TLE for sure! Your solution is O(n^2) and the constraint is 2*10^5 Make sure to learn the Fenwick tree first to solve this problem

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

      It can be solved with c++ set

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

        Please explain this solution in c++ set.

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

          For rows:

          store in set every value that is not covered by any rook.

          initially this set is obv full.

          to know whether there exists a row between x1 and x2 that is not covered you make use of set.lower_bound()

          if lower_bound(x1) is set.end() or its value is > x2 then all cells between x1 and x2 must be covered

          same for columns

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

For some reason I couldn't come up with using segment tree for C, instead I used a complicated data structure that contains every consecutive segments. I believe it is useful for some specific problems, but it was an overkill for this problem. It is implemented with a set<pair<int, int>> where each pair represents the endpoints of each segment. Each operation is implemented in these ways:

  • To insert a new element x, check if there is a segment that contains x-1 and x+1, respectively. If a segment [l, x-1] exists, remove it and insert [l, x]. If a segment [x+1, r] exists, remove it and insert [x, r]. If both exist, remove both and insert [l, r]. If none of them exist, just insert [x, x]
  • To remove an element x, search for a segment [l, r] that contains x. Remove this segment, and insert [l, x-1] and [x+1, r], if l != x and x != r, respectively.

Every operation can be done in $$$\mathcal{O}(\log{n})$$$ time. Searching for segments around x can be done with set::lower_bound or set::upper_bound and decrementing the iterator if needed.

AC code: 157170732

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

    Forgot to mention the part that checks the answer. For a query [x1, x2], we just need to find a segment that includes x1, and see if that segment also includes x2.

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

    Looks like a weakened version of Chtholly Tree (or to use a more accurate description, maintenance of connected color segments).

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

Can someone suggest similar problem like D

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

Can someone please explain why my solution from problem C is giving TLE. 157292933

Thanks

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

My video editorial: https://youtu.be/Qa9gabukKqg

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

With 1 minute and 30 seconds left in the competition, tourist got to the first place by a hack. Cool!

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

Should not ratings be updated again for this contest? At contests page I got 894 place but at official standings 883 place.
Check out your own