1527A - And Then There Were K

Author: loud_mouth
Idea: Bignubie

1527B1 - Palindrome Game (easy version)

Author: DenOMINATOR
Idea: shikhar7s

1527B2 - Palindrome Game (hard version)

Author: DenOMINATOR
Idea:DenOMINATOR

1527C - Sequence Pair Weight

Author: sharabhagrawal25
Idea: rivalq

1527D - MEX Tree

Author: mallick630
Idea: CoderAnshu

1527E - Partition Game

Author: rivalq
Idea: rivalq

• 18 months ago, # ^ | ← Rev. 2 →   +13 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)

• 18 months ago, # ^ | It is given in the input section that string ss contains at least one 00

  • 18 months ago, # ^ | But for this, why Draw is not the correct answer?

    • 18 months ago, # ^ | Yes, technically it should be DRAW but to avoid confusion we omitted that case

      • 16 months ago, # ^ | ← Rev. 2 →   0 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(); } }

• 18 months ago, # ^ | We precompute the dp and use it to answer all test cases

• 18 months ago, # ^ | Dp is pre-computed not run for each test case

• 18 months ago, # ^ | I think this will TLE in python

  • 18 months ago, # ^ | It does not. PyPy 3 submission: 116877296

• 18 months ago, # ^ | Yes, you can do that too, but it would take too much time and result in TLE

  • 18 months ago, # ^ | ← Rev. 2 →   +2 The complexity is logn for this so it won't TLE. At each iteration, you're setting at least 1 set bit to 0.

• 18 months ago, # ^ | ← Rev. 2 →   0 Hey! I am not able to understand why I am getting TLE for this solution :( Solution This is my submission : 116759121

• 18 months ago, # ^ | Actually, for example 000000000000 game goes- AA pay 11100000100000 BB pay 11100001100001 AA pay 11100101100101 BB pay 11101101101101 AA pay 11111101111101 BB reverse 101111101111 AA pay 11111111111111 BB wins Now, analyse 010101010010101010

• 18 months ago, # ^ | 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 practicepractice, things would become somewhat more intuitive and reflexive.

• 18 months ago, # ^ | I am using divide and conquer dp optimization for problem E. can you help me why i am getting TLE code

  • 18 months ago, # ^ | for(int k = mid; k >= optl; k--) { kk should be enumerated from optroptr to optloptl, not midmid to optloptl. Otherwise, the parameter optr is unused.

• 17 months ago, # ^ | How to prove complexity of two pointers trick?

• 18 months ago, # ^ | ALICE — 10100 BOB — 10101 ALICE- 10111 BOB — 11101 (REVERSE) ALICE — 11111 ALICE --> 3 BOB -->1 BOB WINS

  • 18 months ago, # ^ | Why it is not possible? ALICE — 10100 BOB — 00101(REVERSE) ALICE- 10101 BOB — 11101 ALICE — 10111(REVERSE) BOB — 11111 ALICE --> 2 BOB -->2 DRAW

    • 18 months ago, # ^ | 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 .

• 18 months ago, # ^ | Yes they are different. The one in dp transitions you can regard as a temp variable.

• 18 months ago, # ^ | 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.

  • 18 months ago, # ^ | According to you Alice wins..But according to Jyotirmaya Bob wins...So what is the exact ans...Both of you correct.

    • 18 months ago, # ^ | 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.

• 18 months ago, # ^ | ← Rev. 2 →   +4 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.

• 18 months ago, # ^ | 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.

  • 18 months ago, # ^ | 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."

• 18 months ago, # ^ | but you know what you got something to learn.

• 18 months ago, # ^ | I mixed subsegment with subsquence, and it wasted me lots of time to solve this problem in a wrong way

• 18 months ago, # ^ | 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.

• 18 months ago, # ^ | 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

  • 18 months ago, # ^ | Oh now i get it, thank you so much

    • 18 months ago, # ^ | Happy to help

  • 9 months ago, # ^ | I was confused over this part. Thanks now,I got it.

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';
    }

}

• 18 months ago, # ^ | This is my logic, you can use to improve your code 116814530

• 18 months ago, # ^ | ← Rev. 2 →   0 I got that error by incorrectly calculating in the tree "0 -- 2 -- 1" the number of pairs with mex == 2 (there are 0).

• 18 months ago, # ^ | 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.

  • 18 months ago, # ^ | I will keep that in mind. Thanks

• 18 months ago, # ^ | 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.

• 18 months ago, # ^ | Yoir solution simplified the question mqnyfolds. Thanks anadii!

• 10 minutes ago, # ^ | Shouldn't it be (v0+v1+v2+v3+...+vi−1+i)×(n−vi)(v0+v1+v2+v3+...+vi−1+i)×(n−vi)

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) }

• 5 months ago, # ^ | I ran the same code. Its giving correct answer : 7

  • 5 months ago, # ^ | can you please explain me ? how is it possible

    • 5 months ago, # ^ | Check input format