applepi216's blog

Codeforces Round 986 (Div. 2) Editorial
By applepi216, 4 days ago, In English

Thank you everyone for participating in the round! We hope you enjoyed the problems :)

2028A - Alice's Adventures in ''Chess''

Hint
Solution
Code

2028B - Alice's Adventures in Permuting

Hint
Solution
Code

2028C - Alice's Adventures in Cutting Cake

Hint 1
Hint 2
Solution
Code

2028D - Alice's Adventures in Cards

Hint
Solution
Code
Bonus

2028E - Alice's Adventures in the Rabbit Hole

Hint 1
Hint 2
Hint 3
Solution
Code

2028F - Alice's Adventures in Addition

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code
  • Vote: I like it
  • +37
  • Vote: I do not like it

»
4 days ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

I dont understand what the meaning of 32MB in F. I don't like problems with too many meaningless details (I believe the main idea of F is not the memory optimisation, or maybe this retarded problem does not have main idea at all?)

→ Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    same goes for problem B. why put 10^18, simply 10 ^ 9 was sufficient. But no, the author has to make us deal with overflows.

    → Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    I'd call F a "DP Optimization" problem. There's a fairly short $$$O(n^2 m)$$$ solution, and then the question becomes how to optimize it. Memory optimization is a real thing that people care about a lot, and here I think it's pretty cool how it naturally falls out of the analysis.

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you for such a cool Problem F, I hope in the future I will learn to solve this)

      → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      I'm trying to understand what you are talking about. I think the only main idea should be, the number of $$$\times$$$ operation will not exceed $$$\log_2 m$$$, and other parts are just trivial knapsack DP (including bitset optimisation)

      So why not just set $$$n,m \le 5000$$$ with 512MB ML to let the $$$\mathcal O(nm \log m)$$$ solution pass? In this case I will call this a cute problem (but still not that good).

      The bitset optimisation is ok, but the memory optimisation is really bad. If one knows the $$$\mathcal O(\dfrac{nm \log m}{w})$$$ solution, he must know how to optimize the memory, in this case the tight ML just increases the difficulty of implementation, which is really annoying.

      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it +62 Vote: I do not like it

        that's why it's problem F

        → Reply
        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it -24 Vote: I do not like it

          A good problem F shouldn't be difficult on optimisation unrelated to the main idea

          → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Actually, I don't think the memory optimization is an issue. It is pretty easy to see that you can only keep the last log bitsets if you realise the rest of the solution. Anyway the solution is ok, but it's pretty easy itself, I think too easy for a problem F.

        → Reply
»
4 days ago, # |
  Vote: I like it -117 Vote: I do not like it

best contest ever,

I liked problem B so much.

Every problem should be like this in every contest.

Thanks, upvote who agrees.

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

    are you serious right now bra

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      He's kidding obviously. B is the shittiest problem ever. Thats the worst nightmare of "hmm, should i use k-1 or k in this 108th case...".

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

        ya man constructive problems are the worst we can expect in a contest

        → Reply
        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But I should say that the solution for B is elegant. IMHO, the editorial doesn't clearify all the details of the solution but once you understand it, you don't feel like this problem is that tricky anymore.

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

            The trickiness of this kind of problems is hugely determined by the strength of the examples, and this one kinda well-hided the edge cases. If the examples were even weaker, I'd say it could be at least as hard as a regular D2C.

            → Reply
          • »
            »
            »
            »
            »
            »
            38 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ya i find it difficult to check all the edge cases during the contest but nice contest i hope it will increase my ability to think more next time

            → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got the answer to Question B of this Wrong Answer three times, but I got all four questions in ACDE AC once. This question I thought was cleverly designed to avoid certain special cases in the sample, which is something to watch out for in reality, and the ICPC tends to test a player's sensitivity to such Cases.

        → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I still think B is cool. But yeah its hard to find the logic behind it.

        → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for fast editorial! orz applepi216

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for a very first tutorial

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I still don't understand why my ceil division didn't work like this:

ans = n - (n - c + b - 1) / b
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    This formula only works when c <= n.

    Try this testcase: 1 3 1 5

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

      I have specific part to handle other cases:

            if (c >= n) {
        ans = n;
      } else if (c == n - 1) {
        ans = n - 1;
      } else {
        ans = n - (n - c + b - 1) / b;
      }
      → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How about b = 0

        → Reply
        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
            while (T-- > 0) {
    int64_t n, b, c;
    cin >> n >> b >> c;
    int64_t ans = -1;
    if (b == 0) {
      if (n == 1) {
        ans = (c == 0 ? 0 : 1);
      } else if (n == 2) {
        ans = min(int64_t{2}, max(int64_t{1}, c));
      } else if (n >= 3) {
        if (c == 0)
          ans = -1;
        else {
          if (c >= n) {
            ans = n;
          } else {
            ans = n - 1;
          }
        }
      }
    } else {
      if (c >= n) {
        ans = n;
      } else if (c == n - 1) {
        ans = n - 1;
      } else {
        ans = n - (n - c + b - 1) / b;
      }
    }

    println("{}", ans);
  }

          Here goes the whole solution

          → Reply
          • »
            »
            »
            »
            »
            »
            4 days ago, # ^ |
            ← Rev. 2   Vote: I like it +1 Vote: I do not like it

            I think the formula is not the reason you got WA, b == 0 && c == 0 is not the only case that answer = -1.

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

            say b is 0, now all the n values will be c, now if n!=c+2 we wont be getting a permutation. if b is non zero we will always get a solution which will be number of number greater than n-1 in our vector.

            → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        you did not take n-2 for consideration

        else if(c==n-1 || c==n-2) { ans=n-1;}

        → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B

1

100000000000000 1 1

test not working when use while, but there are accept solution with while.

→ Reply
»
4 days ago, # |
  Vote: I like it +7 Vote: I do not like it

A. OK. nice. AC

B---lew me away.

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Tree solution to $$$D$$$ :

Lett root of the tree be $$$n$$$, now add the edge between $$$i$$$ and $$$j$$$ such that $$$i$$$ is more valuable than $$$j$$$ in atleast one of the $$$3$$$ permutations and $$$i > j$$$, answer is the decreasing path from $$$n$$$ to $$$1$$$, it's easy to construct solution from the path.

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Wouldn't the number of edges be $$$O(n^2)$$$ in this solution ?

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

      How can tree have $$$n^2$$$ edges, tree have $$$n-1$$$ edges hence we are considering every element only once

      → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    May I ask if you could simply explain the code implementation? I don't quite understand how to create the graph. I wrote about a similar method in the contest, but I didn't complete. :(

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The formula for t(v) doesn't make any sense in problem E, you define d(v) and then wrote d/d+1 .What is that?

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    d should just be d(v).

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      thanks, updated editorial mildly to make it $$$d(v)$$$.

      → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

New lesson learned — use fenwick tree whenever possible to prevent MLE, missed D by 1 second!

→ Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Man, if these kind of problem were being asked in div 2 B, then I might not reach pupil in this life. But I would say problem A was good though. Haven't solved it in contest, but it gave new perspective to solve Brute force type problems

→ Reply
»
4 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Who wrote the problem B? "I just wanna talk to him"

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

    The entire contest was authored by a single author, it's clear from that.

    → Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have found out max 14 iterations can be taken. Edge case:- n=9 a=10 b=1 WWWNSEEEE

    |_,_,_,_ s e

    If we go for 13 iterations then 'e' will be at 13,0 which gives highest point at (9,1). But if we go for 14 iterations then 'e' will be at 14,0 which gives highest point at (10,1).

    Here is my submission

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, why it is not enough to run the pattern for 10 times ?

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider SNNE and $$$(10,9)$$$.

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

      thanks

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

      Why exactly less than 100 is sufficient and not less than 50 or 90 and more than 110 or 150 or 200 ??

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

        i did 20 and got AC

        → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        It is definitely sufficient to repeat the move sequence exactly 100 times.

        First just look at where Alice lands after a full sequence. You can think of that as a translation in 2D space, a vector. Repeating the full sequence will just result in multiplying that vector by an integer. Clearly, it will never take more than 10 applications of an integer vector to reach the target which coordinates are $$$\le 10$$$.

        Now let's think of what happens when Alice performs just the first move. After that, she will more or less start repeating the same sequence again. More precisely, for example if her sequence was SENESW, then her first move was S and will now be repeating the sequence of moves ENESWS (except for her very last move). That new sequence has the same length. So to reach the target after her first move, 10 repetitions of the sequence are enough again.

        The same reasoning can be applied when you think about what if she has done her first two moves, first three moves, etc. But her sequence is only 10 moves long, so in total she will never need more than $$$10 \times 10$$$ moves.

        Not saying it can't be capped at a lower number as others have written, but this was enough to get AC.

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

        consider at each time you repeat a sequence, your position improved 1 distance to the target.

        Mahattan distance from (0,0) to nmax (10, 10) is 20. So worst case it can do is 20 loops.

        But my instinct tell me to do something around 100 (nmax*nmax, and in my sub I do 110 because I'm very lazy to think about edge cases in A/B problem). Kinda doing it with what the guts tell though.

        Later, the problem B hurt me so much I don't have enough time for C. Just barely 5 minute I'll AC problem C but just can't.

        → Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have found out max 14 iterations can be taken. Edge case:- n=9 a=10 b=1 WWWNSEEEE

    |_,_,_,_ s e

    If we go for 13 iterations then 'e' will be at 13,0 which gives highest point at (9,1). But if we go for 14 iterations then 'e' will be at 14,0 which gives highest point at (10,1).

    https://codeforces.me/contest/2028/submission/290973014

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Having spent basically half the contest thinking about E, I am somewhat underwhelmed by the lack of proof of the formula for $$$t(v)$$$. The editorial just drops it on you saying it matches up with the bamboo case (fair enough) but gives no intuition on why it works :(

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hm, I think the main point I'm trying to make is that we can reduce the problem to solving it on paths. In other words, we can somewhat simulate "removing" the edges of the shortest path from root to leaf, which decomposes the tree into a forest. For each root of that forest, we now know the probability of Alice escaping from that root, and so the same inductive logic applies (cut away a shortest root-to-leaf path, repeat). So, the proof for the bamboo case must apply to the whole tree.

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Okay I took some more time to parse the last paragraph and your reply and I see it now, the $$$t(v)$$$ formula in the second paragraph clearly follows from that reasoning, thanks!

      I think a good way convince oneself that the game takes place at one (subtree)root-leaf path at a time is to say that: Alice is trying to advance to the root asap; Bob is trying to get to any leaf asap; the most probable path to any vertex is the shortest one, so it is optimal for Bob to alway target the closest leaf at any given time. (So long as it doesn't involve going upwards, as that move is always optimal for Alice, and we're playing a zero sum game)

      → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked it very much, even though I don't know enough to solve harder problems :D I'll make sure to write them (with help of editorial)

→ Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

For E, one can enumerate leaves from low depth to high depth, and fill the link between the leaf and the first ancestor that is filled with an A. P. Code: 290943603

→ Reply
»
4 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem B: binary search solution:

https://codeforces.me/contest/2028/submission/290960549

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

    Thnx!. Couldn't thought of a o(1) solution. I completely forgot that 128 bit intengers exist

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand what is wrong with my code for B?https://codeforces.me/contest/2028/submission/290960656

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
       else {
        if (b==0) {
            if (c<=n-1) cout<<n-1<<nl;
            else cout<<n<<nl;
        } else {
            float k = (float)(n-1-c)/(float)b;
            if (k < 0) cout<<n<<nl;
            else cout<<(n-1-(int)k)<<nl;
        }
    }

    in your if statement where b==0 there are 3 cases

    if(c>=n) ans=n;
else if(c>=(n-2)) ans=n-1;
else ans=-1;
    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

From problem C, I found one segment from the start and one segment from the end, use whichever is smaller. max(the remaining part, maximum of the m parts if the sum of the remaining part is over v) is for alice. Why is this approach incorrect?

And what is the 222nd test case for pretest case 2?

→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    10 4 1 4 4 4 4 4 4 1 1 1 10

    → Reply
  • »
    »
    4 days ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Initially, I tried that as well but it doesn't work. Try these cases:

    n = 9 m = 4 v = 10: 13 1 12 9 1 11 8 3 1

    n = 9 m = 4 v = 10: 13 1 12 9 1 13 8 3 1

    They should both be 14.

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

      Thank you! But what are n, m, v then?

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

        edited

        → Reply
      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        basically it seems like with this approach you can't know which side to take from unless you check the entire middle (which takes O(n) time per creature), so O(mn) time overall.

        → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have proof for A?

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

    I don't have the proof for the tight bound, but it's easy to see that repeating it large enough times is sufficient.

    Consider a case when you completed the move sequence once, and now you're at $$$(x,y)$$$. If $$$x=0$$$ and $$$y=0$$$, repeating the same sequence will never let you get anywhere new. Otherwise, each time you perform the move sequence, your position will change by $$$(x,y)$$$ again, which will eventually "surpass" $$$(a,b)$$$, either in positive or negative direction. Since each sequence has limited number of moves, you can't reach more than the length of the sequence away from your current position within a single move sequence. Therefore, after enough iterations, $$$(x,y)$$$ will become far from $$$(a,b)$$$ that you cannot reach there within another move sequence, and the distance will become even greater after each move sequence.

    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let r be the max(x, y) after doing the pattern once. if r = 0, 1 simulation is enough else after 20 simulations we have to start from a point that is a least 20 away from the beginning and cannot reach a coordinate in the square 10,10 since the pattern is 10 long.

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

    I've added a proof to the editorial.

    → Reply
»
4 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I spent almost 2 hours to debug problem B with no success, with every solution "Wrong Answer on test 2". When the contest was over, I checked the verdict and realized the verdict's comment: Wrong answer 6077th number differs. Please can anyone tell me what's wrong with my code, thanks for your time. After I read the editorial, I still didn't understand why my solution is wrong.

This is my code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        ll n, b, c;
        cin >> n >> b >> c;
        if(b == 0){
            if(c == 0){
                if(n == 1){
                    cout << 0 << endl;
                }
                else if(n == 2){
                    cout << 1 << endl;
                }
                else{
                    cout << -1 << endl;
                }
            }
            else{
                if(n == 1){
                    cout << 1 << endl;
                }
                else{
                    if(n - c > 2){
                    	cout << -1 << endl;
                    } else{
                    	cout << n - 1 << endl;
                    }
                }
            }
        }
        else{
            if(n - 1 < c){
            	cout << n << endl;
            } else{
            	if(n - 1 == c){
            		cout << n - 1 << endl;
            	} else{
            		ll temp = (n - 1 - c) / b;
            		cout << n - 1 - temp << endl;
            	}
            }
        }
    }
}
→ Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    consider 4 0 7

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Edited: Realized the whole point where I'm wrong and I've gotten AC. Thank you so much for your help. I am missing if c >= n when b = 0 (should print "n" instead of "n — 1"). Please ignore my comment :)

      Oh wow thanks, I realized the problem. With this below code, it seems to run out properly (4 0 7) outputted 4, but I still get Wrong answer 6077th number differs. Can you come up with another test case that could work? Thanks so much! I've never gotten desperate to a Div2 B problem like today :(

      #include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        ll n, b, c;
        cin >> n >> b >> c;
        if(b == 0){
            if(c == 0){
                if(n == 1){
                    cout << 0 << endl;
                }
                else if(n == 2){
                    cout << 1 << endl;
                }
                else{
                    cout << -1 << endl;
                }
            }
            else{
                if(n == 1)
                {
                    cout << 1 << endl;
                }
                else{
                    if(c > (n - 1)){
                        cout << n << endl;
                    }
                    else{
                        cout << (n - 1) << endl;
                    }
                }
            }
        }
        else{
            if(c > (n - 1)){
                cout << n << endl;
            }
            else{
                ll temp = (n - 1 - c) / b;
                if(temp < 0)
                    temp = 0;
                else if(temp + 1 > n)
                    temp = n;
                ll m = temp + 1;
                if(m > n)
                    m = n;
                ll k = n - m;
                cout << k << endl;
            }
        }
    }
}
      → Reply
  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This part (inside handling b==0):

    if(n - c > 2){
    cout << -1 << endl;
} else{
    cout << n - 1 << endl;
}

    is wrong when $$$c\geq n$$$ (the answer should be $$$n$$$ in that case).

    → Reply
    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Wow thank you so much that solved the problem. Have a nice day!

      → Reply
»
4 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone tell why my approach fails 290961099 ? can we solve it by binary search ?

problem c.

→ Reply
»
4 days ago, # |
  Vote: I like it +3 Vote: I do not like it

best C ever

→ Reply
»
4 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Does anyone know the tight bound of the number of repeats for A, and how to make the worst case?

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Here are the two worst cases, taking 14 repeats:

    9 10 1
WWWNSEEEE

    and

    9 1 10
SSSEWNNNN

    (which is in a sense symmetric)

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with problem D .I am just not able to find the error. My code is failing on input 230 of tc 3. ;)

https://codeforces.me/contest/2028/submission/290954199

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I was writing O(n) solution for A but it's too much case work for checking this

start.x + gap.x * k(iteration ) = x start.y + gap.y *k(iteration) = y

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also wrote an AC O(N) solution, but true, it was too much of a case work :(

    → Reply
»
3 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I would like to share my key-learnings from today's contest in this blog post. Since I have negative contributions, My post is not visible due to Negative contributions.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually your post is visible, or at least I can see it

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain below expression: 1 + (n — c — 1) / b

Instead of this why can't we take 1 + (n-c)/b?

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that is because we need to fill 0~n-1 not 1~n

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/2028/submission/290975793

Does anyone have simpler O(n) solution of A than this .

It's simply two much case work.

→ Reply
»
3 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Bonus for D would be using segment tree right? Instead of maintaining the minimum $$$x$$$ as mentioned in editorial, we'll have to maintain 3 arrays which will store the DP values according to the order of $$$p_i$$$ for each player. Then when we want to find answer for $$$a$$$, we'll do an RMQ to find the $$$b$$$ with minimum $$$dp_b$$$ with $$$p_b<p_a$$$ across all 3. After this we will update the DP value for $$$p_a$$$ using point update.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think, you just have to maintain the distance. No need to segment tree.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My intended solution for this version is indeed a segtree -- can you elaborate by what you mean for "maintain the distance"?

      → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Hi applepi216, before I explain my thought process, I would like to confirm what I am thinking is right or not.

        https://codeforces.me/contest/2028/submission/290968924

        Can you please run/test output of your code, with segment tree, and see, if number of required trades are equal.

        If they are equal, then I will try to elaborate my idea.

        → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think it can be done without segtree too,

        I want to sort the cards by the permutation. for example

        the permutation, 2 3 1 4

        pair with index (2,1), (3,2), (1,3), (4,4)

        Then sort (1,3), (2,1), (3,2), (4,4)

        Then I can Dijkstra over this representation. Every node can reach any other node to its left. So every time I pop a node from the priority queue, I check every unexplored node to its left.

        If the card number is larger, I add it it to the priority queue, if the card number is smaller, I can safely ignore(within king, queen, jack), since it does not explore any extra nodes than the current, so I don't have to add it later even if it is reachable.

        Using a monotonic increasing pointer to keep track of the last unchecked edge, I can check each edge at most once.

        → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission of A: flex is only O(n) The movement have permutation nature, i mean "NE" is equal to "EN". so if the sequence is "NESWSWNSWES", and the the way to reach the queen is NESWSWNSWES + NESW, it's equal to NESW + NESWSWNSWES. i call (i,j) is the result of NESWSWNSWES, so the road should be (i,j)*x times+ subset of NESWSWNSWES. so we just start from this subset result, and try to determine whether it can reach the queen. notice negative road (instead of +(i,j), it will — (i,j) ) My English s*ck

290935227

→ Reply
»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem D:

In the second example, why can’t Alice trade with the Queen to get card 3, and then trade with the Jack to get card 4?

The queen values 1 over 3, so Alice can trade 1 for 3. The jack values 3 over 4, so Alice can trade 3 for 4.

Clearly, I’m missing something obvious but can’t see it after re-reading the problem.

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Had you found out why? I am also unable to understand this case. And I tried the code given in the tutorial, which is also confusing: input: 1 4 3 1 2 4 1 2 3 4 1 4 3 2

    output: YES 2 q 2 j 4

    → Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    You probably misunderstood the meaning of preference values. The Jack values 4 over 3 because $$$p_4 > p_3$$$ ($$$3 > 2$$$).

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For C: We can maintain a count and keep accumulate the sum from the right side, whenever our sum is >=v, we store this index as check[count] = i, count++, since this index is enough to feed count number of people.

Now we iterate from left side, whenever we feed c people, we find j=check[m-c] index which is the farthest index from i such that m-c people can be feed. so for each such i, ans = max(ans, sum a[i+1,j-1]). Finally, ans variable stores the largest segment which Alice can have.

Submission : 290978919 runs in O(n) with just 2 iterations in 77ms.

Do let me know if you have something to ask about this.

→ Reply
»
3 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain, what system of linear equations is mentioned in problem E editorial? Or just explain in other way, why $$$1 − \frac{(i−1)}{d}$$$ is a solution for a bamboo.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Suppose we have a bamboo on nodes $$$0, 1, \ldots, d$$$. Let $$$p_i$$$ be the probability of Alice escaping from node $$$i$$$ (let $$$0$$$ be the root, so $$$p_0 = 1$$$ and $$$p_d = 0$$$). Then, $$$p_i = \frac 12 p_{i+1} + \frac 12 p_{i-1}$$$ for all $$$1\le i \le d - 1$$$.

    From this system of equations, you can prove by substitution & induction or other means (for example, martingales or some discrete harmonic function facts) that $$$p_i = 1 - \frac id$$$. In fact, if you guess that this is the solution it is not too hard to verify that it works by plugging it in.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does pd equals zero?

      → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        By definition, Alice loses if she reaches any leaf (here I'm just shifting so that $$$0$$$ is the root and $$$d$$$ is the leaf)

        → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i figured this out but i would love if you dropped a little proof

      → Reply
      • »
        »
        »
        »
        33 hours ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        p(i) = (p(i+1) + p(i-1))/2

        p(i) − p(i-1) = p(i+1) − p(i)

        It is easy to see that the change in probability between the adjacent nodes on the branch being referred to by applepi216 will become a constant from the leaf upto parent of the ith node

        → Reply
    • »
      »
      »
      33 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You can simply see that p(i) − p(i-1) = p(i+1) − p(i) holds from the above equation, with p(d) = 0 and p(0) = 1

      It is easy to see that the change in probability of these adjacent nodes is constant, from which you can get that going from p(d) to p(0), p(i) = 1 − i/d

      → Reply
»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there a way to see or download the full testcases? I do not understand why my answer is wrong.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote a BFS solution for D which got accepted. But I now realize after reading the editorial that the solution is incorrect.

In fact, it fails on this particular test case:

1
6
1 2 4 5 3 6
3 2 5 1 6 4
1 2 3 4 5 6

The solution is YES but my code prints NO. Any div 1 user, please feel free to uphack :)

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I realize why I got WA now. Thanks a lot.

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey!!

applepi216 in bonus of problem D Bonus can we claim that if answer exist than minimum length of it would be either 1,2,3(number of trade)? I can't really put argument since i couldn't come up with any proof.

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try this

    1
8
1 3 2 5 4 7 6 8
2 1 4 3 6 5 8 7
1 2 3 4 5 6 7 8

    I think the minimum steps is 7.

    Queen only trades 2->3, 4->5, 6->7

    King only trades 1->2, 3->4, 5->6

    Jack does not trade at all.

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B,I found that c+(b-1)*((n-c-1)/b)+(n-c-1)%b can also be used instead of n-max(0ll,1+(n-c-1)/b) by math,can anybody prove it that they are actually the same?

→ Reply
»
3 days ago, # |
  Vote: I like it +5 Vote: I do not like it

What felt natural to me in E: //1. write the equations and observe each node depends on its parent and node leading to the nearest leaf. //2. to determine the order in which values have to be found draw the directed graph and decompose into SCCs, then //topsort, in that order. pretty common stuff. //3. for each SCC, observe it is a path from v to some ancestor. p(i)=1/2(p(i-1)+p(i+1)) roots of its char eqn is 1,1 //so p(i)=a+bi if outgoing edge of v leads to a node with prob x and similarly ancestor leads to y then, //a=x and b=(y-x)/(sz(SCC)+1). //okay, a pretty obvious thing was that witch will pull it down, even if nearest leaf can be obtained by going up.

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please, say me what equations we need to write

    → Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In testcase case no. 2 of problem c answer would be 20 instead of 12 because she can divide the cake into (1+1),(1+1) and remaining would be (10+10)=20

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Subarrays mean that they have to be contiguous, so you can't give both $$$[10]$$$ and $$$[10]$$$ to Alice.

    → Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Ive never felt more satisfaction getting AC on a D2B

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

D is a cute problem. Thanks.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I use Pypy in problem A with an almost same code, but it's time exceeded.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

is binary search possible on problem b , given constraints are very large

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It worked for me. As I wasn't able to deduce the direct formula used for the else part in the suggested editorial solution for case when $$$b != 0$$$, I had realized using Binary Search for the problem B.

    If it works in PyPy3 (Python implementation of Python 3), it should work on most of the languages. Check out my Binary Search inclusive solution to Problem B here: https://codeforces.me/contest/2028/submission/290951271

    → Reply
»
3 days ago, # |
  Vote: I like it -21 Vote: I do not like it

I still dont get problem E, isnt it possible that alice will move back and forth indefinitely if the coin keeps alternating between heads and tails?

→ Reply
  • »
    »
    3 days ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    As the number of flips goes to infinity, the probability that Alice still hasn't reached the root or a leaf goes to zero, meaning that Alice will almost surely end up either at the root or a leaf with infinite amount of tries.

    → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    To see why this isn't the case in another way, consider the event that the coin flips heads $$$n$$$ times in a row (we will keep flipping the coin even after Alice either escapes or gets trapped). Certainly, if it's heads $$$n$$$ times in a row then the process stops. But, this event happens with probability $$$1$$$ (in other words, as djm03178 put it, it will almost surely occur) so we can "condition" on this event. Thus, eventually someone will win with probability 1.

    → Reply
»
3 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For anyone that doesn't understand the last paragraph of E, including me here is a slightly better explanation. Let the node we want to escape from be v, the parent is p, the chance of escape from the parent is p(v) and distance to closest leaf node is d we can say that until we reach the parent v, the game will only be played on the bamboo going from p, into v, and to the closest leaf. Thus the chance of getting to the parent p is the chance of getting from the node second from the top to the top in a bamboo. This turns out to be d/(d+1)(or to say it out loud, # of nodes below this one over the total number of nodes not including this one) which just comes from the bamboo equations. So we can derive that the overall chance is p(v)*d/(d+1).

→ Reply
»
3 days ago, # |
← Rev. 5   Vote: I like it +14 Vote: I do not like it 
Problem E,
My Solution (In detail)

Let i be the node on which alice is currently. 

The optimal moves will be
=> Alice will always try going to the parent of the current node
=> Other person will always pull Alice to a child node of the current node via which some leaf node is closest.

Let, dp[i] be the probability of alice escaping, ch[i] be the optimal child node of i for the second person and p[i] be the parent node of i.

dp[i] = (1 / 2) * dp[p[i]] + (1 / 2) * dp[ch[i]]  -> (1)
dp[1] = 1 (Alice can always escape)

For All leafs
dp[leaf] = 0 (Alice can never escape)

Let,
i -> ch[0] (ch[0] is nothing but ch[i] in equation 1)
ch[0] -> ch[1]
ch[1] -> ch[2]
ch[x-1] -> ch[x] (ch[x] is a leaf)
be the optimal child nodes for the other player.

Now, 
dp[ch[0]] = dp[i] * (1/2) + dp[ch[1]] * (1/2)
dp[ch[1]] = dp[ch[0]] * (1/2) + dp[ch[2]] * (1/2)
--------
dp[ch[x-1]] = dp[ch[x-2]] * (1/2) + dp[ch[x]] * (1/2)
dp[ch[x]] = 0

Simplify dp[ch[x-1]] , dp[ch[x-2]] , dp[ch[x-3]].

dp[ch[x-1]] = dp[ch[x-2]] * (1/2)

dp[ch[x-2]] = dp[ch[x-3]] * (1/2) + dp[ch[x-1]] * (1/2)
dp[ch[x-2]] = dp[ch[x-3]] * (1/2) + dp[ch[x-2]] * (1/4)
dp[ch[x-2]] * (1 - (1/4)) = dp[ch[x-3]] * (1/2)
dp[ch[x-2]] = dp[ch[x-3]] * (2/3)

dp[ch[x-3]] = dp[ch[x-4]] * (1/2) + dp[ch[x-2]] * (1/2)
dp[ch[x-3]] = dp[ch[x-4]] * (1/2) + dp[ch[x-3]] * (1/3)
dp[ch[x-3]] * (1 - (1/3)) = dp[ch[x-4]] * (1/2)
dp[ch[x-3]] = dp[ch[x-4]] * (3/4)

By mathematical Induction we can say
dp[ch[0]] = dp[i] * (x / (x + 1)) -> (2)

Now,
Let d[i] be the minimum depth from node i to any leaf in the subtree of i
Then,
dp[ch[i]] = ((d[i] - 1) / d[i]) * dp[i] (From equation 2)

Substitute this in equation (1)
dp[i] = dp[p[i]] * (1 / 2) + dp[i] * ((d[i] - 1) / d[i]) * (1 / 2)
dp[i] * (2 - ((d[i] - 1) / d[i])) = dp[p[i]]
dp[i] * ((d[i] + 1) / d[i]) = dp[p[i]]

dp[i] = dp[p[i]] * (d[i] / (d[i] + 1))

So,
dp[1] = 1
dp[leaf] = 0 (all leafs)
dp[i] = dp[p[i]] * (d[i] / (d[i] + 1)) (For all other nodes appart from 1 and leafs)

Precompute d[i] for every node and compute dp[i] with above transitions :) .
→ Reply
»
2 days ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Editorial's hint for D :

This is not a graph problem.

Tags 😁 :

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain me A in a simpler way? I am not getting it.

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i didn't read the editorial but just simulate once, check to see if you reach. If not, you know the total delta distance per cycle so run it a few times and have a set to check to see if you brought a and b in range, refer to my submission.

    → Reply
  • »
    »
    44 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After the first run of the movement pattern, Alice will either move towards -x, +x, -y, +y, or remain at the same position. This depends on which direction has the highest count among N, E, S, and W. If all directions (N, E, S, and W) have the same count, she will remain at the same position.

    In the worst case, you could have a pattern like NNNNNNSSSS. In this case, Alice will move down by up to 4 levels and then move back up. After 10 iterations, Alice will reach a position that is 10 units away, but since there are four additional S moves, she will come down again, within a 10x10 grid. After 4 more iterations, Alice will reach the border of a 14x14 grid. If the pattern continues, the farthest she can reach is the edge of a 10x10 grid.

    Thus, in the worst case, you need 15 loops to be safe:

    10 iterations to reach the 10x10 grid border.
5 more iterations to ensure Alice does not re-enter the 10x10 grid while following the movement pattern.
    → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The problen D is pretty good.It made me realize my shortage in dp.Though,i failed to solve it in time,it actually made me stronger.

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is it not possible to multi-source bfs from all the non-root leaves to all the other edges to find the shortest path to the next non-root leaf? I tried this and it failed

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C is really a nice question ,i missed on really simple observation that what can be the maximum piece from i Alice can take and tried to binary search on segments or binary search on answer.

→ Reply
»
46 hours ago, # |
  Vote: I like it +21 Vote: I do not like it

In Problem E, the derivation of the formula $$$t[i] = 1 - \frac{i - 1}{d}$$$:

We have the base cases $$$t[1] = 1$$$ and $$$t[d+1] = 0$$$.

As there are two moves with equal probability (moving $$$i - 1$$$ or moving $$$i + 1$$$) for all other $$$i$$$, the equation $$$t[i] = \frac{t[i - 1]}{2} + \frac{t[i + 1]}{2}$$$ holds.

We can rewrite the equation as $$$t[i] = \frac{t[i - 1] + t[i + 1]}{2}$$$. So we need to find a sequence of length $$$d+1$$$ whose first term is equal to $$$1$$$ and the last term is $$$0$$$ and the other terms must be arithmetic mean of the two neighbouring terms. Does that remind you of something?

Yes, it does. All the conditions hold, if and only if the sequence is arithmetic. Let's change the question: You are given first and the last terms of an arithmetic sequence of length $$$d + 1$$$, and asked to find the sequence itself. You can find the difference, $$$dif$$$, between two consecutive terms by the formula $$$dif = \frac{term_{d+1} - term_1}{d}$$$. Just substitute last term with $$$0$$$ and first term with $$$1$$$, then you will get $$$dif = \frac{-1}{d}$$$. Then, the formula for the $$$i_{th}$$$ term will be $$$t[i] = t[1] + (i - 1) \times dif$$$. Again, substitute everything to get the final formula:

$$$t[i] = 1 + (i - 1) \times (\frac{-1}{d})$$$ $$$\rightarrow$$$ $$$t[i] = 1 - \frac{i - 1}{d}$$$.

The problem just requires some thinking and knowledge from 4th grader. Amazing.

Thank you, applepi216, for such an interesting problem.

→ Reply
»
46 hours ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

I think that my two pointers solution for problem C is simple and elegant.

Solution
→ Reply
»
44 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

In B , even binary search gives TLE. According to the tutorial, it can be done in O(1) , but BS should also not give TLE. I think

// this is code

#include<bits/stdc++.h>
using namespace std;

void solve(){
    long long n,b,c;
    cin>>n>>b>>c;
    long long l = 0;
    long long r = n-1;
    long long m = (l+r)/2;
    
    // if(b==0 && c== 0){ cout<<n-1<<endl;  return;}
    if( b== 1 && c==0){ cout<<0<<endl;  return;}
    if(b==0 && c < n-2){ cout<<-1<<endl;  return;}
    if(b==0 && c < n){ cout<<n-1<<endl;  return;}
    if(b==0 && c >= n){ cout<<n<<endl; return;} 
    long long ans = -1;
    while(l <= r){
        // long long val = ;
        if( (double)b < ((double)n-c)/m){
            ans = m;
            l = m+1;
        }
        else{
            r = m-1;
        }
        m = (l+r)/2;
    }

    cout<<n-ans-1<<endl;
    return;

}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please explain why this fails in C? I used a 2 pointer based greedy,where i create segment from start(sum>=v): say from 0 to i and same segment from the back(say from j to n-1), now I choose the segment with the lower sum(but still >=v), and decrease count and move pointers accordingly.

→ Reply
»
38 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

PROBLEM E: Why optimal move of the Queen is downward? Considering the following case:

9
1 2
2 3
3 4
3 5
5 6
6 7
7 8
8 9

What if Alice starts at 5 and Queen intends to move 5 -> 3 -> 4. Will the probability be greater or lesser than the moving downward way?

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Think about it this way: the Queen has more winning possibilities by moving downward than moving upward. In other words, the probability of Alice losing increases as we go down the tree (since it must decrease as we go up the tree).

    → Reply
»
37 hours ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Another direct proof for $$$t[i] = 1 - (i - 1) d^{-1}$$$ in the Problem E. The comment proves that the following equation

$$$ t[i] = 2^{-1} (t[i - 1] + t[i + 1]), \tag{1} $$$

with the boundary conditions

$$$ t[1] = 1,\quad t[d+1] = 0, \tag{2} $$$

holds.

Further, various authors suggest noticing something to solve Eq. (1). However, there is no need to notice anything. We need only to apply the standard technique. Denote $$$ j = i + 1 $$$, then we have

$$$ t[j - 1] = 2^{-1} (t[j - 2] + t[j]), $$$

which is equivalent to

$$$ t[j] - 2 t[j - 1] + t[j - 2] = 0, \tag{3} $$$

To solve Eq. (3) we construct the characteristic polynomial:

$$$ \lambda^2 - 2 \lambda + 1 = 0. $$$

Hence $$$\lambda=1$$$ (it is the root of multiplicity 2). So

$$$ t[j] = C_1 1^j + C_2 j 1^j = C_1 + C_2 j, \tag{4} $$$

where $$$C_1$$$ and $$$C_1$$$ are constants, which can be founded from the boundary conditions. Let us substitute (4) into (2) and obtain

$$$ t[1] = C_1 + C_2 = 1,\quad t[d+1] = C_1 + C_2 (d+1) = 0. \tag{5} $$$

The solution of the system (5) has the form: $$$C_1 = \dfrac{d+1}{d} = 1 + \dfrac{1}{d}$$$ and $$$C_2 = -\dfrac{1}{d}$$$ (it is so obvious that I don't see the point in describing it in detail). Thus,

$$$ t[i] = C_1 + C_2 i = 1 + \dfrac{1}{d} - \dfrac{i}{d} = 1 + \dfrac{1 - i}{d}. $$$

The statement is proved.

→ Reply
»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Im trying to use 2 pointers here by calculating the minimum sum subarray such that sum >= v by traversing from start as well as the end. If the sum from left was smaller and lets say now left pointer is at L than in next iteration pointer from right end lets say R should end at L, ip and jp are current left and right ends.

#include <bits/stdc++.h>
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n, m, v;
        cin >> n >> m >> v;
        vector<int> a(n);
        long long S = 0, SS = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            S += a[i];
        }
        int L = 0, R = 0;
        int i = 0, j = n - 1;
        int ip = 0, jp = n - 1;
        while (i <= j && m > 0) {
            if (i == j) {
                if (a[i] >= v) {
                    SS += a[i];
                    m--;
                }
                break;
            }
            while (i <= jp && L < v) {
                L += a[i];
                i++;
            }
            while (j >= ip && R < v) {
                R += a[j];
                j--;
            }
            if (L >= v && R >= v) {
                if (L < R) {
                    SS += L;
                    L = 0, R = 0;
                    j = jp;
                    ip = i;
                } else {
                    SS += R;
                    L = 0, R = 0;
                    i = ip;
                    jp = j;
                }
            } else if (L >= v) {
                SS += L;
                j = jp;
                ip = i;
            } else if (R >= v) {
                SS += R;
                i = ip;
                jp = j;
            } else {
                m = 1;
                break;
            }
            L = 0, R = 0;
            m--;
        }
        cout << (m != 0 ? -1 : S - SS) << '\n';
    }
    return 0;
}
→ Reply
»
16 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I found an interesting way to solve E by constructing a different system of linear equations and solving it using a variation of Tridiagonal Matrix Algorithm: https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm.

Let $$$p_v$$$ be the answer for vertex $$$v$$$, $$$p(v)$$$ be the parent of $$$v$$$ and $$$s^*(v)$$$ be the child of $$$v$$$ which lies on the shortest path from $$$v$$$ to leaf in subtree of $$$v$$$. Then we have:

$$$p_v = \begin{cases} 1, & \text{if $$$v$$$ is a root,} \\ 0, & \text{if $$$v$$$ is a leaf,} \\ \frac{1}{2}\left(p_{p(v)} + p_{s^*(v)}\right), & \text{if $$$v$$$ is neither a root nor leaf.} \end{cases} $$$

This system is quite difficult to solve in a straightforward way by Gaussian elimination since it requires $$$O(n^3)$$$ time in general, but we can use the approach similar to Tridiagonal Matrix Algorithm in $$$O(n)$$$ time. We express $$$p_{p(v)}$$$ as $$$\alpha_v p_v + \beta_v$$$, substitute this in an equation for $$$p_v$$$ and find coefficients $$$\alpha_{s^*(v)}$$$ and $$$\beta_{s^*(v)}$$$ in terms of $$$\alpha_v$$$ and $$$\beta_v$$$, solve for $$$p_{s^*(v)}$$$ recursively and then solve for $$$p_v$$$.

Then we can implement DFS-like solver which starts from $$$v = 1$$$ with $$$\alpha_1 = 0$$$ and $$$\beta_1 = 1$$$ (since $$$p_1 = 1$$$), propagates $$$\alpha_v$$$ and $$$\beta_v$$$ into $$$s^*(v)$$$, then solves for $$$p_v$$$ and goes into another children. The only problem left is the proper way to "go into another children". Since we've already found $$$p_{p(v)}$$$, from the expression for $$$p_v$$$ we conclude that it's enough to pass $$$\alpha = \frac{1}{2}$$$ and $$$\beta = \frac{1}{2}p_{p(v)}$$$ into DFS call for every child.

→ Reply
»
15 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How to be able to solve problems like E, I feel that however i spend time i can never solve it.

→ Reply