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

Gheal's blog

By Gheal, 10 months ago, In English

1831A — Twin Permutations

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate Problem

1831B — Array Merging

Author: tibinyte

Hints
Solution
Code (tibinyte, C++)
Rate problem

1830A — Copil Copac Draws Trees

Author: alecs

Hints
Solution
Code (Gheal, C++)
Code (alecs, C++)
Rate problem

1830B — The BOSS Can Count Pairs

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Code (Vladithur, Python)
Rate problem

1830C — Hyperregular Bracket Strings

Author: Gheal

Hints
Solution
Code (Gheal, C++)
Rate problem

1830D — Mex Tree

Author: Gheal

Hints
Solution
Code (tibinyte, C++)
Rate problem

1830E — Bully Sort

Author: valeriu

Thanks to errorgorn for the solution!

Solution
Code (tibinyte, fenwick tree + ordered_set C++)
Code (tibinyte, sqrt decomposition, C++)
Code (errorgorn, divide and conquer, C++)
Rate problem

1830F — The Third Grace

Author: tibinyte

Thanks to errorgorn for the editorial!

Solution
Code (errorgorn, C++)
Code (valeriu, C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments.

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

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

"If there is anything wrong or unclear in this editorial, feel free to ping me or any of the other authors in the comments."

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

    Can you explain how to do Div2 E (Hyperregular Bracket Strings). I can't understand the editorial. So, i understood the logic of splitting the overlapping intervals, then how did you proceed further? Also, if I have 3 intervals (1,20),(3,12),(4,9) -> (1,2),(3,12),(13,20),(4,9) -> (1,2),(3,3),(4,9),(10,12),(13,20) -> this should be impossible right? As (3,3) will never be a regular interval

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

      They don't mean to split intervals like that. Imma illustrate their idea. As an example, let's say $$$n=10, k=3, (l_1, r_1) = (1, 8), (l_2, r_2) = (3, 4), (l_3, r_3) = (7, 10)$$$. I'll use the letter $$$x$$$ to denote an empty space. Let's write a sequence of $$$n=10$$$ empty spaces: $$$xxxxxxxxxx$$$. If a position is covered by the $$$1^{st}$$$ interval, put $$$1$$$. If a position is covered by $$$1^{st}$$$ and $$$2^{nd}$$$ intervals, put $$$2$$$. If a position is covered by $$$3^{rd}$$$ interval, put $$$3$$$. If a position is covered by $$$1^{st}$$$ and $$$3^{rd}$$$ intervals, put $$$4$$$. So the sequence of empty spaces turn into this: $$$1122114433$$$. Now look at subsequences containing only $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$: $$$1111$$$, $$$22$$$, $$$33$$$, $$$44$$$. We count ways to make RBS on these four subsequences and then multiply them together: $$$2 \cdot 1 \cdot 1 \cdot 1 = 2$$$,which is the correct output.

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

        Thanks. Got it. Can you explain the step after that too? Regarding hashing?

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

          The main idea is every time we input an interval, we modify a subarray (the array here is the sequence $$$xxxxxxxxxx$$$) according to the interval so that each position knows which intervals cover it. So like after inputting $$$l_1 = 1$$$ and $$$r_1 = 8$$$, we do something in the subarray $$$[1,8]$$$, so every positions from $$$1$$$ to $$$8$$$ knows they are covered by $$$(l_1, r_1)$$$. The editorial does this by assigning each interval a random number and XOR every element in the subarray $$$[l_i, r_i]$$$ by it, but some solutions I saw use addition instead of XOR.

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

            But why they don't have to fix hash conflict?

            There are 2^30000 subsets of intervals in total, hashed into a 64-bit integer. Won't that be lots of conflicts?

            I don't really understand.

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

    why cant we simply just sort the array in the a problem ?

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

i love this round

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

I had almost solved Div-1C, I had the idea of overlapping and included intervals! but I couldn't find a way to implement it :(

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

    same problem! kinda sad that I missed the chance to solve ABCd1

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

Can Div-1B be solved with smth like CHT or LiChao tree? We can reduce the problem to two operations:

  1. $$$add \_ line(k, b)$$$ — add line $$$kx + b$$$ to our structure.
  2. $$$count(x, y)$$$ — count number of lines s. t. $$$kx + b = y$$$ (or $$$\leq y$$$).

Is there anything what can support these operations?

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

    Tried thinking along that line too. But i don't think LiChao can do operation 2 due to overcounting?

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

Solved Div2 C in practice using BFS. Or is it also DP in disguise?

https://codeforces.com/contest/1831/submission/207670475

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

    Yes. It will consider two cases using BFS. It actually corresponds to two cases of dp.

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

Please add this to the contest material of Div 2 :) currently it can only be seen from Div1.

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

For some reason Div2 A prolem time limit is failed when using Java 17 with standart util.Scanner.

Yes, I know util.Scanner is not fast, but I guess there should be enough time to read data by standart tools, if you have algorithm with needed complexity (O(N) in this task)

https://codeforces.com/contest/1831/submission/207588412

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

Can someone try hacking https://codeforces.com/contest/1830/submission/207655131 , or explain why it’s good. It is solution for Div1C, and i am basically keeping a stack to calculate answer. But when two intervals partially intersect, i delete the latter , but add back a needed interval to my set of intervals.

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

Div1B is terrible. The goal of a problem should be figuring out the solution, and not trying to squeeze your code to pass after you know the solution.

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

    The model solution runs in under 1.2s, which I think is fairly reasonable for a problem with a 4s TL.

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

      It's not about the complexity of your solution. It's about the people who had the same idea as the editorial but failed to solve it because they used for instance hashmap against map, or some tiny constant.

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

        Dear contestant,

        Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.

        Thanks for the feedback.

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

      Why does the model solution use 500MB of memory out of the allowed 512MB?

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

        +1. I resubmitted (with 2 extra WAs which were my fault) because I was afraid 518k KB would MLE systests. I don't think it's a bad problem but I feel allowing 1024MB would've been ok here. Especially since the model solution uses a similar amount of memory.

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

        We also have solution with linear memory, but it's not posted there.

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

          pls share.

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

          Yeah, but why didn't you think that it is a good idea to set ML to 1024MB if one of the authors solutions uses $$$n \sqrt{n}$$$ memory?

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

            Authors test 1000s (a bit of exaggerated) solns, its not necessary to allow all of them to pass.

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

      Can someone explain time complexity of 207670551?
      I do not understand why its fast enough (run in <350 ms), worst case I can think of will take $$$O(n*sqrt(n))$$$.

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

    .

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

    i felt the same

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

div1B killed

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

    for me, honestly, finding solution for div1B was much easier than understanding problem statement for problem Div1A/Div2C.

    I spent more than 30 minutes to understand problem statement and test case '1' in problem C.

    I solved problem Div1B,Div2D within 28 minutes. xD

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

      this is not hard to find solution, but it is hard to code it

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

Since there is lot of discussion going on about problem D with tight timelimit, I personally feel that time limit was sufficient to pass O(N * log N) + O ( N * sqrt(N) * log N ) , which is more than sufficient.

Solution with Simple map and binary search
  • »
    »
    10 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I think that TL was enough but the great problem was in the ML. By the way you're code is very clean. got AC with this time complexity!! Take a look at my code which should have $$$O(n\sqrt n)$$$ with time complexity of 1123ms 207646321

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

    But how are you maintaining the condition 1<=i<j<=n,I am not able to understand.

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

    Where did shard[k] come from? Shouldn't it be shard[p]?

    Thank you for your explanation you are a legend.

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

https://codeforces.com/contest/1830/submission/207653094

The code is giving runtime error with GNU G++ 17.No runtime error with GNU G++20.

Why is it happening ??

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

    Yes the same happened to me...

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

thanks for the contest, solving D1D was very fun

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

Yesterday's abc_E tilted me towards a leaves-first idea for div2C, counting up the number of out-of-order edges on the way to the root. It's an approach that can work, but I seemingly stumbled into every possible way to make it break, even after getting a fake AC.

TLE: long path from root into many leaves risks repeatedly traversing that path

WA: attempts to bail early on lack of update worked, but (hindsight) since I was updating and testing on different vertices, I had to leave in the == no-update case... which meant it was still very possible to TLE as before

uphackTLE: in attempting to test vs. that worst case, I neglected to clear out all shuffling/randomizing code in my generator, so the 'far' root 1 was always randomly somewhere convenient and/or the number of passes really did need updating

technical-debt-TLE: (hindsight again) a bug-free version of my per-leaf approach was still vulnerable because there could be a tree that actually did have progressively better passcounts per traversal obviating my early-out flailing. What I really needed was the post/return half of a dfs/bfs, only proceeding rootward after all children were accounted for... OR not getting the leaf-first idea stuck in my head from yesterday.

tl;dr free uphack and maybe some giggles...

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

The idea of Div1B was fine, but the tests were so weak. Even the system tests cannot save it as most solutions got TLE on tests provided by hackers, and I don't even think that my solution is good enough to get AC :D

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

Good round, I like it.

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

The Memory limit Div1 B was soo tight, but it was fun to solve tho

»
10 months ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

This was my first Div. 1 contest. I solved A, but not very fast because I wanted to get accepted with one submission. Then I started to think about problem B. In about 1 hour and 20 minutes I got accepted (I was happy to increase my rating on my first Div. 1 contest). But, unfortunately, I got FST (TLE on test 15) during the system testing. And I want to share with you my solution and a bug, which was tricky to find.

The main idea of my solution is similar to many of the other solutions.

I keep the answer in $$$ans$$$. First, I define an array of vectors $$$c$$$, where I store all $$$b_i$$$-s for every element in $$$a$$$ (i. e. for every pair of $$$(a[i], b[i])$$$, I push $$$b[i]$$$ to $$$c[a[i]]$$$) and then I sort every $$$c[i]$$$.

Then I brute force every $$$i$$$ and $$$j$$$, such that $$$i*j <= 2*n$$$ and $$$i<j$$$. My goal is to find every pair $$$(x, y)$$$: $$$x$$$ from $$$c[i]$$$, $$$y$$$ from $$$c[j]$$$, such that $$$x+y=i*j$$$. Now, for every pair $$$(i, j)$$$, I go through all the elements of $$$c[i]$$$. For element $$$x$$$, I find $$$l$$$ and $$$r$$$ (with binary search): the borders of $$$i*j-x$$$ in $$$c[j]$$$. Then I update the answer with $$$r-l$$$ (or $$$r-l+1$$$, depending on how you choose the borders). After that I update the answer for $$$i=j$$$, and we are done!

But wait!, this solution gets TLE. And the problem is, that if there are many elements in some $$$c[i]$$$, we will brute force through them for every $$$j$$$. To avoid this, we find one with fewer elements than the other one (I mean $$$c[i]$$$ or $$$c[j]$$$) and go through the elements of that one. And at last here we are done.

Time complexity: $$$O(2n*\sqrt{2n} + C * log(n))$$$. Here $$$C$$$ is the maximal possible value of $$$\displaystyle \sum_{i<j}^\mathbb{}$$$ $$$min(size(c[i]), size(c[j]))$$$.

My code.

I hope this was helpful.

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

    I did exactly what you did, but I can't prove the time complexity. Could you please explain it clearer how choosing the smaller between c[i] and c[j] results in that time complexity?

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

      I apologize that I can't prove it formally, but intuitively, if there is one with many elements, there has to be another with few elements. Also, it is obviously better to brute force through the one with fewer elements.

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

Div2 D has an O(nlog^2n) solution. Let cnt(x, y) be the number of indexes i such that a[i] = x and b[i] = y. b[i] + b[j] = a[i] * a[j] <= 2 * n, so for fixed i there are 2 * n / a[i] possible values of a[j]. Thus, iterating over all possible pairs of values (a[i], a[j]) takes O(nlogn) operations (2n/1 + 2n/2 + ... + 2n/n = 2n * (1 + 1/2 + 1/3 + ... + 1/n) = 2n * logn). For given pair (x, y) we can iterate over all i such that a[i] = x (totally O(n) time) and add to the answer cnt(y, x * y - b[i]). cnt(x, y) can be calculated for O(logn) using binary search.

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

    I don't think that would work. For example, when iterating $$$a[i] = 1$$$, based on my understanding, you find all $$$i$$$ such that $$$a[i] = 1$$$, then also iterate over all $$$y = 1, 2, ...2n$$$, and then add $$$cnt(y, 1 * y - b[i])$$$ to the answer. But this step is actually $$$O(n^2)$$$, because there could be $$$O(n)$$$ indices $$$i$$$ such that $$$a[i] = 1$$$.

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

      But what if I apply a little optimization?

      For a $$$(a_i, a_j)$$$ calculation, we get two (multi)sets $$$S = \{ b_k | a_k = a_i \}$$$ and $$$T = \{ b_k | a_k = a_j \}$$$.

      Then if $$$|S| > |T|$$$, swap them, and iterate $$$S$$$.

      It finally get passed(211334263), but I can't figure out it time complexity, or whether it's a truly correct approach. Could anyone tell me this?

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

https://codeforces.com/contest/1831/submission/207670314

Could someone point out mistake in my code been trying for very long ,dont see the mistake getting WA in test 2 ,i did a bfs like soln

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

    did you try cleaning the global variables after solve()? Probably it's bugged when you have more testcases

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

      i did that at the end of the code after cout

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

        Sorry, i didn't see that.
        Took a while but i found an actual counterexample:

        ans is 2, your code says 3

        You do some weird stuff with ok. You're looking for the minimum index edge, but i think you should set it while you do the bfs: something like

            ok[c.first] = c.second;
            if(c.second > ok[x]) dis[c.first] = dis[x];
            else dis[c.first] = dis[x]+1;
        
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          oh ok i see the mistake thanks a lot

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

Problem Div 2D has a good idea IMO. But my solution of $$$n \sqrt{n}$$$ was not passed the time limit because I used unordered_map to count the frequency (207642815)

I have used the unordered_map optimization using custom_hash function referring to this blog. Which got me to think :

  1. Did my solution wrong? I used set to maintain unique elements only. The difference with author solution is I didn't skip when $$$a_i > \sqrt{n}$$$. But I did the break the loop tho

  2. If assuming my implementation indeed is $$$n \sqrt{n}$$$ What kind of test case that breaks the unordered_map constant factor?

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

    Your solution is $$$O(n^2)$$$,here is a sample. If $$$a[1] \dots a[\frac n 2]$$$ are $$$1$$$,the other $$$\frac n 2$$$ of $$$a[i]$$$ are large and different from each other,when you find the answer of $$$a[1] \dots a[\frac n 2]$$$,all of the elements will be found,then your solution become $$$O(n^2)$$$

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

      Ah I guess that makes sense. Didn't cover that kind of test case. Thanks!

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

    yeah i too tried many $$$n\sqrt{n}log(n)$$$ and then tried with hashing (not custom), and I'm of the opinion that either im a really poor implementor or the limits are too strict

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

      Asking to remove the log factor of the map is somewhat strict imo. You had to use an array instead of a map to erase the log in the complexity. Usually if i can use a map to make it faster to implement i do it and for this reason i got a lot of TLEs before realizing that O(1) access gives ~1/4 time of map

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

        if they didnt force to remove log, the problem would definitely be solvable by n^2 (already was)

        i think they should have just forced linear memory, so it becomes clear this solution is out instead of being on edge

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

          Fair enough. Effectively n² is close enough to n^(3/2)log n. Actually plugging n it's ~1.5e9, which is obviously too big

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

            I have solved it with O ( N * log N) + O ( N * sqrt(N) * log N) .

            I have used O(log N) complexity for searching element in sorted array with binary search. and my solution passes easily.

            I dont understand why you guys couldn't pass the solution ?

            Can you please share your solution which is getting TLE ?

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

              I was using a vector s (s[a][b] = count of the pair a-b for a <sqrt(2n)). Actually some of the solution passed the time but gave wa for overflow. But they were very close. One was not in the time because i had min() in the loop condition. Moving it out made the code faster enough to get wa on another case. It was kind of a panic moment actually (still don't know if it would still get tle after fixing the overflow too)

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

              207656497, if you wish

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

Is it any problem in 1C's editorial?if $$$l_1\leq l1_2\leq r_1\leq r_2$$$,the groups formed by two intervals are $$$[l_1,l_2-1],[l_2,r_1],[r_1+1,r_2]$$$?But it doesn't matter :D

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

Want to point out that, for Div1 C, to derive the number of regular bracket strings of length 2n, this is essentially equivalent to having a simple random walk that start at 0 and end at 0 while never touching -1. The reflection principle is commonly used to calculate it.

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

Can 1B exist any polylog solution?I guess the answer will no more than $$$O(n\log n)$$$ or $$$O(n)$$$ if all pairs of $$$a,b$$$ are distinct,but I have no idea how to find them in no more than $$$O(n\log^2n)$$$ :(

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

How to solve problem B?

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

I'm wondering why I got TLE for div2 C.

I pretty much did the same thing as the editorial. I have an array to store the index of each edge, and then I did BFS. At each node, I compare the index of the edge that connects that node and the parent with the index of the edge that connects the parent and the parent of the parent.

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

    nvm I figured out why, apparently I was creating vectors of size 2e5 for every testcase, so for some reason creating a vector of size n is O(n)??

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

      "the sum of n over all testcases is 2e5" But if you have 10,000 testcases and make an array 2e5 long you have that the total complexity is 2e5 *1e4 = 2e9, which is a big overhead considering that to have t=1e4 you have average n = 20

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

        207786285

        Is this the reason why my solution gets a TLE too ? (I have tried to maintain an ans value (current.first in the submission) along with the edge-number for each node. And update the ans everytime a node is fully "explored").

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

          It's possible. Just try and change resize(N) to resize(n+1) and see if it works

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

            Holy shit, that worked. Thankyou so much. I would have wasted the entire week trying to find out why if it wasn't for your comment.

            The TLE was happening because effectively the complexity was more like O(n*t) where t is the number of tests in one big-test-case ? Or is it that making such a long array for each test case is just inherently very "slow" to do ?

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

              Your complexity is O(maxn*t) and if t = maxt you have the worst case. Btw you can check in the docs the complexity of resize (it's linear in the difference to the current size)

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

F can be solved with lazy propagation on kinetic segment tree: code

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

Really liked div 1, C and D. Also, I think there is a simpler way to implement div 1 C using segment tree instead of xor hashing, for the union part of solution. Was close but could not solve it in contest though :(

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

my rating stayed as is, haha what were the odds!

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

Would someone be able to check why my solution to Div 2 D TLEs on case 8?

It's basically the same as the official solution and runs in O(n*sqrt(n)), so I'm unsure why it TLEs.

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

Can somebody debug my problem B code where i'm doing mistake: Approach: I stored the max frequency of each number of a and b in mpa and mpb. After that i calculated the ans as the sum of frequency from a and b.

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

    You gotta keep the counts of the longest subarray of similar integers, for every integer in a and b find out the maximum length of of all equal elements, do this for both array and in the end just store the sum of length of contiguous equal subarrays for all integers in both arrays. Why are you using stacks?

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

      i used stack to count the max frequency of each number present in a array, btw i figured out the issue with minor changes my code got accepted. If you want to have a look

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

        stacks + maps pretty heavy, I guess the runtime will stay around 500ms anyways

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

Only if I proved my solutions :(

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

What is the time complextity of my solution: 207651808?

First, I iterated through the values of a[i], this part is $$$O(n)$$$

Then, I iterated through the values of a[i] * a[j], until now it's $$$O(n log n)$$$

After that, I iterate through the indices i that have value a[i] and used binary search (this add another log) to count number of satisfied indices j. Here, I optimized it by iterate through indices j instead if there is fewer of them.

Somehow this passed systest, (actually during the systest I saw it TLE on pretest 3, but AC when I checked again this morning).

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

Div 2 problem B.Array merging... Editorial looking so complex Here is my approach 1-->Intially after reading the arrays take the contigues frequencies of all elements and update if it is greter than the previous freq of that element make this for both the arrays after making that just iterate from 1 to 2*n and take the max of res and fre[i] would give you the solution

and here is my submission have a look https://codeforces.com/contest/1831/submission/207716898

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

Div2 D is the most interesting problem for me.

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

    I am having difficulties understanding the editorial, can you help me out a bit?? thanks!

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

      Well, the basic idea is lim = sqrt(2 * n) and fr[a[i][b[i]] (a[i] <= lim). For each i, instead of running all over the array (which takes O(n)), you can just use the formula fr[j][ai⋅j−bi] where j runs from 1 to lim denotes for a[j], a[i].j — b[i] denotes for b[j] while you have known a[i] and b[i] which takes O(lim), enough to pass the tests!

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

        yess, that makes sense. I understood the equation which you gave. But I am still confused with the equation given in the editorial for ai=aj and and ai>aj. Can you explain how those two equations work..

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

          the equation of a[i] > a[j] is as I've explanied above. But I don't truly understand the equation a[i] = a[j] though.

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

            Okay Thank you!

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

            assuming you understood the fr[a[i]][a[i]^2 — b[i]] part of the equation, notice that we overcount such cases in the expression: let's say we got a[i] = 2 and b[i] = 2 for some i, then a[i] * a[i] = b[i] + b[i], so the pair (i, i) is counted as good, but since the problem only asks for good pairs where i < j, we need to subtract all such cases, and what do these cases look like? since we have a[i] * a[i] = b[i] + b[i] iff a[i]^2 = 2 * b[i] iff a[i]^2 / 2 = b[i], so we need to subtract fr[x][x^2 / 2] for all 1 <= x <= lim, and that's where the numerator of the equation comes from. now the reason we divide the numerator by 2 is because we're counting all good pairs twice since if (i, j) is a good pair then (j, i) is also a good pair, and we need to count only one of these.

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

Great Contest :)

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

Can someone help me with Div2 D, please? Thanks!

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

Can anyone explain how the formula is arrived in DIV2 D for the cases ai=aj and ai>aj ?

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

Can anyone explain what's wrong with my submission for Div2B? https://codeforces.com/contest/1831/submission/207612809

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

    while checking maxi keep an iterator from 1 to 2*n and for every i in the m1 and m2 update the maxi

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

Can we download the full testcases ? I want to debug my code. Can anyone help with this, here is my solution link https://codeforces.com/contest/1831/submission/207738412

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

I saw Div2B if..else in for and to add else block after for loop pattern, million times yet I couldn't solve it

Goal for 2025: Newbie after solving 1000 problems

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

In div-2, problem C was amazing.

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

I was so sad that i could not solve b in contest time . but i just realized that the range of array a and array b is <= 2*n .

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

In div2 D why this soln gives TLE-> Let's traverse on unique pairs of a(i),b(i) and for each a(i) we will traverse for all distinct values of a(j) and find the value of b(j) corresponding to the known a(i), b(i) and fixed value of a(j) and thus can then easily calculate the number of pairs formed using an unordered_map with custom hash in avg o(1) complexity..

Now for fixing the value of a(j) lets see two cases for a(i)-> 1. a(i) >sqrt(2*n)->

in this case since a[i]*a[j] should be less than on equal to 2*n (as shown in editorial), hence possible values of a[j] would be from [1, sqrt(2*n)]. hence for each a[i]> sqrt(2*n) we can traverse all possible values of a[j] in sqrt(n) complexity

  1. a(i)<= sqrt(2*n)->

in this case value of a[j] can be from [1, n] but since all the pairs of a[i] with a[j]>sqrt(2*n) is already covered in case 1 hence we need to iterate only on the values in range [1,sqrt(2*n)].

hence overall complexity is o(n*sqrt(2*n))

please help Gheal

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

Am i the only onr who solved div2 C using lazy segmenttree with O(nlog(n)) ??

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

Could someone explain how's the first summation came out in Div2D/Div1B? Thanks!:)

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

In Div1D, the maximum size of a connected component is $$$O(\sqrt n)$$$. But what's the exact upper bound of it? Theoretically, it's $$$\sqrt{3n}\approx 774$$$, but my submission, where I suppose it doesn't exceed 400, got accepted. Can anyone prove it or hack it?

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

I have been wondering for the past two days how the hell did my submission passed the tests in div.2 C and didn't get TLE: https://codeforces.com/contest/1831/submission/207638978

In a test like this:

1

200000

1 2

1 3

1 4

1 5

1 6

1 7

...

...

...

1 199999

1 200000

The only thing I realized is that this corner test case isn't in the test cases or there are some hidden info in the constrains I didn't notice. But I don't think so.

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

    That case was just missing. Your solution is now hacked.

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

      Thank you!

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

        BTW how do I uphack a submission after the round is finished?

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

          A "hack" button appears on the submission page, but only if you're 1900+ rated (or 2100+, I can't remember which)

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

I think that I have trouble understanding the first code of 1F.

The tutorial says that we should subtract the contribution of some lines, but in the code, the only update is adding new contribution.

Maybe I have made some stupid mistakes. Can anyone please explain it? QaQ

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

nice contest

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

I'm new to hashing. In Div1 C, is there a chance of a wrong answer when using randomly generated numbers? And can we choose some numbers on our own to avoid that situation?

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

Do you know solution for Hyperregular Bracket Strings without random?

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

    You can find all minimum ranges by scanning line and heuristic merge(?not sure about this name), and the rest can be solved as a bracket sequence. One implementation is 207718096. However, I think this is just a coincidence that there exists a non-random solution. I still recommend you learn the randomized solution, it's very general.

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

https://codeforces.com/contest/1831/submission/207616298 Can anyone help me with the runtime error in my submission. I am not able to figure out the what is the reason for this.

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

In the solution of Div1/C, for the case 2 (partially overlapping intervals), won't the groups formed should be [l1,l2-1],[l2,r1] and [r1+1,r2] instead of [l1,l2-1],[l2,r2] and [r2+1,r1]. Gheal

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

In div1 C, I spent most of my time during the contest trying to use sweep line to construct a tree with hierarchy of intervals. I have read the hints in the tutorial, it's mentioned that it is difficult to construct that tree. Gheal, do you know an algorithm that constructs that tree? or if anyone could provide useful resources.

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

    Sorry for the late reply. If I'm not mistaken, Vladithur had a deterministic solution while testing, I've reuploaded it here.

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

For the solution code of Div 2E/1C, if I change LLONG_MAX to LONG_MAX in uniform_int_distribution<ll> rnd(0,LLONG_MAX), I get WA on test case 4, which is a big-number test case where n = 300000 and k = 300000 (207948273) (I submitted multiple times and it's always WA on test case 4). When I print the hash values, they all seem to be as random and large as the solution code.

Can anyone explain why this happens? Thanks in advance.

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

    oh nvm, it's due to compiler differences.

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

problem c

vector<pair<int,int>> edg[NMAX]; ... edg[u].push_back({v,i}); edg[v].push_back({u,i});

how does this work? why we create a new pair in the vector element?

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

There is an alternative solution for Div.2 C, where you essentially simulate the process. You keep a std::set of all the edges you can draw and a pointer of where you currently are in the edge list. Using the lower_bound function we can find the next edge we will encounter and when we do, we update the set of edges we can draw and update the pointer to the index of the currently processed edge + 1. In the case when the largest element in the set is smaller than the pointer we set the pointer to 0 and add 1 to the answer. We will process each edge exactly once so the complexity is O(n*log(n)). You can see my submission here: https://codeforces.com/contest/1831/submission/207936976

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

For div 2 c question I think the statement of each edge is not accurate, I ran the code I think it is checked the edge below this edge[problem:1831C]

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

May someone explain me why the computation of the dp in Div1 D is $$$O(n\sqrt n)$$$ ? it's hard to prove for me, even that I know how to prove that the time complexity of the "7-th trick" is $$$O(n^2)$$$.

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

    In the "7-th trick" the time complexity is $$$\sum siz(v) \cdot siz(u) \le n^2$$$ over all dp merges. In our case, we have time complexity $$$\sum \sqrt{siz(v)} \cdot \sqrt{siz(u)}$$$ so we have the sum of square roots of these values. Let's define $$$\sqrt{siz(v) \cdot siz(u)}$$$ as just a value $$$a_i$$$. We know $$$\sum_{i=1}^n a_i^2 \le n^2$$$ (there are actually $$$n-1$$$ summands but it doesn't matter). Dividing both sides by $$$n$$$ and taking a square root we get $$$\sqrt{\frac{\sum_{i=1}^n a_i^2}{n}} \le \sqrt{n}$$$. But on the left-hand side we have the quadratic mean which is at least the arithmetic mean by the means inequality. So $$$\frac{\sum_{i=1}^n a_i}{n} \le \sqrt{\frac{\sum_{i=1}^n a_i^2}{n}} \le \sqrt{n}$$$. $$$\sum_{i=1}^n a_i \le n \sqrt{n}$$$ follows which is exactly what we wanted.

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

      Thanks for your generous help! That helps a lot for me. The prove is definitely right and I know exactly how to realize it by code. However, the time complexity of the standard method is $$$\sum_{i=1}^n min(siz[v],lim)\times min(siz[u],lim)$$$, which $$$lim = \sqrt{3n}$$$. If possible, I hope you can provide relevant proof. Thank you very much!

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

        Oh, wait, is it? I think in trick 7 it is just the product of sizes. But even if it's not, it is easy to see that just the sum of products of sizes is $$$O(n^2)$$$ because you can think about the product of sizes as uniting two sets and listing all pairs of elements where one element is from the first set and the other elements is from the second set. In this way, every pair of elements in total will be listed at most once (exactly at their LCA), so the total sum is at most $$$n \cdot (n-1) / 2$$$.

        And well, taking min with $$$lim$$$ can only decrease the sum but it is actually irrelevant.

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

          Is it irrelevant? I believe that if you merge in $$$min(sz_u,lim) \cdot min(sz_v,lim)$$$ the time complexity becomes $$$O(n \cdot lim)$$$. I don't know how to prove it tho but perhaps it's something similar to the $$$lim = \sqrt{n}$$$ case.

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

            We merge in time $$$\sqrt{sz_u} \cdot \sqrt{sz_v}$$$.

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

        Ok. Now I understand your question. I guess the solution in the editorial is a bit different from what I read there. Without loss of generality, we can assume that our tree is binary because we kinda assume it anyway: we merge all the children of a vertex one by one which is equivalent to having a bamboo in which we add them one by one to the tree. If you take $$$\sum \min(sz_v,lim) \cdot \min(sz_u, lim)$$$, then you can consider $$$v_1, v_2, \ldots, v_k$$$ to be all the vertices $$$u$$$ in the graph such that all children of $$$u$$$ have $$$sz_u \le lim$$$ but for the parent $$$pr_u$$$ of $$$u$$$ it is not true (so $$$pr_u$$$ has some child (either $$$u$$$ or not) that is large). Then $$$v_i$$$ can't be an ancestor of any $$$v_j$$$ (otherwise its parent would have a big child and then $$$v_i$$$ would also). It means that all subtrees of $$$v_i$$$ s are disjoint so $$$\sum sz_{v_i} \le n$$$. Inside every subtree of $$$v_i$$$ by trick 7 we work in time $$$sz_{v_i}^2$$$. But both children of $$$v_i$$$ have sizes $$$\le lim$$$, so $$$sz_{v_i} \le 2 lim+1$$$. Then Inside all these subtrees we work in time $$$\sum_{i=1}^k sz_{v_i}^2 \le \sum_{i=1}^k (sz_{v_i} \cdot (2 lim+1)) = (2 lim+1) \sum_{i=1}^k sz_{v_i} = O(lim \cdot n) = O(n \sqrt{n})$$$. We are left with all the bigger subtrees that do not lie inside $$$v_i$$$ subtrees (call all these vertices $$$u_i$$$s). There are two types of vertices $$$u_i$$$: they either have at least one of their child as one of the $$$v_l$$$s or they have both of their children as $$$u_j$$$ and $$$u_k$$$. In the first case, we work in time $$$\le v_l \cdot lim$$$ which sums up to $$$\sum v_l \cdot lim \le lim \cdot \sum v_l \le lim \cdot n = O(n \sqrt{n})$$$. In the second case, we work in time $$$lim^2$$$ per vertex but there are at most $$$O(n / lim)$$$ such vertices so we work in time $$$O(n \cdot lim) = O(n \sqrt{n})$$$ in total for them too.

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

    Take a look at this comment, it explains the exact dp formulation used in solution.

    Complexity is $$$O(nk)$$$ where $$$k=\sqrt n $$$. Proof is based on iterating over all pairs such that their preorder differs by at most $$$2k$$$.

    You can imagine it when you merge two subtrees, in the left subtree you "keep" only last $$$k$$$ nodes and in right subtree you "keep" first $$$k$$$ nodes, so their preorder number differs by at most $$$2k$$$, if subtree contains less than $$$k$$$ nodes just iterate through them. Because of that you go through $$$min(sz[u],lim)$$$.

    For each $$$i$$$ we have at most $$$2k$$$ pairs of the form $$$(j,i)$$$ such that $$$j<i$$$ so for all $$$1\le i\le n$$$ it total we have $$$O(n*2k)$$$ = $$$O(n\sqrt n)$$$

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

      Thank you! The method you mention to prove this task inspired me a lot! :)

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

I think the editorial of D D2/C D1 was wrong in case 2, when l 1 < l 2 ≤ r 1 < r 2

The three groups formed by these two intervals are:

  • [l1, l2 — 1]
  • [l_2,r_1]
  • [r1 + 1, r2]
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can some one tell me why the editorial guy is subracting fr[i][i/2] from the case when a[i]=a[j]

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

Hi Gheal & Vladithur, Python solution in the editorial for problem Div2D (1830B — The BOSS Can Count Pairs) throws TLE. Can you please fix it? https://codeforces.com/contest/1831/submission/208150150

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

fr[i[[i.i/2]? how is this well defined?

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

Can anyone help me with Div2B? I can't pass test 2.Code is here

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

Still cannot understand the description for 1830F. If there is just one activated point covered by two intervals, the cost of each interval should be the coefficient of that point.

For the first example, however, the last point (30) appears in two intervals ([2, 8] and [3, 8]), but 30 is only added once to the result.

Also, for the second example, why don't we activate the last point? It is covered by [1,6] interval.

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

    2 8 in the first test case and 1 6 in the second test case aren't intervals; they're n m, i.e. the number of intervals and number of coordinate points for the test case.

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

      Oh thanks... I am spoiled by LeetCode and didn't do much of input parsing before...

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

Solution of 1830A, without using DP and using a visited array (space complexity remains same). This question -> https://codeforces.com/contest/1830/problem/A

Solution -> https://codeforces.com/contest/1830/submission/208569032

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

Can someone explain what "connected component" means in Div1D please. If the graph is a tree then shouldn't the size of connected component be of size $$$N$$$?

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

    A maximal region with nodes of the same color.

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

      Can you further explain why the the "connected component" have $$$loss \geq \displaystyle\frac{(k)(k+1)}{2}$$$ please.

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

        It's beacause every path in a connected component contains exactly one color, so the mex surely is not 2.

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

          Got it! Thank you so much for the help

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

Can anyone please explain to me what merging exactly is in the question

1831B — Array Merging

I tried but couldn't understand what

†
 A merge of two arrays results in an array c
 composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c
. We repeat this operation as long as we can (i.e. at least one array is nonempty).

this exactly meant.

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

Regarding Div2 C , Can we do it without DP?

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

Sorry for necroposting.

I tried doing d1c, and I found a $$$O(klog^{*}k)$$$ and a linear solution, so I thought that maybe someone would find it interesting.

If you look at the prefix sums where open parentheses are $$$+1$$$, closed parentheses are $$$-1$$$, then a restriction $$$[l, r]$$$ says that $$$s_r = s_{l - 1}$$$, and every $$$s$$$ in between must be greater or equal than the $$$s_{l - 1}$$$ (that is, $$$\forall i, l - 1 \leq i \leq r, s_{l - 1} \leq s_i$$$). If we look at how ranges overlap, if they do partially, then we pretty much get the same as in the editorial: $$$s_{l_1 - 1} = s_{r_1} = s_{l_2 - 1} = s_{r_2}$$$. The equality between $$$s_{l_1 - 1} = s_{l_2 - 1}$$$ is obtained with a $$$a \leq b \land b \leq a \implies a = b$$$ argument.

The idea of the solution is to have the ranges, do a sweep line from left to right, and try to store the equivalence classes, while also trying to compute the answer.

The way that I store the equivalence classes is by storing a DSU (the linear solution is obtained from the one with DSU and figuring out that it's actually useless) and a stack. I will store all the equivalence classes, and for each one I will store the following: the position of the last element, the position of the first element, the number of open ranges (this is used to figure out when you're done with an equivalence class and you do not need to store it anymore) and the number of already processed elements (that is, the total length of the included sub-intervals). The classes in the stack should be ordered, from bottom to top, increasingly by the position of the last element. When you insert a range, you just add it as a standalone equivalence class. When you close an interval, you merge all the equivalence classes from the stack that can be merged by the current interval. That is, you pop from the stack as long as the last element of each class is included in the current range, and merge the popped elements from the stack. When popping elements from the stack, you also try update the answer: suppose that the last element in each class from the popped elements are $$$x_1, x_2, x_3, ..., x_n$$$, then you multiply by $$$f(x_2 - x_1 - e_1) * f(x_3 - x_2 - e_2) * ... * f(x_n - x_{n - 1} - e_{n - 1})$$$ where $$$f(N)$$$ is the number of bracket sequences of length $$$N$$$. $$$e$$$ is the number of erased elements from each of the equivalence class.

The count is used to see when you're done with an equivalence class for good. That is, after you merged all the classes and decreased the count with 1, you see if you push it back to the stack, or not, and then update the erased elements for the top element in the stack.

I think that this solution is correct, but I'm not 100% sure. When it comes to cases like "what if you have multiple ranges that share the same endpoints? Don't you want them sorted by the other end, or by their length, or something similar?", it doesn't matter, because if you insert the smaller element first, then you will merge it with the larger ones and they will get trimmed to the last element, and if you do it the opposite way, then you will add the smaller one to the answer and subtract it from the larger range.

Also, to precalculate the function $$$f$$$, you can just compute the factorials, do the inverse of the largest factorial, then do all the other inverses, everything in $$$O(maxN)$$$.

I feel like I rambled here about a stack and a DSU, because the underlying cases are cumbersome and I'm not entirely sure why my solution works, so if you understood what I was trying to say and have an easier way to explain, or any other cases that should be mentioned, please let me know.

Here are the two accepted solutions:

  • $$$O(maxN + n + klog^{*}k)$$$ (a little bit cheated, I precalculated the factorials for each test, so there is also a $$$tlogn$$$ term): link
  • $$$O(maxN + n + k)$$$: link