Блог пользователя ninja_28

Автор ninja_28, история, 3 недели назад, По-английски

1498A - GCD Sum

Video Editorial

Author and Problemsetting: ninja_28
Editorialist: sigma_g

Hint
Hint 2
Hint 3
Solution
Corner cases
C++ solution
Python solution

1498B - Box Fitting

Video Editorial

Author and Editorialist: sigma_g
Problemsetting: ninja_28

Hint
Hint 2
Solution summary
Solution implementation
Another implementation
Proof of correctness - brief
Proof of correctness - elaborate
Alternate implementation with easier proof
Does this solution work when block widths are not a power of two?
C++ solution
Python solution
C++ solution - multiset
C++ solution for easier proof

1498C - Planar Reflections

Video Editorial

Author, Problemsetter and Editorialist: sigma_g

Hint 1
Solution idea
Solution details
Implementation details
Note
C++ solution
Python Iterative solution

1498D - Bananas in a Microwave

Video Editorial

Author: shash42
Problemsetting and Editorialist: sigma_g

Brute force solution
Optimizing the brute force: hint
Optimizing the brute force: hint 2
Optimizing the brute force: details
Optimized solution implementation
Common mistakes
C++ solution
Python solution

1498E - Two Houses

Author, Problemsetting and Editorialist: dixitgarg

Description
Hint1
Proof of unique topological sorting
Hint2
Proof
Hint3
C++ solution
Python solution

1498F - Christmas Game

Author: nikhil_c
Problemsetting and editorialist: sigma_g

How do we solve a standard Nim game on arrays?
How to solve tree nim game for one rooting if K = 1: classifying odd/even steps
How to solve tree nim game for one rooting if K = 1: how bad are even steps
Reducing tree nim game to linear array: the stair case nim
Extending to general K
Calculating the answer for all roots
C++ solution
Python solution
 
 
 
 
  • Проголосовать: нравится
  • +419
  • Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ninja_28 (previous revision, new revision, compare).

»
3 недели назад, # |
  Проголосовать: нравится +176 Проголосовать: не нравится

Excellent problem set! Need more Div2 rounds like these.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +57 Проголосовать: не нравится

Thanks for the lightning-fast and detailed editorial!

»
3 недели назад, # |
  Проголосовать: нравится +79 Проголосовать: не нравится

One of the best editorials I've ever seen if it's not the best...Congratulations to all the team behind this round !

»
3 недели назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

a SCC is a strongly connected component, but what is a compressed SCC?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ninja_28 (previous revision, new revision, compare).

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится +475 Проголосовать: не нравится

E can be solved in $$$O(n\log n)$$$ with ZERO queries.

Consider sorting by in degree. For the $$$i$$$th point, one can tell whether it is the last point of a SCC by comparing $$$i(i-1)/2$$$ with the sum of in degree of the first $$$i$$$ points.

So one can find all SCCs just by iterating through the degree array. Thus finding the answer.

Implementation

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +50 Проголосовать: не нравится

    Now i'm curios -- did authors know about this solution?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    Thank you for letting us know! Our previous version of E was suffering from this issue (answering without asking queries). So, we had to change the question to ask for the pair of bi-reachable houses with maximum indegree difference, not just any pair of bi-reachable houses. However, we were not aware that this version also suffers from the same issue.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Sorry, I'm curious why compare i * (i−1)/2 with the sum of in degree of the first i points can determine whether it is the last point of a SCC?

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

        When you process the very last node in an SCC, it means that all of the indegrees processed so far have been accounted for (no future node will ever have a directed edge towards a node at index $$$\le i$$$). So the sum of indegrees must be the same as the number of pairs processed so far, which is $$$\binom{i}{2} = i(i-1)/2$$$.

        Another way to think about this is to keep track of a count "how many of the indegrees I have processed so far are due to future nodes", and you know you are in the last node of an SCC when this count becomes zero. In fact, this is what dengyaotriangle does in the submission they linked.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится -48 Проголосовать: не нравится

    Yeah. I too had a feeling that it can be done with zero queries. But couldn't come up with this solution. :(

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ninja_28 (previous revision, new revision, compare).

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for B why using map fails but using freq arr pass ? frq arr : 111405356

map: 111388954

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You are missing the reference (&) Check this. Basically, you are changing a copy of the value but not the actual value

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can C be solved using iterative dp?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Obviously, 111382908 .

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you Explain this please??

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        dp[x][y]: Number of particles that bounce in the x-th plane with y ages passed from the beginning. So, if (y & 1) then all those are bouncing to the left, and to the right otherwise. It is not difficult to notice that if(y & 1)

        $$$dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... dp[i-1][0]$$$

        that leads to

        $$$dp[i][j] = dp[i-1][j-1] + dp[i][j-1]$$$

        the other case is analogous. Finally, I need to add dp[i][j] to ans for all i < n && j <= k, those are the cases when those particles don't bounce.

        • »
          »
          »
          »
          »
          3 недели назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I've done it during contest using O(K) memory and it obviously runs in O(NK) time complexity.

          Implementation

          Indeed it is kind of messy, during the contest it took me 30 minutes to debug and find out why it doesn't work for inputs with N = 1 or K = 1. (It can probably be improved somehow, but for now I'll handle them as special cases).

          Basically what I'm doing here is keeping prefixes and suffixes, where:

          Prefix — number of generated items if we start at 1, 2 ... i-1, i, and shoot in the right direction.

          Suffix — number of generated items if we start at i, i + 1 ... n-1, n, and shoot in the left direction

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Almost anything that can be solved using recursive dp can in principle be solved using iterative dp also.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

could you please help me?) this is my solution for problem C and i don't know what's wrong with it. thank you! 111401801

»
3 недели назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

The problems were really interesting . Great Work !

»
3 недели назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Beautiful editorial. I just loved the way they are explained step by step.

»
3 недели назад, # |
  Проголосовать: нравится -75 Проголосовать: не нравится

»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

In E problem, why this submission passed and this submission failed. I added following condition before asking query in AC submission.

Spoiler

Why is swapping making difference?

»
3 недели назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I guess this is an easier proof for Problem E not requiring discussion of things like SCC and top-sort:

So the solution is: if there exists pair $$$(A, B)$$$ such that $$$k_{A} \geq k_{B}$$$, and we can go from $$$A$$$ to $$$B$$$ (assumption), then we can go from $$$B$$$ to $$$A$$$. We have to prove this.

Case 1: if the edge is from $$$B$$$ to $$$A$$$ : since we can go from $$$A$$$ to $$$B$$$ (assumption), and from this edge we can go from $$$B$$$ to $$$A$$$, so yes.

Case 2: the edge is from $$$A$$$ to $$$B$$$. Now consider all other vertices $$$C$$$. We claim that there exists a $$$C$$$ such that edges $$$(B, C)$$$ and $$$(C, A)$$$ exist.

Proof: we can think of indegrees as score. Currently we have discovered edge $$$A$$$ to $$$B$$$ so score is $$$0:1$$$. We want score of $$$A$$$ to be greater than that of $$$B$$$. Now if for each $$$C$$$, the only edge combination that favourably increases score of $$$A$$$ is $$$(B, C)$$$ and $$$(C, A)$$$. Hence proved.

Is there any mistake or lack of rigour in this proof?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    What if we don't find any pair (A, B) such that $$$K_A \ge K_B$$$ and we can go from A to B ?

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится -60 Проголосовать: не нравится

      Haha do you see what you have written. If there don't exist such pairs then the answer is NONE of course lol. Cuz one of them has to be greater than the other. And you must find a bireachable pair. Lol.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Your proof avoids using SCC and topo-sort by not proving the part that requires them at all. So I would say your proof is incomplete because your proof makes assumptions.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    It can also be done this way :

    First we remove all the nodes with indegree 0 or outdegree 0. (After removing a node, we would again need to check for it and keep removing such nodes).

    Now if we have two nodes, $$$A$$$ and $$$B$$$, $$$k_A >= k_B$$$ then I claim that we can go from $$$B$$$ to $$$A$$$ (Yes! without any other assumption).

    Number of nodes reachable from $$$B$$$ = $$$n - k_B$$$ and

    Number of nodes reachable to $$$A$$$ = $$$k_A + 1$$$

    If we can't reach from $$$B$$$ to $$$A$$$, total nodes would be $$$n + 1 + k_A - k_B > n$$$ , its not possible. So we can go from $$$B$$$ to $$$A$$$.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      I didn't require the assumption to prove that we can go from $$$B$$$ to $$$A$$$. I required it to prove that they form a bidirectional pair. I proved that we can go from $$$B$$$ to $$$A$$$ if $$$k_{A} \geq k_{B}$$$ and then using the assumption I proved bidirectional thing.

»
3 недели назад, # |
Rev. 4   Проголосовать: нравится -9 Проголосовать: не нравится

Wonderfull editorial with clear explanations

»
3 недели назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

why i can't hack after system testing?

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Nice Editorial it helps me so much for solving rest problems which i m not able to do... Thanks

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In problem E, can anyone please tell why did I receive wrong answer on test 2, I just implemented the same thing using multiset, LINK.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ninja_28 (previous revision, new revision, compare).

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

I framed D in a slightly different way which might be more straightforward to you if you're so inclined.

Essentially, for each timestep, we want to solve a version of the coin-change DP problem where we have a finite number of coins all of the same value. We want to do this in O(m). If there were an unlimited number of the coin, this is just the coin-change DP problem, and you just iterate left-to-right, storing DP[i] as 1 if you can get there, 0 if you can't.

Since we only have a finite number of coins, we still iterate left-to-right, but instead of storing 1 or 0, we store in DP[i] the minimum number of coins used to reach that value.

To recap, iterate i from 0 to m. if DP[i] != -1 and DP[i] < y, then DP[f(i)] = DP[i] + 1. Where f(i) is applying the function (either addition or multiplication) once.

111392313

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi,

    Can you please explain this line, DP[targ] = max(DP[j]-1, DP[targ]);

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh yeah, sorry, that must be confusing.

      In my writeup I said to store in DP[i] the minimum number of coins we need to use to reach that value.

      In my code I actually store in DP[i] the maximum number of coins NOT used in order to reach that value. So if we call the value in my writeup k, then the value in my code is just y - k, and all the reachable DP[i] starts at y instead of 0.

      The reason I did it that is so that taking the max would automatically overwrite the existing DP[targ] if DP[targ] == -1, so I don't have to add the if DP[targ] == -1.

»
3 недели назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Finally i reached pupil after 16 contests (including this):)

»
3 недели назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

C C can be done with $$$O(n)$$$ memory too!

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится -53 Проголосовать: не нравится

    Love the comments from grey guys, giving improvements on C problems! Climb out of your hole first

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      Show some respect.

      He is only helping and you are encouraging him to think that he can do above level question only when he will be at that level.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ninja_28 (previous revision, new revision, compare).

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Really quick and well explained editorial

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

can anyone tell whats wrong in my logic for part C

solve(n,k)=1 when n==0 or k==1

and

solve(n,k)=1+solve(0,k-1)+solve(1,k-1)+solve(2,k-1)............solve(n-1,k-1) when n>0&&k>1

my logic for solve(n,k) is as follows:

if present decay age is k and it passes through n planes then it will lead to new particles as follows

particle generated at plane 1 will now pass through no plane leading to increase in solution by solve(0,k-1)

particle generated at plane 2 will now pass through one plane leading to increase in solution by solve(1,k-1)

similarly particle generated at plane i will increase solution by solve(i-1,k-1).

so my formula comes out to be:

solve(n,k)=1+solve(0,k-1)+solve(1,k-1)+solve(2,k-1)............solve(n-1,k-1)

But my logic was giving wrong answer.

Can anyone tell whats wrong with the logic???

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Problems similar to F have appeared before. Staircase nim itself is a common concept, and Move the Coins is a problem with K=1 with updates. Here's a more in-depth tutorial about staircase nim and this problem. This idea generalizes really easily as nodes with depths which have different residues mod k are independent (this isn't really mentioned in the editorial even though it's a pretty important fact).

»
3 недели назад, # |
Rev. 5   Проголосовать: нравится +21 Проголосовать: не нравится

Solution for problem C with only 2 dimensions:

The idea

My full submission.

Few lines of Code

UPD: Of course this can be optimized to get rid of the second dimension since we only need the information from states with $$$age$$$ and $$$age - 1$$$, this improves our space complexity to $$$O(n)$$$, code.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Fixed! :D

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    very well explained mate thanks:)

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Hey can you please explain the order of evaluation you used. I was looping through 'hits' first then 'age' like this:

    for hits in range(1,n+1):
     for age in range(2,k+1):
      dp[hits][age]=dp[hits-1][age]+dp[n-hits][age-1]
    

    and got wrong answer and changed it and got correct answer. I am a bit confused.

    • »
      »
      »
      3 недели назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      In this order sometimes you will use the value of the state $$$[n - hits][age - 1]$$$ while it has not been calculated yet.

      How can this happen?

      When $$$hits$$$ is small enough: $$$n - hits \gt hits$$$, and since you never reached any $$$dp[i][j]$$$ where $$$i \gt hits$$$ and any $$$j$$$ from $$$2$$$ to $$$k$$$ your code will use $$$dp[n - hits][age - 1]$$$ before it even gets calculated.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, As you have explained the reason for not changing the loop order below. I got that part but if we keep the order state above in your code.

    where n-hits > hits , we also need do[n-hits][age-1] to calculate dp[hits][age] which is not calculated yet.
    
    Could you please tell me what am I doing wrong here?
    
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Notice that the state $$$[n - hits][age - 1]$$$ is calculated before state $$$[hits][age]$$$, because we had already calculated all the states $$$[i][age - 1]$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Thank you for the quick response.
        I thought it as dp[n-hits][age] instead of dp[n-hits][age-1].
        You are right, we have already calculated states values for age-1 to use it in dp[n-hits][age-1] for the calculation of dp[hits][age].
        
  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Great approach, the key here probably was to understand that the direction of the particle doesn't matter on the number of planks in front of it.

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for sharing

»
3 недели назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

what is complexcity of this code it should get tle

include <bits/stdc++.h>

using namespace std;

long long int gcd_sum(long long int num) { // returns gcd-sum long long int tmp = num, digitsum = 0;

while (tmp > 0) {
    digitsum += tmp % 10;
    tmp /= 10;
}

long long int gcd = __gcd(num, digitsum);
return gcd;

}

int main(void) { int t; cin >> t;

while (t--) {
    long long int n;
    cin >> n;
    if (gcd_sum(n) != 1) {
        cout << n << endl;
    } else if (gcd_sum(n + 1) != 1) {
        cout << n + 1 << endl;
    } else if (gcd_sum(n + 2) != 1) {
        cout << n + 2 << endl;
    }
}
return 0;

}

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's $$$O(length(n))$$$. You can search for the Euclidean Algorithm for the time complexity of __gcd.

    For finding the sum of digits of n: $$$O(length(n))$$$.

    For finding the gcd: $$$O(\log length(n))$$$.

    The total complexity: $$$O(length(n) + \log length(n))$$$, and then it's $$$O(length(n))$$$.

    Here $$$length(n)$$$ is the number of digits in $$$n$$$.

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

Thank you for the great Editorial and Video!!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E had 100 ACs in just the last 10 mins damn.

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Every editorial should be like this. Awesome job.

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

B was good this time it required more thinking than just straight implementation

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

deleted

»
3 недели назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

1498C - Planar Reflections can also be solved without using DP. Here is my solution 111412008 where i just traverse the given setup in ZigZag fashion.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It is arguably still a DP solution, but this is a nice way to condense it to just N of memory.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      That's true, but You don't need a conventional 2/3 state Dynamic Programming approach to solve this is the point i was trying to make as the editorial clearly used that concept and it's not easy for a person to understand who doesn't know DP yet.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Solved problem 1498C - Planar Reflections using 2 states only. You don't need the 'direction' state or dimension if you observe the following.

Hitting the $$$i^{th}$$$ wall (/plane) in the opposite direction at any moment is equivalent to hitting $$$n-i+1^{th}$$$ wall in the forward direction at the same moment.

Thus the following short recursive DP function works perfectly, with calling the function with call(n, k)

ll call(int front, int k){
    // front = how many walls are in front.
    if(k == 1){
        return 1; // This particle itself, which is about to die
    }
    if(front == 0){
        return 1; // Again, this particle itself, which will go to infinity and beyond...
    }
    if(dp[front][k] != -1) return dp[front][k];
    ll ret = call(front - 1, k) + call(n - front, k - 1); // keep going forward + decay and turn back, aided with the observation mentioned above.
    if (ret >= modd) ret -= modd;
    return dp[front][k] = ret;
 
}

My submission 111384789

Also, looks like the spoilers get broken for comments (looks fine on the post). It would be nice if it gets fixed.

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Best editorial guys.. Keep up the good work

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

On problem E I proved my solution on a different approach.

Lemma: Let A and B be nodes such that $$$k[a] <= k[b]$$$. Then, $$$B$$$ is reachable from $$$A$$$.

Proof:

Case 1: (If there is a directed edge from $$$A$$$ to $$$B$$$.)

There is nothing more to be done.

Case 2: (If there is not a directed edge from $$$A$$$ to $$$B$$$.)

Let $$$X_i$$$ be the set of nodes such that there exists a directed edge from every element of $$$X_i$$$ to $$$I$$$. Also, let $$$Y_i$$$ be the set of nodes such that there exists a directed edge from $$$I$$$ to every element of $$$Y_i$$$. Let's prove that there is at least one node that belongs to $$$Y_a$$$ and $$$X_b$$$. We have:

$$$|Y_a| + |X_b| = (n \; - \; 1 - \; k[a]) \; + \; k[b] = \; n \; - \; 1 + \; (k[b] \; - \; k[a]) \;>\; n - 2$$$

Using Dirichlet Principle, as $$$B$$$ does not belong to $$$Y_a$$$ and $$$A$$$ does not belong to $$$X_b$$$, we have that there are n — 2 nodes and the sum of elements of $$$Y_a$$$ and $$$X_b$$$ is bigger than n — 2. So, they have an element in common. Then, let $$$X$$$ be this element. There is an edge from $$$A$$$ to $$$X$$$ and from $$$X$$$ to $$$B$$$. We have a path from $$$A$$$ to $$$B$$$, finishing our proof.

I used this and for every pair of nodes, verified if there is a path between $$$B$$$ and $$$A$$$ (assuming that $$$k[a] \; <= \; k[b]$$$).

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Nice proof! There's two things I would like to ask about:

    1. Why is the sum $$$|Y_a| + |X_b| \geq n - 2$$$ and not $$$\geq n - 1$$$? (given that $$$k[b] - k[a]$$$ could be at least $$$0$$$).

    2. On this line: "we have that there are n — 2 nodes and the sum of elements of $$$Y_a$$$ and $$$X_b$$$ is bigger than n — 2". Why can we say that it is bigger than $$$n - 2$$$? supposing the inequality you mentioned in 1. is $$$\geq n - 2$$$, would the statement be "bigger or equal to $$$n - 2$$$"? (or "bigger or equal to $$$n - 1$$$" if that's the correct right-hand side of the inequality). In such case, how can show that there'll be at least one element in common?

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Thanks!

      1: Actually the correct result was supposed to be:

      $$$|Y_a| \; + \; |X_b| \; = \; n \; - \; 1 \; + \; (k[b] \; - \; k[a]) \; >= \; n \; - \; 1 \; > \; n \; - \; 2$$$

      Because the lemma stated that $$$k[a] <= k[b]$$$. So, the sum of $$$Y_a$$$ and $$$X_b$$$ sizes is strictly bigger than $$$n - 2$$$. Sorry for that, my mistake.

      2: I will try to explain it a bit better. Because of the assumption of the case (If there is not a directed edge from $$$A$$$ to $$$B$$$), we have that $$$B$$$ does not belong to $$$Y_a$$$ and $$$A$$$ also does not belong to $$$Y_a$$$. Then, there are at most $$$n - 2$$$ different elements in $$$Y_a$$$. Similarly, there are at most $$$n - 2$$$ different elements in $$$X_b$$$.

      Suppose they have no elements in common. Then, we must have at least $$$|Y_a| \; + \; |X_b|$$$ different nodes other than $$$A$$$ and $$$B$$$. But, the graph has at most $$$n - 2$$$ nodes other than $$$A$$$ and $$$B$$$. Then, we get, from the above equation:

      $$$n - 2 < |Y_a| + |X_b| <= n - 2$$$

      By contradiction, they must have at least a common element.

      I hope that helps!

»
3 недели назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Awesome editorial and problem set. Really appreciate the quick and neat editorials and videos. It shows how much effort you people put into this round. Congrats and keep up the good work.

»
3 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Love this great problem set for Div2 and the detailed editorial!

»
3 недели назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

we need more editorials like this on the platform

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me why this solution 111375843 for problem B is wrong. I solved using 2 pointers. Thanks in advance :)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice editorial!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why don't you guys ever give solutions in java??

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tutorials are so neat and detailed.Loved the way this contest was handled :)

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My solution for C was correct, but my code crashed because I was exceeding stack limit on my pc. How can I increase stack size on windows? I'd seen a few blogs, nothing worked so far.

EDIT: It worked, if anyone needs help feel free to DM me.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Which test can broke solve which based on summing all blocks and dividing it into lenght of the box, and of course, adding 1 if some blocks left(I am about problem B)?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The tutorials are really awesome and beginner friendly. Thanks.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the problem C in Python using recursion?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C I made ll dp[1001][1001][2] then I wanted to write ll &ret = dp[i][j][d]; but accidentally I wrote ll &ret = dp[i][j][k]; it got Accepted but..

$$$d <= 1$$$

$$$k <= 1000$$$

so when I call ll &ret = dp[i][j][k]; it's like ll &ret = dp[1000][1000][1000]

when I put vector instead of the array I got RTE

Can anyone explain why ll &ret = dp[1000][1000][1000] didn't get RTE or MLE because it's large ($$$10^9$$$) and the array is ll dp[1001][1001][2] ?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the cool editorial .

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me why my code for C gives WA? https://codeforces.com/contest/1498/submission/111406325

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great Editorial! I love how there's hints for the solutions so that you can actually figure it out by yourself. There should be more editorials like this

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Awsome Problem set!!!

»
3 недели назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

My code is wrong and it gives TLE but pass the example. And I thought my theory is wrong instead of looking again at my implementation and stuck. :<

»
3 недели назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Personally, I think C Problem can be solved in linear space in a very concise and "clean" way:

Solution Idea

Forgive me if that picture is simply too ugly :(

We give special treatment to $$$n=1$$$ or $$$k=1$$$ cases, and in other cases, we start by an array of length $$$n$$$, initialized 1,0,0,...,0 and calculate the partial sum of that array each step, after every calculation we reverse the array and do the exact same thing, finally terminate after $$$k$$$ rounds.

so the time complexity of this solution is $$$\Theta(nk)$$$, as you can see in my contest submissions :D

Actually, we can prove that there always exists a recursion in shape of $$$a_i=\sum_{\Delta=1}^{n}c_{\Delta}a_{i-\Delta}$$$, in the angle of view which $$$n$$$ is designated and $$$k$$$ varies as a sequence, which can be easily calculated in $$$\Theta(n^3\log k)$$$ time and potentially be calculated in $$$\Theta(n\log n\log k)$$$ time using polynomials and other (highly non-trivial) tricks.

For those who are Chinese, I think there's a website and several problems about this.

Well, me myself isn't very good at maths and especially polynomials, additionally I'm learning literacy class now, so I don't really understand this...... QwQ

ALSO, DON'T EVER TRY TO USE double TO CALCULATE INTEGER AND FRACTION CEILINGS WHEN long long IS SUFFICIENT ENOUGH.

»
3 недели назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

C can also solved by finding regularity.We can find how many copies will be produced by all the particles going in the same direction each time.And their sum is the answer.Sorry my English is so poor.

Code:111393762

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

omg i think this is one of the best editorials on this platform!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for Problem D, we only need one res array (res[i] == -1 means not visited), as in a 0-1 knapsack problem, instead of iterating from 0 to m, we iterate from m down to 0, therefore no need to keep two visited arrays.

check my code here: 111428128

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for problem B i wrote the same multiset approach, but it faield on Pretset 2. Exactly same approach of multiset..

multisetst; for (int i = 1; i <= n; i++) { cin >> a[i]; st.insert(a[i]); // mp[a[i]]++; }

int leftover = k;
int ans = 1;
while (!st.empty()) {
    auto f = st.upper_bound(leftover);
    if (f == st.begin()) {
       leftover = k;
       ans++;
    }
    else {
       // if (f == st.end())
       f--;

       st.erase(st.find(*f));
       leftover -= *f;
       // db(*f, st.size(), leftover);
    }
}
cout << ans << endl;
  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Wrong
    Right
    Reason
    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Though the reason stated by you doesn't apply..It was failing because of some constant global variable issue.Accessing afterwards deleting or before doesn;t creates issue until reference poitner is in memory.

      *f is in memory till end brace so we can access that anywhere till that

  • »
    »
    3 недели назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    PS: Reason given by Dush1729 is right

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

I really liked the contest specially problem E. I still haven’t read to tutorial but in my solution I didn’t use top-sort. First I proved for any two vertices in a tournament like a and b if the output degree of a is at least as big as the output degree of b, b is reachable from a. (The proof would be kinda long if I write but it isn’t so hard using induction and u need to know that each tournament graph has a king but it might have an easier solution. Still if u couldn’t and wanted the answer just comment it and I will explain) After this it’s easy. For every two vertices we will push back the difference between k of those in a vector and then sort it from big to small and we check the first which is possible. Here is my code if it will help( I used set though) 111401603

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Tutorial is just awesome, need more div2 problems and tutorials like this.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem D , Making x long double and using x = x' /(1e5) with inbuilt ceil function is giving me Wrong Answer

However ,

Using x as long long and with the "incline ceil function" given in the editorial is getting accepted .

Can someone please help me out and explain why this is happening ?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    There might be precision issues with a fractional value of the multiplier. The integral ceil function in the editorial bypasses any such issues.

»
3 недели назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Actually during contest I did not read the question D properly (entirely my fault). I thought that for type 2 operation x can be between 1 and 10^5m instead of 10^5 to 10^5*m (x / 1e5 >= 1). Only reread at the end of contest (b4 7 minutes of contest end). Suppose x can be a fraction value as well for the type 2 operation. i.e. 1 <= x <= 10^5 * m. Is there a solution ?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just consider the case when it's not that the block sizes for problem 2 are not in powers of 2 then can anyone think of a way to implement the DP solution?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

really loved the contest and step by step explanation in editorials

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Peace be upon you ! I really liked this contest and it's Editorial. Good job ! I'm waiting for more contests from you :)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please explain the scenario in

$$$E$$$

when there is no solution ? We have proven that the topological sort of the SCC is unique, and that the indegree of vertices in those SCC increases as we go from left to right in the topological sort enumeration, but is it always possible to topological sort this graph ?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There is no solution when the input graph is acyclic.

    but is it always possible to topological sort this graph ?

    It is always possible to do a topological sort of the condensation graph because it is acyclic.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please share the reason the condensed graph is acyclic ?

      • »
        »
        »
        »
        3 недели назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        If some strongly connected components are in a cycle, they wouldn't be called strongly connected components because the entire cycle would make a (subset of a) single strongly connected component.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1498/submission/111389903 Can someone please help me in figuring out why this gave a TLE?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great problemsetting and Excellent tutorial! Thanks to this round :)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

From the editorial can anyone explain that in the ith timestamp why every unvisited node (upto i-1 th timestamp) is visited atmost once? Let's assume that the operation is t=1 and "no" is an unvisited node upto i-1 th timestamp.Then "no" can get visited from no-x,no-2*x,no-3*x.... (assuming all of them have been visited upto i-1th step). I am telling this according to the solution given in the editorial. Can anyone please tell me where I am wrong?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    According to the solution in the editorial, no (an unvisited node) will only be visited from its closest already visited node.

    The iteration starting from no-3x will stop at no-2x (since it's an already visited node). The iteration starting from no-2x will stop at no-x (since it's an already visited node). So, only the iteration starting from no-x will actually reach no.

»
3 недели назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I was stuck at problem D....

S;G fans only.
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Help needed in Problem C !
When a particle of decay age $$$k$$$ hits the $$$n^{th}$$$ plane, it produces a particle with decay age $$$k-1$$$ directed towards the $$${(n-1)}^{th}$$$ plane (if it exists), which on hitting the $$${(n-1)}^{th}$$$ plane produces a particle of decay age $$$k-2$$$ (if $$$k>2$$$) directed towards the $$$n^{th}$$$ plane, this goes on until the decay age of the produced particles is greater than $$$1$$$.
How the solution in the editorial is able to count such particles with decay age $$$k-2$$$ & the consequently produced particles when a particle of decay age $$$k$$$ hits the $$$n^{th}$$$ plane?

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    So basically in dp transition step we are summing up the dp[curr+1][k][dir] and dp[curr-1][k-1][1-dir] here:

    if (curr < n)
      ans += solve(curr + 1, k, dir) — 1;
    
    ans %= mod;
    
    if (curr > 1)
       ans += solve(curr — 1, k — 1, 1 — dir) — 1;
    
    ans %= mod;
    

    These two dp states will take care of particles you are talking about because a dp state of n,k,dir indicates the total number of particles (at the end of the simulation) when one particle of decay age k hits the n-th plane in the direction d.

    P.S: If still not clear I would recommend to watch video editorial for this problem where we have clearly explained about how to think of dp states.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the wonderful solution!

Realllllly fast!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got WA on D because I used ceil() instead of dividing integers :(

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think in D it is written to stop when we get first visited[ind]=1; But I think that is not required at all. We can do only 1 operation and stop. Maintain one num array as the minimum operation required to reach this point at this timestamp. Now suppose we want to do one operation if(num[ind]+1<=y) then only we can do this operation and update the next num and visited nxt as true.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes you are right!. We found given implementation more cleaner so mentioned that in the editorial.

  • »
    »
    3 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Additionally, in the editorial, I wanted to highlight the subtle difference between the TLE and the accepted solution, that is why I did not cover this approach.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why can't be firstly sort the array of widths and then run a for loop from which we pick the greatest element not visited till now and then pick the elements from the start which can be accomodated with the greatest we've selected till now ?

https://codeforces.com/contest/1498/submission/111442457

LINK TO MY SUBMISSION

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody explain problem F a bit more? I understood everything related to staircase NIM but now we have the problem of finding for each node the xorsum of values at nodes that have $$$d' = d/k$$$ odd. How can we do that an maintain the answers for all roots?

  • »
    »
    12 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you find any resources to explain it. I have the same question with you. :<D

  • »
    »
    11 дней назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, I have figured out this problem.

    Let's define f[u][i] is a state that root is 1, and the deep is i that value ralated to Hey, I have figured this problem.

    It is a type of root-changed(I am not sure about this word) DP.

    Whatever xD

    Let's define f[u][i] is a state that root is 1, and we just think about some nodes in the subtree of u and the distance with node u remainder by (2*K) equal to i. The value of f[u][i] is function of sg.

    dp[u][i] is a state that root is u, and we just think about some nodes distance with node u remainder by(2*k) equal to i. The value of dp[u][i] is function of sg.

    ——————— Firstly, we can calculate f[u][i] in this transfer equation as follows. The time complexity is O(n*k). Define u is the father of v

    f[u][i] ^= f[v][i-1];

    Obviously, dp[1] = f[1].

    Secondly, if we just think about the relationship between u(father of v) and v. We can find the value is about:

    dp[v][i] = f[v][i] ^ dp[u][i-1] ^ f[v][i-2];

    We also can calculate them by dfs. The time complexity is O(n*k).

»
3 недели назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

In Problem B , Use a priority queue (better solution than any solution mentioned above . very easy implementation . Thank me later !

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Some solutions which passed system cases are now getting WA on E on later added test cases. So isn't this matter of luck for people who submit wrong codes and got accepted? It happened to me twice in recent contests :( (Didn't code my logic, thinking it to get WA, but another guy submitted it and passed system tests and failing on later added test cases but still getting the points)

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Seems like there is a little typo in the C++ solution of D(in the ceiling function) which is causing compilation error.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sorry about it! This seems to be a common issue across multiple editorials, for example, the editorial of problem C here.

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah, I think it's because of unicode quotations marks instead of ASCII quotation marks. Here the subtraction (-) is being replaced by a dash.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://www.youtube.com/watch?v=FJ9tVXReosM Problem C in Hindi Simple Recursion

int func(int forward, int backward, int decay){

if(decay==1 || forward ==0){
     return dp[forward][decay] =1;
 }

 if(dp[forward][decay]!=-1){

     return dp[forward][decay];
 }

 return dp[forward][decay] = (func(backward,forward,decay-1) + func(forward-1,backward+1,decay))%mod;

}

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One of the best editorials I have seen off late. Great work!

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What are odd steps and even steps in problem F ?

UPD : Understood after reading this blog

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In planar reflections problem, can any one tell why ans was initialized to two in recursive c++ approach?

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C can be much more simple. It can simply be solved using 2-state dp. dp(i, j) implies the total number of particles generated if a particle is needed to pass i sheets with current age j. As the opposite direction is symmetric the simple reccurence comes out to be dp(i,j) = dp(i — 1, j) + dp(n — i, j — 1); (n — i bcz if there are i sheets needed to be crossed rightwards there will be n — i sheets for the newly born particle in opp. direction to be crossed).

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think we don't need binary search in Alternate implementation with easier proof of B(Box Fitting), It is sufficient to find least height required for every suffix of Ci and required height will be maximum of all possible least heights. here is the Solution.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Binary search is used to reduce time complexity to O(nlogn).

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      At first with Binary Search, Time Complexity was O(n+log(Wmax)log(n)). now if we don't do Binary search, then it will be O(n+log(Wmax)). Please observe carefully, I am talking about Editorial Section containing Alternate implementation with easier proof in problem B (Box fitting).

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It will be O(n + log(Wmax)n), I believe.

        Also can you explain why log(Wmax) came in O(n + log(Wmax)log(n)) came in binary search. I did not understand it.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

При решении задачи В методом бинарного поиска мы подбираем высоту коробки и проверяем войдут ли в нее все прямоугольники. Я не могу понять, как учесть то пространство, которое уже было использовано. Как работает эта формула из разбора ci=ci+2×ci+1+4×ci+2…. Поясните кто-нибудь. Спасибо.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Two states solution for problem C

#include <bits/stdc++.h>

using namespace std;

int n, k, mod = 1e9+7;
int cache[1005][1005];

int dfs(int i, int k){
    if(i == 0 || k == 1) return 1;
    if(cache[i][k] != -1) return cache[i][k];
    int ans = dfs(i-1, k) + dfs(n-i, k-1);
    ans %= mod;
    cache[i][k] = ans;
    return ans;
}

void solve(){
    cin >> n >> k;
    memset(cache, -1, sizeof(cache));
    cout << dfs(n, k) << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
        solve();
}

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Unfortunately the Python solution to problem E has been uphacked: https://codeforces.com/contest/1498/submission/111571072

It TLEs with 125000 write/flush?

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It has not been uphacked. Test 29 was already in systests. We need to submit the code with Python 3. AC submission. Though, I am not sure why PyPy3 and Python 3 give different I/O rates.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Here's a sort of "meta-solution" I came up with for problem E. It's not really rigorous, but it is simple :)

First, remove all vertices that cannot be in the answer by repeatedly removing all vertices whose indegree is n-1 (and update n after that).

Now, consider a pair of vertices A and B, whose indegree difference is ID. Now, if you decide to query a pair of vertices C and D whose indegree difference is less than ID, there is a risk that A and B are the answer, since if there exists at least one graph that matches the input, and in this graph A and B are mutually reachable, you cannot ignore the possibility that this graph is in fact the graph that is given. So in a sense, we are forced to query the pair of vertices whose indegree difference is ID before we can query a pair of vertices whose indegree difference is less than ID. And, if we are forced to query it, and the answer is "Yes", we don't have any other option than to output this pair as the answer, since we don't have any other candidates.

»
3 недели назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Certain mistakes id like to point out in question and Editorial #711 Div. 2B. Box fitting

The values of Wi can only be 2**x for some non-negative integer x, but it also says wi lies between 1 and 10**6, now there is no non-negative integer X, such that 2**x==10**6, as Log2(10**6)==19.931568569324174 Thus there is a mistake in the question framing and also if there are only 20 distinct values of wi as given in the solution implementation then the upper limit of Wi must be 524288 which is equal to 2**19 and hence we x belongs to [0,19] inclusive.

Also in the solution, it is mentioned there are only 20 distinct values for Wi as Wi has an upper limit of 10**9 which is again wrong as W has an upper limit of 10**9, another mistake :(

Please do not do such mistakes.

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain to me please why am I getting the wrong answer in D if I use this operation function instead of theirs?

auto operation = [&] (long long &curr, double mx) {
     if (t == 1) {
          curr = curr + (int)ceil(mx);
     } else {
         curr = ceil((double)curr * mx);
     }
};
where ceil is standard cpp function and mx = x[i]/1e5.

Any kind of help is highly appreciated.

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There might be precision issues with a fractional value of the multiplier. The integral ceil function in the editorial does not mess around with fractions, and is thus guaranteed to always give the correct ceil.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice explanations!!

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello guys, this is my problem C solution 'Planar Reflections'. I have optimized it as much as I can... but it is still not passing the test case 3 basically when n and k both are 1000. Can anyone help me what else can I do in my code to optimize it further without changing the idea behind my code thought. Basically what I'm doing here is I'm keeping count on "starting point" -> "st" and "direction" -> "dir" and obviously "decay age" -> "d_age". and then if particle is going towards right(1) I change the direction to left(0) and vice-versa and keeping the sum in "sum" variable.

this is my code.

// I'm not including my macros...I hope you will get it
int _count = 0;
int dp_arr[1001][1001];

int totalReflection(int n, int st, int dir, int d_age) {
    //_count += 1;
    if (dp_arr[st][d_age] != -1)
        return dp_arr[st][d_age];

    int sum = 1;
    if (d_age == 1)
        return sum;

    if (dir == 1) {
        for (int i = st + 1; i <= n; i++) {
            sum = (sum + totalReflection(n, i, !dir, d_age - 1)) % mod;
        }
    } else {
        for (int i = st - 1; i > 0; i--) {
            sum = (sum + totalReflection(n, i, !dir, d_age - 1)) % mod;
        }
    }

    return dp_arr[st][d_age] = sum;
}

void solve() {

    int n, k;
    cin >> n >> k;

    memset(dp_arr, -1, sizeof(dp_arr));
    int result_num = totalReflection(n, 0, 1, k);
    cout << result_num << nline;
    //cout<<"count: "<<_count<<nline;
    _count = 0;

}

int32_t main() {

    fast;

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    clock_t start_time, end_time;
    start_time = clock();

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    end_time = clock();
    //cout << "Time Taken: " << (end_time - start_time) / CLOCKS_PER_SEC << endl;
    return 0;
}

111652321

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, Can Someone help me understand how to solve Problem E. I don't understand what is SCC and compressed SCC. Can some one guide me what i need to learn in prior to understand the solution?

»
2 недели назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Problem C Video Editorial : https://www.youtube.com/watch?v=_iSd--gtSpI (Recursive DP in detail explanation)

»
13 дней назад, # |
Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

I have a problem in B here . I used multiset and did quite same but still got TLE . (the only difference in my approach is I used lower_bound instead of upper_bound) .. can anyone tell me why its happening like this? i am posting the link to my code here https://codeforces.com/contest/1498/submission/112199870 thanks in advanced !!

  • »
    »
    13 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

    can anyone help me in figuiring out why its giving TLE? problem B i used multiset and lower_bound

    temp=0;
            out=1;
            auto it = s1.end();it--;
            temp+=(*it);
            s1.erase(it);
            while(s1.empty()==0)
            {                        
                if( (temp + *(s1.begin())) > W)
                {
                    temp=0;
                    out++;
                    it = s1.end();it--;
                    temp+=(*it);s1.erase(it);
                    continue;
                }
                it=s1.lower_bound(W-temp);
                if(it==s1.end())
                {
                    it--;
                    temp+=(*it);
                    s1.erase(it);
                    continue;
                }
                if((*it)<=W-temp)
                {
                    temp+=(*it);
                    s1.erase(it);
                }
            }
            cout<<out<<"\n";
»
9 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Author solution in Python for Task D does not meet Time Limit. :(

  • »
    »
    9 дней назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    It does. All the solutions we have posted in the editorial are verified on Polygon. You have to submit this code in PyPy3.

»
5 дней назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Best Editorial I have ever seen! Keep it up!

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Moreover, any two distinct rectangles must not overlap, i. e., any two distinct rectangles must have zero intersection area.

For problem B,please explain this.