the_nightmare's blog

Codeforces Round #721 — EDITORIAL
By the_nightmare, history, 4 years ago, In English

1527A - And Then There Were K

Author: loud_mouth
Idea: Bignubie

Editorial
Solution (Loud_mouth)
Solution (the_nightmare)

1527B1 - Palindrome Game (easy version)

Author: DenOMINATOR
Idea: shikhar7s

Editorial
Solution (DenOMINATOR)
Solution (shikhar7s)

1527B2 - Palindrome Game (hard version)

Author: DenOMINATOR
Idea:DenOMINATOR

Editorial
Solution(Greedy) (DenOMINATOR)
Solution(DP) (DenOMINATOR)

1527C - Sequence Pair Weight

Author: sharabhagrawal25
Idea: rivalq

Editorial
Solution (sharabhagrawal25)
Solution (mallick630)

1527D - MEX Tree

Author: mallick630
Idea: CoderAnshu

Editorial
Solution (shikhar7s)
Solution (the_nightmare)

1527E - Partition Game

Author: rivalq
Idea: rivalq

Editorial
Solution (rivalq)
Solution (the_nightmare)
  • Vote: I like it
  • +166
  • Vote: I do not like it

Comments Comments (84)
| Write comment?
»
4 years ago, # |
  Vote: I like it +118 Vote: I do not like it

contest was the_nightmare

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

nightmare round

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

How to solve E using divide and conquer DP? (and especially how to maintain the cost around?)

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

    link here is my code for divide and conquer technique

    i took the idea from the code given below and understood it link

    basically what we are doing here is we are maintaining a persistent segment tree on every ith index which will provide us with the information that if we consider a segment of [i,j] then what will be its cost. The basic idea here is to use segment tree with range updates and point query.You could see from my code how to update ranges its pretty straightforward.

    now that we can find out the cost of any segment in log(n)complexity all we have to do is calculate the dp which can be calculated with the help of divide and conquer the only hard part of this method was the persistent segment tree part which was difficult to understand and actually think by yourself(atleast for me it was very new idea)

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

In problem B1, when all the elements of the string is 1, then how Bob wins?

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

    It is given in the input section that string $$$s$$$ contains at least one $$$0$$$

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

      But for this, why Draw is not the correct answer?

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

        Yes, technically it should be DRAW but to avoid confusion we omitted that case

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

          i have implemented dp for B2, but it's giving me incorrect output, pls help me find the bug

          const int N = 1e3;

ll dp[N/2 + 1][N/2 + 1][2][2];

void solve() {
    int n;
    cin >> n;
    string s; 
    cin >> s;
    int cnt00 {}, cnt01 {}, mid {}, rev {};
    for(int i = 0; i < n - 1 - i; i++) {
        if (s[i] == s[n - 1 - i] && s[i] == '0') {
            cnt00++;
        }
        if (s[i] != s[n - 1 - i]) {
            cnt01++;
        }
    }
    if (n % 2 && s[n/2] == '0') {
        mid = 1;
    }
    if (dp[cnt01][cnt00][mid][rev] < 0) {
        cout << "ALICE" << '\n';
    }
    else if (dp[cnt01][cnt00][mid][rev] > 0) {
        cout << "BOB" << '\n';
    }
    else {
        cout << "DRAW" << '\n';
    }

}


int main() {
    fastio();
    for(int i = 0; i <= N/2; i++) {
        for(int j = 0; j <= N/2; j++) {
            for(int mid = 0; mid < 2; mid++) {
                for(int rev = 0; rev < 2; rev++) {
                    dp[i][j][mid][rev] = INF;
                }
            }
        }
    }
    dp[0][0][0][0] = 0;
    for(int i = 0; i <= N/2; i++) {
        for(int j = 0; j <= N/2; j++) {
            for(int mid = 0; mid < 2; mid++) {
                for(int rev = 0; rev < 2; rev++) {
                    // i -> cnt of symmetric 01 pairs
                    // j -> cnt of symmetric 00 pairs
                    if (i > 0) {
                            dp[i][j][mid][rev] = min(dp[i][j][mid][rev], 1-dp[i-1][j][mid][0]);
                    }
                    if (j > 0) {
                            dp[i][j][mid][rev] = min(dp[i][j][mid][rev], 1-dp[i+1][j-1][mid][0]);
                    }
                    if (mid > 0) {
                            dp[i][j][mid][rev] = min(dp[i][j][mid][rev], 1-dp[i][j][0][0]);
                    }
                    if (rev == 0 && i > 0) {
                            dp[i][j][mid][rev] = min(dp[i][j][mid][rev], -dp[i][j][mid][1]);
                    }
                }
            }
        }
    }
    int tc = 1;
    cin >> tc;
    while(tc--) {
        solve();
    }
}
          → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      in case of 1100 why bob will win??

      Alice can reverse

      then bob has to do 1011

      again Alice can reverse

      and bob again has to do 1111

      so Alice will win..

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

        but initially it is pallin so alice can't reverse it!

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

          1100 is pallin??

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

            no, 1100 is not pallin so u can's reverse it at the first place alice had to put 1

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

orz

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

Does someone know of any problem similar to C?

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

what is the time complexity in B2 dp approach. 1.is it O(n^2) for one test case as it depends on no of 00 pairs and no of 01 pairs? 2.also if n^2 per test case how it passes the judge in 1 sec as n^2*t=1e9 ?

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

Alternative solution to A:

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

    I think this will TLE in python

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

    Yes, you can do that too, but it would take too much time and result in TLE

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

      The complexity is logn for this so it won't TLE. At each iteration, you're setting at least 1 set bit to 0.

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

    Hey! I am not able to understand why I am getting TLE for this solution :(

    Solution

    This is my submission : 116759121

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
MY ISSUE PLEASE HELP ( PROBLM B1) !!

UPD: Understood!!How to solve this. Thanks everyone

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

    Actually, for example $$$000000$$$ game goes-

    $$$A$$$ pay $$$1$$$ $$$100000$$$

    $$$B$$$ pay $$$1$$$ $$$100001$$$

    $$$A$$$ pay $$$1$$$ $$$100101$$$

    $$$B$$$ pay $$$1$$$ $$$101101$$$

    $$$A$$$ pay $$$1$$$ $$$111101$$$

    $$$B$$$ reverse $$$101111$$$

    $$$A$$$ pay $$$1$$$ $$$111111$$$

    $$$B$$$ wins

    Now, analyse $$$010101010$$$

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

    example 0 0 0 0 0 0

    A pay1 1 0 0 0 0 0

    B pay1 1 0 0 0 0 1

    A pay1 1 1 0 0 0 1

    B pay1 1 1 0 0 1 1

    A pay1 1 1 1 0 1 1

    B reverse 1 1 0 1 1 1

    A pay1 1 1 1 1 1 1

    This is the optimal strategy discussed in the editorial. In each step except the last one, try to make the string palindrome again and in the last reverse the string. Yours is the same strategy I used during the contest but guess I needed to think more.

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

After spending about 20-25 minutes I understood the logic of problem C ( yes I'm still a noob), but I was wondering how does one come up with that logic during contests ( I know practice, practice practice) but I suck at dp and I've been trying to improve it, so if anyone has dp sheets that can build my foundation it'll be of great help thanks :), I've been doing classic dp problems like knapsack, longest common subsequence type questions and even started with matrix chain multiplication recently.

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

    The states are easier to come up during contests if you really try to, most probably you just take what the problem asks and derive subtasks as a prefix, eg: Kadane-ish (or multiple prefixes across multiple sequences, eg: LCS), suffix, subarray of the original sequence, eg: matrix chain multiplication. I'm sure after a lot of $$$practice$$$, things would become somewhat more intuitive and reflexive.

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

Alternative solution to E:

First steps are also coming up with the $$$dp$$$ and writing the brute-force transition formula. Then, by considering $$$last(a_{r + 1})$$$, we can prove the following property:

  • $$$c(l - 1, r) + c(l, r + 1) \leq c(l - 1, r + 1) + c(l, r)$$$

Therefore, $$$c$$$ satisfies Quadrilateral Inequality, where a divide-and-conquer solution works in $$$O(nk\log n)$$$ time.

Note that calculating $$$c$$$ needs a two pointers trick similar to 868F - Yet Another Minimization Problem.

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

    I am using divide and conquer dp optimization for problem E. can you help me why i am getting TLE code

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

      for(int k = mid; k >= optl; k--) {

      $$$k$$$ should be enumerated from $$$optr$$$ to $$$optl$$$, not $$$mid$$$ to $$$optl$$$. Otherwise, the parameter optr is unused.

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

    How to prove complexity of two pointers trick?

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

Anyone please, help me to understand..

For problem B1 help me to figure out the answer for this test case 00100

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

    ALICE — 10100 BOB — 10101 ALICE- 10111 BOB — 11101 (REVERSE) ALICE — 11111

    ALICE --> 3 BOB -->1 BOB WINS

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

      Why it is not possible?

      ALICE — 10100 BOB — 00101(REVERSE) ALICE- 10101 BOB — 11101 ALICE — 10111(REVERSE) BOB — 11111

      ALICE --> 2 BOB -->2 DRAW

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

        it's not that you can't do that . you can .But you know what , the word optimal is mentioned in the question, means if i got a chance to play then i tried my best to win , so if bob put a 1 in the string instead of reversing he will land in the winning position , instead of a draw. You can't just brute force and say bob or alice win or its a draw. its not mandiatory that if i have a chance to reverse the string then i have to reverse it , so that i will be relived from that 1 dollar penalty, you can't do that .

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

rivalq the_nightmare I am confused in the editorial for E. Aren't the k mentioned in the dp transitions and the k mentioned in the big oh notation different?

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

    Yes they are different. The one in dp transitions you can regard as a temp variable.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  • Problem B2 — Palindrome Hard
  • Please explain this case for string: 1000
  • A reverses -> 0001 (A=0 B=0)
  • B pays -> 1001 (A=0 B=1)
  • A pays -> 1101 (A=1 B=1)
  • B reverses -> 1011 (A=1 B=1)
  • A pays -> 1111 (A=2 B=1)
  • So BOB should win. But by the above code, it's making Alice the winner.
  • Please guide me where I am doing a mistake in the implementation.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Alice can win this way:

    A pays -> 1001

    B pays -> 1101

    A reverses -> 1011

    B pays -> 1111

    B = 2 A = 1, so Alice wins. Bob has no other moves.

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

      According to you Alice wins..But according to Jyotirmaya Bob wins...So what is the exact ans...Both of you correct.

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

        Alice wants to win right? So she would do exactly what I stated. Bob has no other move than just to lose. It is not logical to make a move that will allow your oponent to win.

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

In fact , some users of the Chinese online judge : Luogu said that the difficulty of these problems is not monotonically increasing and they suggested that you should have changed the order of problem B and C. the_nightmare

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

    There is only one additional case to be dealt in B2 if you look at the editorial. That would explain why they considered B2 as easier probably..

    and dp is not what most div 2 contestants used.

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

    Basically, we have to put together B1 and B2 due to contest restrictions due to which we are not able to swap B2 and C. But we have provided the scoring according to difficulty B(750+1500) total 2250 and C only 1500.

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

      In problem D's editorial shouldn't it be "We will always break before or on reaching root" instead of "Note that we will always break at the root as it is marked visited in the initial step."

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

The term "Contiguous Subarray" is much more quicker to grasp than "Subsegment".

Hope future authors see this :) Nice Contest btw

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

    but you know what you got something to learn.

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

    I mixed subsegment with subsquence, and it wasted me lots of time to solve this problem in a wrong way

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

Could someone please write a simpler edit for Problem-C, I have gone over it a lot of times but am still confused as to why the question creator went for:

value[a[i]] += (i + 1);

please help me out with the logic. I understood the task but couldn't implement it that well and now I'm even more confused.

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

    I think (i+1) refers to the total number of subarrays ending at i. Since we are using 0 indexing, so +1 for the adjustment.

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

    Consider and element i. Now if take an element j such that a[i]==a[j] and j < i then subarray a[j-i] will occur as part of all subarray's from i = 0 to j i.e j + 1 times. So value[a[i]] += i + 1

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

Can someone help me with my solution :

My idea:
Maintain a path and its endpoints.
Maintain a 'visited' array which denotes whether or not this node is in current path.
Consider 0 as base case and mark it visited and initialize both the endpoints to 0.
Iterate from 0 to i
In order to find if there can be a path having all nodes [0, i] we just need to check if the endpoints of path having all of [0, i-1] can be extended to i, so move from ith node to its parent till we find a node that is in the path that includes the nodes [0, i-1], that is first visited node.
If this node happens to be one of the endpoints then extend the path and update endpoints else there can be no such path that includes all of [0, i] nodes and we dont need to check this for following i's.

I am unable to figure out why this gives TLE !
https://codeforces.me/contest/1527/submission/116924323

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

My code is giving wrong answer. Please someone help !!

include<bits/stdc++.h>

using namespace std;

int main(){

int t;
cin>>t;

while(t--){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int count=0;
    if(n==1&&s[0]=='0'){
        cout<<"BOB"<<'\n';
        continue;
    }
    for(int i=0;i<s.length();i++){
        s[i]=='0'?count+=1:count=count;
    }
    if(count%2==0){
        cout<<"BOB"<<'\n';
    }
    else{
        cout<<"ALICE"<<'\n';
    }

}

}

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

Nice explanation of problem B2

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

Can someone give a small test for those codes which fail test case 5 by printing 1 instead of 0 at 1923rd position for problem D? Submission

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

    I got that error by incorrectly calculating in the tree "0 -- 2 -- 1" the number of pairs with mex == 2 (there are 0).

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

In problem A I am getting wrong output format Expected integer, but "2.68435e+008" found

Solution

What does the pow function in c++ return? In some previous questions also the I got WA because of pow function return type, so can anyone tell how it works, what it return and what are its constraints??

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

    pow() returns a double, while the expected output is an integer, hence the WA. Also as anubh4v stated, pow() (and log2() too) can be imprecise at times, leading to incorrect rounding of the number.

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

Can someone explain me how does the dynamic programming solution for B2 works?

From my understanding of the problem when we consider alice we add positively, when we consider bob we add negatively. But how does that happen in code? How does the code distinguish bob from alice? And how does it simulate turns?

In other words: can someone explain me how the simulation of the game occurs during the bottom up transitions of the editorial / given code?

Thanks in advance.

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

    Because dp[i][j][k][l] is the optimal answer for a state where i is the number of 00, j is the number of 01 or 10, and k = 1 denotes if the middle position in case of odd length string is 0 and l = 1 denotes that in the last turn other person reversed the sting thus we can not reverse.

    For all the states, we will assume that the current turn is of Alice and to compute the answer for that state, we will add negative of the transition states, which will denote Bob's optimal score.

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

can anyone pls tell why i am getting time limit exceeded on test case 7 in problem D MEX TREE i am just doing a dfs traversal once to calculate subtree sizes and then iterating from 1 to n and marking not visited nodes as visited in my current path and calculating answer for each mex value.

my submission link https://codeforces.me/contest/1527/submission/116996030

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

In Problem D: as mentioned in the editorial that we need to "update the subtree sizes as we move up to parent recursively", we don't need to do this. When (l!=r) we will always choose the other parent. Only when we are calculating MEX1 (the previous l was equal to r) so we have to update the size of 0 subtree only once.

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

    Yoir solution simplified the question mqnyfolds. Thanks anadii!

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

I do not know if this approach has been covered for E using divide and conquer dp. To get cost of current interval, maintain global 2 pointers on the array, sum variable and array of deque. Fit the pointer for each query. Amortized complexity over per level of dp should be N*log(N). So with K layers it becomes K*N*log(N).

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

the_nightmare's solution for D will TLE for the following case. https://drive.google.com/file/d/1K-1sb5ls2PP0lKiGQf5dy9BVuqMBvReG/view?usp=sharing

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

Problem 1527C - Sequence Pair Weight could have been done greedily (and imo it's easier). Let $$$d(x, y)$$$ denote the number of segments which contain elements at indices $$$x$$$ and $$$y$$$ (indices start from 0 so $$$x,y \in {0, 1, 2, \dots, n-1}$$$). It is easy to see that if $$$y > x$$$ then $$$d(x, y) = (x+1)*(n-y)$$$. This allows obvious $$$O(n^2)$$$ solution, but it can be done faster in $$$O(n)$$$. Let's say we have a vector $$$v$$$ and we are at it's $$$i$$$-th element.

Then, we can calculate the answer as:

$$$d(v_0, v_i) + d(v_1, v_i) + \dots + d(v_{i-1}, v_i) $$$

which is just

$$$(v_0+1)*(n-v_i) + (v_1+1)*(n-v_i) + \dots + (v_{i-1}+1)*(n-v_i)$$$

and this can be simplified to:

$$$(v_1 + v_2 + v_3 + \dots + v_{i-1} + i-1) * (n-v_i)$$$

Which you can easily calculate while iterating through the vector. Code: 124839948

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

    Shouldn't it be

    $$$ (v_0 + v_1 + v_2 + v_3 + \text{...} + v_{i-1} + i) \times (n-v_i)$$$

    ?

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

I think more short solution for A: https://codeforces.me/contest/1527/submission/127546267

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

in problem C let the array be, 1 3 1 2 1 when we take subarray , 

1 3 1 2 1  weight will be 3 {(1,2),(2,5),(1,5)}


3 1 2 1 then weight will be 1 { (3,5) }

but according to editorial the weight of second one will be 3.

anyone please reply ?

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
long long ans = 0;
for (int i=0; i<n; ++i){
	int x; cin >> x;
	ans += (n-i)*p[x];
	p[x] += i+1;
}

Only necessary for C

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

Can anyone clear me this thing?

In the solution of B1 by DenOMINATOR, it says there will be no draw.It also says that if the number of "0" is even,BOB will always win. If it is the thing then explain me a test case,

let's think of string of even number of zero,,

let it be "0000" now ,Alice will make the string "1000",,and she will have 1 point. then,as it is not a palindrom,bob will just reverse it and his point is 0. now,alice cannot reverse it,so she will make it "1001" and she will have 2 point; thus,in the end ,bob will also have 2 point,as from the next step bob will start the game,,

now ,my question is,why it is not DRAW!!??

explain me please,if i am missing any point

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

    First Alice will be forced to put a 1

    Like in the case of 0000 , it will become 1000 and Alice would have had paid 1 dollar Following this , it would be beneficial for Bob to play 1 at the ending that is make it 1001 and Bob would have paid 1 dollar aswell

    Current String : 1001 Bob : 1 dollar Alice : 1 dollar

    Now Alice will be forced to put a 1 in, therefore the new string will be 1011

    Current String : 1011 Bob : 1 dollar Alice : 2 dollar

    Now Bob will reverse , therefore Alice will be forced to put Again

    Current String : 1111 Bob : 1 dollar Alice : 3 dollar

    Therefore Bob wins since he has used up less dollars.

    → Reply