oursaco's blog

By oursaco, history, 6 months ago, In English

Sorry for the weak pretests on A :(. We hope you enjoyed the round nonetheless.

1904A - Forked!

Idea: Apple_Method
Preparation: Apple_Method/oursaco
Analysis: lunchbox

Solution
Code

1904B - Collecting Game

Idea: oursaco
Preparation: oursaco
Analysis: lunchbox

Solution
Code

1904C - Array Game

Idea: lunchbox
Preparation: lunchbox
Analysis: lunchbox

Solution
Code

1904D1 - Set To Max (Easy Version) / 1904D2 - Set To Max (Hard Version)

Idea: oursaco
Preparation: oursaco
Analysis: oursaco

Hint 1
Hint 2
Solution
Code

1904E - Tree Queries

Idea: Apple_Method
Preparation: oursaco

Editorial 1:
Analysis: oursaco

Thanks to errorgorn for the solution!

Hint 1
Hint 2
Solution
Code

Editorial 2:
Analysis: willy108

Hint 1
Hint 2
Hint 3
Solution
Code

1904F - Beautiful Tree

Idea: Apple_Method
Preparation: oursaco
Analysis: Apple_Method

Hint
Solution
Code
  • Vote: I like it
  • +135
  • Vote: I do not like it

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

i love oursaco

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

after this contest i realised, that chess tasks are not for me)) i solved B easily, mb im stupid for A idk

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

    Lol, I could say the same about math tasks. My suggestion would be for you to go onto chess.com and practice in your free time :)

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

      i don't think the problem is that you are not good at chess enough, this is really just a brain teaser, i might suggest instead to get familiar with those type of problems, a good book about this is "The art and craft of mathematical problem solving", an interesting one full of problems, although it barely talks about math, just skip the math ones since the book structure is designed for so :3

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

    and who can explain why this 236632847 doesn`t work ?

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

      Try this sample:

      1
      4 2
      5 8 1000 1006
      

      Correct answer would be 1 instead of 2 (from your solution)

      The reason is that when you use upper_bound, it give you the first element that is considered greater than your number. You should get the prev of that element for calculating difference. In the case above, 1006 - 1000 give you 6 and upper_bound give you 8, but you should look for 5

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

    can you provide and explain your B solution?

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

Got TLE in B on system testing. Did two wrong submissions also on B. I was hoping to be blue today. But missed the chance.

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

What's wrong with this solution for A? 236554300

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

    236585544 is my solution with same approach

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

    Don't do that, if you check all cases by it makes your code so long and sometimes missing cases lead to WA. Instead of using you can make 2 vectors Move_x, Move_y then For from 0->7 (a knight can move 8 cases) from the Queen and King, If a cell can be moved by King and Queen your Ans++. You can refer to my code: 236529329

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

      Yes, solved it like that later but thought casework would work as well. I missed a few cases in brute force case solution which I have to check

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

I liked D2 on how simple its implementation really was. Even though I implemented sparse table and range update segment trees, realizing it only required monotonic stack was pretty cool.

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

    so i think you'll be likely to dislike problem E and F.(hard and long code)

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

      Not really. In general, I like problems that have harder logic and lesser implementation.

      However even if the implementation is long, if the question is very unique and beautiful, I love it regardless.

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

can anyone tell me why did I get TLE here ? https://mirror.codeforces.com/contest/1904/submission/236554358.

I think the complexity here is O(N*N*log(N)). Am I wrong?

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

    You used set and map there. So on the worst case time complexity is O(N*N*log(N)*log(N))

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

    Quite strange that commenting out the map gets it accepted because the map itself should run in O(N*logN)

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

      thats why I'm asking. I really didnt understand the issue in that part of the code.

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • Your set h contains at most N ^ 2 elements. Then u lower_bound in that set for every i in array a, and run the pointer back to the beginning of the set, so the time complexity is O(N ^ 3 * logN)
        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Should the time complexity not be O(N^2 logN). As logN is required to find the upper/lower bound in the set for an element. Why there is an additional N factor in TC. Could you please explain?

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

            oh my bad, i thought he runs the pointer back to the starting point after using lower_bound. Anyway, his code is correct, just need a few minor optimizations. Here the fixed code: 236638928

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

Thanks for contest

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

Can someone try hacking this solution to D2?

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

    This test will TLE, courtesy of porker2008

    print(1)
    
    print(200000)
    
    ans = [200000 - i for i in range(200000)]
    print(" ".join(map(str, ans)))
    
    ans = [min(200000, 300000 - i)  for i in range(200000)]
    print(" ".join(map(str, ans)))
    
»
6 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

nice problems

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

Can Someone explain where my code is wrong for Problem B https://mirror.codeforces.com/contest/1904/submission/236571395

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define int long long
    // clang-format on
    
    void sol( ){
       int n;
       cin >> n;
       pair<int , int > v [ n ];
       for( int i = 0; i < n; i++ ){
          cin >> v [ i ].first;
          v [ i ].second = i;
          }
       sort( v , v + n );
       for( int i = 1; i < n; i++ ){
          v [ i ].first += v [ i - 1 ].first;
          }
       int k = v [ n - 1 ].first;
       v [ n - 1 ].first = n - 1;
       for( int i = n - 2; i >= 0; i-- ){
          if( k <= 2 * v [ i ].first ){
             k = v [ i ].first;
             v [ i ].first = v [ i + 1 ].first;
             }
          else{
             k = v [ i ].first;
             v [ i ].first = i;
             }
          }
       for( int i = 0; i < n; i++ ){
          swap( v [ i ].first , v [ i ].second );
          }
       sort( v , v + n );
       for( auto&& i : v ){
          cout << i.second << ' ';
          }
       cout << '\n';
       }
    
    signed main( ){
       ios_base::sync_with_stdio( false ); cin.tie( nullptr ); cout.tie( nullptr );
       int t = 1;
       cin >> t;
       while( t-- ) sol( );
       return 0;
       }
    
»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Loved this competition! My solution to problem C first failed on system testing, but then suddenly the verdict changed) Also, my friend’s solution failed on the same test, but it changed the verdict after the final results! Can someone please explain how this could be, because I just don't understand how system testing works on Codeforces. Sorry for my poor language...)

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

    Something like that happened to me as well. Not sure what happened there

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

can somebody help me with the reason of tle on d2(hard version) on test case 25 .here's my submission — https://mirror.codeforces.com/contest/1904/submission/236593367

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

Cool Contest!

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

For D1/D2, I had a solution I'd like to share.

Firstly, if any position exists such that a[i] > b[i], then obviously there's no solution.

Then, I iterated over the numbers from 1 to n, and for each i, I tried to find all the intervals centered around a position j such that a[j] = i. I then tried to extend it as much to the left and right as possible without messing any conditions up. I found that it you did this for all numbers from 1 to n in increasing order, then you'll either construct a valid solution or find that it's impossible to do so. You can optimize this a bit for D2 by binary searching how far to the left and right you'll extend your current position to and using range assignment and range query operations to check if the intervals you're using are okay (You can do that with a lazy segment tree).

In essence, it's similar to the official solution except you actually construct the solution in this case instead of determining if it's possible. Here's my submission: 236596139

It barely passes in time lol

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

    i solved D1/D2 in this way, but my code is shorter than yours

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

It will be better if F offers stronger samples.

I finished coding and passed samples in 15 min but got WA on #3, and failed to debug in remaining 30 min.

Anyway, A~D are enjoyable.

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

Nice problems. D2 systests were pretty weak though.

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

In problem E, how are we handling the case when path is outside of current subtree?

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

    If you reroot the tree to $$$x$$$ correctly, then each leaf in the segment tree will store the distance of a node to $$$x$$$ and this isn't limited to just $$$x$$$'s subtree. Doing a max query on all the non blocked intervals will then find the maximum distance to all reachable nodes.

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

Was the TL and ML for problem F a little tight in this contest? I see a lot of submissions here which have taken > 3 seconds.

I have roughly the same solution as the editorial, except that my graph is built with edges denoting >= relationships (instead of > relationships), then I find the SCCs of the graph, and the remainder of the construction is roughly the same. Or is there something else extremely slow about my code? I could get it to pass very narrowly with pragmas though.

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

    Maybe to solve the memmory problem,you should use tree chain dissection.

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

    But the time complexity is O(log^2n) However

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

    I ran into a similar problem. I tried implementing the editorial's idea and got TLE (later cloned the contest and checked that it passed in 4788ms), then changed how i did toposort and barely got AC.

    What seems to have happened is that they only had 1 AC solution that passed in 2s (1793ms in my testing) and used the standard "make the TL 2x the model solution", but the way they get the nodes to draw the edges is particularly smart, so it's very easy to make something inneficient compared to it and end up with double or triple the constant factor.

    By the way I did some testing with your code, it passed in 5038ms and 567200KB. Changing the bound for g from MXN * MXK * 3 to MXN * MXK * 2+20 makes it pass the memory limit (482900KB) and changing its type from vector to basic_string also makes it easily pass TL (2761ms).

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

      Thanks a lot for looking into this!

      I had no idea that there was such a substantial improvement possible with basic_string instead of vectors, thanks for pointing that out too!

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

E is a great problem, thank you for such a masterpiece!

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

236621743 can someone please give me any idea to improve this code as iam getting time limit exceeded for test3 of B.

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

orz

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

Can someone help me understand the solution for D.Why does there always exist a valid sequence of operations if we can satisfy the conditions for each element independently

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

How to solve problem E if the queries given online?

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

    The solution described in "Editorial 2" is online.

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

Nice Solutions.

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

Can someone help me in C? The first test gives me MLE and WA but in my computer gives me a correct answer 236711122

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

    Maybe you can try resubmit.

    I tested your solution and it is working fine (there is a bug in your solution though)

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

In Problem F, can anyone explain how they are achieving this exactly: "Given a path and a node, add a directed edge from the node to every node in that path"? I can't understand how they can add edges to (or from) all the nodes in the path, won't that take linear time?

Also, in this sentence "we can repeatedly add an edge from that node to the largest node we can" what does "largest" node mean?

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

    Imagine creating a binary lifting on the tree. You have $$$bin[i][0] = par[i]$$$, $$$bin[i][1] = par[par[i]]$$$, etc. Here, $$$bin[i][0]$$$ is an auxiliary node that has edges to $$$i$$$ and $$$par[i]$$$. $$$bin[i][1]$$$ is an auxiliary node that has edges to $$$bin[i][0]$$$ and $$$bin[par[i]][0]$$$. Note that this is equivalent to $$$bin[i][1]$$$ having edges to $$$i$$$, $$$par[i]$$$, and $$$par[par[i]]$$$. Similar to how you always jump up the largest power of 2 that fits when you perform binary lifting, you will always add an edge to the auxiliary node with the largest power of 2 that fits. This will always require at most $$$log N$$$ edge additions.

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

There is also a $$$O(nlogn)$$$ online sol for E (although with high constant).

Take the euler tour of the tree (the version where you insert again every time you go to a new node, exactly like this image taken from https://cp-algorithms.com/graph/lca.html ):

$$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Heights:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$$$

Lemma: the length of the diameter of a tree is $$$\max(height[a] - 2\cdot height[b] + height[c])$$$ for $$$a \leq b \leq c$$$, being $$$height[i]$$$ the height of the $$$i-th$$$ node in the euler tour. In that case, if $$$v[i]$$$ is the $$$i-th$$$ node in the euler tour, the endpoints of the diameter will be $$$v[a]$$$ and $$$v[c]$$$ and their lca will be $$$v[b]$$$. Proof is an exercise to the reader ;)

Using that lemma, we can ban segments like the solution 1 and if $$$x$$$ is the source node of our query, the answer will be $$$\max(height[a] - 2\cdot height[b] + height[c])$$$ for $$$a \leq b \leq c = x$$$ or for $$$x = a \leq b \leq c$$$, which can be done with a segtree. You just need to remember to rollback your updates after every query. Code: https://mirror.codeforces.com/contest/1904/submission/236721097

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

Hi can someone help me in figuring out why my two pointer approach for problem C is failing?

https://mirror.codeforces.com/contest/1904/submission/236751570

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

    Ive sorted the array and finding the sum which is closest to the ith element and then min of all their difference is the answer.. can anyone pointout the issue in my logic?

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

      You can try this case.

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

In problem C should I pick different (i,j) each time?

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

Or can someone share their two pointer approach for problem c?

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

Direction of the edges in the explanation for the solution for F are backwards

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

can someone please explain what does |a| notation mean in problem C? is it the length of array?

if so, why sorting array in this problem doesn't violate the condition of must pick some (i,j) such that 1≤i<j≤|a|?

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

    You are correct. |a| means the length of the array a.

    Essentially, in each operation, you can pick two different elements (can be equal) from the array and compute the absolute differences and put the result back to the array.

    So the order of the elements in the array does not matter and you are free to reorder the array (including sorting it).

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

      got it, thank you very much for clarification!

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

Can anyone explain me how edges are created in "problem F" in simple way and why are they created in that way(thought process)?

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

why do we need to find smallest ai satisfying ai≥v and greatest ai satisfying ai≤v in C why can't we go over all combinations of dif[i]-a[j] (where dif is the difference array of a of length n-1)

failed submission : https://mirror.codeforces.com/contest/1904/submission/236901057

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

Hi thanks for this contest and I hope this is not necro-posting but for $$$B$$$, don't you think it is enough to check if $$$p_i \geq a_{i+1}$$$ and then set the answer of $$$i$$$ equal to the answer of $$${i + 1}$$$? I have an implementation which you can check out 237039030.

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

My submission to problem F. Getting a TLE, unable to figure out why. Its similar to others', like MridulAhi (link). Can someone help?

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

good D2 and E

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

Could someone help to find what's wrong with my code https://mirror.codeforces.com/contest/1904/submission/237279390?

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

Can someone tell me why did we multiply 4001 in this solution

https://mirror.codeforces.com/contest/1904/submission/236534459

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

    It's not "multiply $$$4001$$$". As the official solution we need set<pair<int,int>>. But in fact we can use set, because every point with small $$$x, y$$$ can be "hashed" by $$$1000x + y$$$. Why it is true? Ok, let $$$(1000x + y)$$$ = $$$(1000z + t)$$$. Then $$$(y - t) = 0 \bmod 1000$$$. But if $$$y, t \leq 100$$$, then $$$y = t$$$ and so $$$x = z$$$. So in fact we just need to use $$$(x, y) <-> (k * x + y)$$$ for a big $$$k$$$.

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

why does this solution gives TLE on problem C 237622851

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

Can someone tell , in problem 3 why this code is not passing the test case 35 of test case 2 . https://mirror.codeforces.com/contest/1904/submission/237695706

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

    I think it is because your num might not be initialized for some test cases and it is reading the old value from the last test case.

    Removing it will now TLE on test 4: 237886642

    This is probably because you need to sort and erase elements from vector for each iteration of b[]

    Slightly change your code without changing your algorithm can get it accepted: 237887308

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

Problem B

Can anybody explain me why is the last sentence of tutorial is correct? If we have a [3, 8, 4, 5], then sorted it gonna be [3, 4, 5, 8] p — prefix sum [3, 7, 12, 20]. Lets calculate answer for i = 2, pi = 7 and largest aj (pi >= aj) is 5 and j = 2. But the correct answer is 3 because we can collect all 3 numbers if started with 4 -> 3, 5, 8

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

    The tutorial is correct. The answer is not j, but answer to j.

    If you start with 5, you can collect all other three. So if you start with 4, since prefix sum is 7, and it is greater than 5, you will have the same answer as if you start with 5, which is also three.

    So it is better to calculate the answer to larger j, then smaller j.

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

o

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

Please! Could someone explain me why this 240992164 gives a wrong answer

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

Task E is really cool!

Both of the intended solutions are really cute, the continuous interval is also really cute. Thank you for this task!

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

I got stuck on problem C for a while. For case k=2, after sorting A, I looked for closest elements of D[i] = A[i + 1] - A[i] in the array to check for the second minimum absolute difference. Well.. my mistake was choosing D[i] = A[i + 1] - A[i] (same as k=1) in the first place thinking that it helps to minimize, but i and j could actually be any pair. Of course, I didn't realize it and checked the editorial to finally understand my stupidity.

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

For problem C, case when k=1 why are we checking for minimum among a[i]-a[j] and a[i]s. Shouldn't it be the minimum among the former only as that's how the operation was defined?

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

    consider the case: 2 5 10 here according to you the answer will be 3 but the min of the whole array will be 2 therefore we need min(a[i], a[i]-a[j]).

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

Can someone explain the soln to B? I didn't understand the tutorial's soln.