Tsovak's blog

By Tsovak, history, 5 weeks ago, In English

Thank you all for participating in the round.

All the problems were created by BiNARyBeastt during our classes in winter.

A — Simple Palindrome

Solution
Code

B1 — The Strict Teacher (Easy Version), B2 — The Strict Teacher (Hard Version)

Solution
Code

C — Lazy Narek

Solution
Code

D — Alter the GCD (Check this comment or the video editorial for an easier solution).

Solution
Code

E1 — Subtangle Game (Easy Version), E2 — Subtangle Game (Hard Version)

Solution
Code (E1)
Code (E2)
  • Vote: I like it
  • +53
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

We trained Tsovak to post this faster than the speed of light, but we failed miserably due to the AI situation.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +46 Vote: I do not like it

    We actually leart about that super-smart AI two days ago and it appeared to be able to solve the problems A to D, and almost E1, so we had to change D within less than 24 hours)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      damn, thank you for the dedication

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        That is most likely because the person doing the prompts did a really good job with smart prompts. Many of us tried the new paid version a few times, and it didn't manage to get past test 6.

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

          He claims no special prompt here: https://codeforces.net/blog/entry/133962

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

            Then maybe we got unlucky. For example, when I was checking for D, it managed to solve it the first two times I asked. Later, I copied the statement and sent it again, but it gave a wrong answer. I guess its results are not consistent all the time.

            I'm not sure how it works to be honest, so I'm still not sure if this is the reason.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

      I have an idea, maybe we don't need to be afraid of AI, if people can use AI to solve problems, we can also use AI to generate problem sets that can confuse itself. But to do that, maybe we need knowledge and experience in both CP and writing prompts.

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

      then what is the point of my life ? ToT

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

281181064 Can somebody tell me why this is giving WA? Suppose array is 2 3 4 5 , and teachers are at 2 5 , the possible values for mid can be both 3 and 4 . I simply calculated the min value for both the possible mid values from each of the teachers. If the array was something like 2 3 4 , then there was only 1 mid (ie 3) hence no issue.

281191926 This passes , wherein I am taking only the (min_max)/2 value, ie 3 for array 2 3 4 5.

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

    The thing is, when teachers travel a distance of min(x - b[0], b[1] - x), then x can choose to remain at its current place. After this, you can directly calculate the mid point of the new locations of the teachers, because x would try to go towards the teacher, which is farther from it.

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

      "you can directly calculate the mid point of the new locations of the teachers"

      The midpoint and the distance from the teachers will same regardless, wont it?

      2 3 4 5 if I take 3 as mid, 3-2=1, 5-3=2. min=1; if I take 4 as mid, 4-2-2, 5-4=1. min=1;

      Since the teachers will always be moving towards the middle, the mid value will remain the same every time right?

      You can say that with this insight, I could just find the answer for mid=(max+min)/2 and it would satisfy the answer, but at the same time finding min distance from both and then printing the minimum shouldn't result in WA.

      Apologies if I missed something.

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

        Yes. You're right. Mid point doesn't change. But the mid point you are talking about, is the array mid point, and not the actual mid point. The actual mid point of two teachers would be (b[0] + b[1]) / 2, and NOT the middle element of the subarray from b[0] to b[1]. Hence, for array [2, 3, 4 ,5], the mid point of the array is (5 + 2) / 2 = 4, and not b[4/2] or b[4/2-1]. Hence, the number of steps required would be (b[0] + b[1]) / 2 - b[0], which is nothing but (b[1] - b[0]) / 2.

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

          Thankyou for your time. The code got accepted, I missed putting the condition in brackets. So demotivating.

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

for B, i didnt see that he can choose not to move, and i coded the completely wrong solution for 20 mins, tragic. great problem C, i absolutely loved it.

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

can someone help me why this code gets wrong answer for problem C

submission: https://codeforces.net/contest/2005/submission/281243184

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

    I think your algorithm is n^2 which is too slow, regardless of correctness.

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

    Maybe you need to learn how to analyze complexity.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

how to train for problems like C?

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
Spoiler
»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Can someone explain how did I get TLE in C? I thought my code works in $$$O(N * M * 25)$$$: 281197818

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

    It is $$$O(nm + n^2)$$$, no?

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

    I made the same mistake as you. Your actual complexity is $$$O(25NM + 25N^2)$$$ due to the for loop calculating dp, and there's no upper bound on the sum of $$$N^2$$$ across all test cases, only upper bound on $$$NM$$$ :sob:

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

    Can anyone plz check my submission , I'm getting TLE on tc19 281877355

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

The contest is amazing!

my only complaint is the protests on problem C could have been better ):

I was going to become a CM for the first time If there were stronger protests.

Thank you for the contest as usual!

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

281249215 can anyone explain why this code getting wa on pt 11 problem c ! i dont think there is an wrong idea !

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

for problem A

Expected output : aaeiou , palindromes subsequences a , a , e , i , o , u , aa

My output : aeioua , a , e , i , o , u , a , aa

Why my output is considered as wrong answer , can anyone explain?

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

    For the string aeioua, other palindrome subsequences include aea, aia, aoa, and aua.

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

    You missed palindromes like aea , aia , aoa , aua

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

I got TLE at C problem and I think it works in (5 * n * m)
solution
am I missing something ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It is O(nm+n2) 
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How ? I wrote a function that works in (m) and I loop only once over n

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    you just need a little bit of optimization. using vector to replace map is ok. see this submission : 281260161

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

      OMG...just the map that works over only 5 chars have 1.5 second difference !
      thanks for the accepted code it was annoying me

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

lol, so fast

... thanks :D

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

Anyone else lost question C by initializing dp to -1 instead of -inf? :(

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Nice round.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

thanks for the fast editorial!

in the problem $$$B1/B2$$$, C++ upper_bound and lower_bound both should point to element strictly $$$>a[i]$$$ (david's position) since $$$b[i]$$$ only contains teacher's positions. or is it not so? my contest submission using both lower_bound and upper_bound got WA.

my contest submission

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Bitset helps to solve E2 without any observation. 281264340

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Why is my submission for C getting TLE on test 11? I think the complexity is $$$O(5*N*M+10*N)$$$.

Submission: 281248462

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

    You're initializing your dp with -1, so if the answer at a certain state was -1 it will call the solve() function again instead of returning the previously calculated answer (which is -1). Instead you can initialize with -INF or create another array to check for visited states.

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

      Thanks, that was an overlook.

      Although, I realized I linked the wrong submission earlier. Updated the submission link.

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

For problem E1, can someone help me understand why Narek wins in this testcase :

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

This is my submission which is failing for this test : [submission:https://codeforces.net/contest/2005/submission/281255124]

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    1. Move $$$1$$$. Tsovak takes $$$(1, 1)$$$.

    2. Move $$$2$$$. Narek takes $$$(2, 2)$$$.

    3. Move $$$3$$$. Tsovak takes $$$(3, 3)$$$.

    4. Move $$$4$$$. Narek takes $$$(4, 4)$$$.

    5. Move $$$5$$$. Tsovak takes $$$(5, 5)$$$.

    6. Move $$$6$$$. Narek takes $$$(6, 6)$$$.

    7. Move $$$7$$$. Tsovak loses since the array ended. Narek wins.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Oh, I seem to have misunderstood the problem. I thought that they can only choose elements from the array A. Since the array A has only the element 6, how can Tsovak pick (1, 1) or (2, 1)?

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

      I've updated the testcase correctly. Can you look and tell me now why Narek wins?

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

        Edited my comment since it would be misleading for the readers otherwise.

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

funny how in problem C "problem tags" there is greedy and the first thing editorial says is that greedy approach doesn't work.

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

    It is my bad for not properly stating what I meant by greedy in the hint section. The tag is relating to the fact that you can greedily count the score when you choose one string. I meant that you can't do greedy on each string without considering their connection with each other by dp.

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

can you please share some tests for C, cant debug it :(

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

I solved E1 in O(n*m*l) time complexity. Can anyone uphack this solution?

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

    I think this is the intended complexity for E1

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

      anyone know why it can pass O(nml) even when you iterate the full 300^3?

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

      I fail to understand why they have given the upper limit of the numbers as 7. I never used that fact in my O(n*m*l) dp

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

        This is only required in E2. For E1, a solution with O(n * m * l) should pass

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

          But in E2 they have not mentioned the upper limit to be 7

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

        That is to help you make an important observation for E2. If you check all the hints, you can see what I mean.

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

          why make O(nml) passable when the intended for E1 is O(nm) based on the 7 observation?

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

            To kind of help people make that observation for E2. Also, we were not allowing O(nml) pass initially. The difference between E1 and E2 used to be only between the matrix numbers. Testers struggled to find this observation though, so we changed it.

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

what is wrong in my recursive dp soltuion 281269592 please help me to debug, tried for so long but not able to find

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

    I made some changes to it and now it passes. I know this part was a problem:

    if (ind == arr.size()) {
        return -ct1;
    }
    

    because I made the same mistake during the contest. It should be (-2) * the current "narek" index, which in your code is last. 281276687

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

      Thanks really helpful

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

      the reason for wrong answer is

      dp=max(ans1,ans2) in place of dp=max(0,max(ans1,ans2)
      
»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Tsovak BiNARyBeastt Kaey TheScrasse

I tried uphacking my solution 281180437 for problem D, and it got an unexpected verdict.
I believe one of the correct marked solutions on polygon also gets TLE on this hack test case.
Can you please take a look at it and fix it?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +36 Vote: I do not like it

    We were aware of this, and we also know a solution that won’t exceed the time limit. We are currently working on updating the editorial and the main solution accordingly. TheScrasse coded the solution to D just minutes before the start. We took a risk by making the problem harder, asking for the number of ways to get the maximum GCD, so that AI wouldn’t be able to solve it. Thanks for noticing this though!

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

I solved E1(2100 rating on clist) but was not able to submit it because of internet connetion problem.

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

can someone help me with why we cant solve problem c with take not take dp?

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

I tried top down approach for C, but am getting WA on test 2, can somebody tell me what's wrong? 281270159

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

Why this solution is accepted after sorting and not without it

int main() {
    int t;
    cin >> t;
    vector<string> vowels = {"u", "o", "i", "e", "a"};  
    while (t--) {
        int n;
        cin >> n;
        string result = "";
        for (int i = 0; i < n; i++) {
            result += vowels[i % 5];  
        }
        sort(result.begin(),result.end());  
        cout << result << endl;  
     }
    return 0;
}
    
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because sorting it puts all the a's together, all the e's together, all the i's together and so on. It doesn't have to be sorted but the occurrences of every vowel need to be grouped together. And sorting is one way to do that. This is an example of a string that's not sorted but still works: eeeoooiiiaauu

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

    Because for example n = 6 Then without sorting it would print: uoieau It also contains the following palindromic subsequences: uou, uiu, etc Whereas after sorting it prints: aeiouu, which doesn't contain these subsequences Basically you were missing the core logic

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

My submission for C can someone please help me figure out why this solution TLE'd? This seems to be O(5*m*n) :(

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

    well your solution looks exactly same as mine and even i got TLE on pretest 11 during contest so i am assuming we did same mistake, the thing is you have intialised your dp array with -1. during calculation of dp[i][j], some of the states answers can be negetive when gpt gets better score, and there is some case where your dp[i][j] is getting calculated as -1 itself. and hence your just going on in that cycle where your dp[i][j] is always -1. i just replaced -1 with -1e18 and it worked.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

About C:Since you want $$$O(n^2)$$$ algorithm got a TLE, why don't put the data in pretest? $$$n \le 10^3$$$ is very deceptive!

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

    Sorry! We overlooked that there might be a solution with that complexity. Unfortunatly, none of the testers came up with anything like that as well.

»
4 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

I have no idea why "if $$$dp_{k,i,j}$$$ wins, then $$$dp_{k + 2, i, j}$$$ also wins".

In fact, I add an assertion in my code, and it received RE(assertion failed) on E1, test 2.

The submission is here: 281298383

Here is (probably) the hack:

1
6 6 6
1 2 3 4 5 6
1 1 7 7 7 7
7 2 7 7 7 7
7 7 3 7 7 7
7 7 7 4 7 7
7 7 7 7 5 7
7 7 7 7 7 6
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Note that $$$dp_{1,1,2}$$$ is $$$1$$$, while $$$dp_{3,1,2}$$$ is $$$0$$$.

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

    In your example, regardless of the value of k, i, or j, the starting player can always start with the last 6 (the one at (n, m)), and the subrectangle starting at (n+1, m+1) will be empty. According to the rules, this means the second player loses. So actually all dp values are 1 in that case.

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

      You are right though. I think it's not correctly written there.

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

    We fixed the editorial. The solution was still correct. We just had a wrong hint there for some reason.

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

rare c d e dp contest

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

/

»
4 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Why in problem C, I let define int long long in my compiler output 0 5 0 7 (correct result of test 1) but in my submission it is 0 5 0 6. After deleting define int long long then it has AC.

My submission

»
4 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

A (probably) more simple solution to D.

We will also make use of the fact that there are only $$$O\left(\log(\max(a))\right)$$$ different prefix gcd, but we will use it on all subsegments instead:

  • Iterate $$$l$$$ from $$$1$$$ to $$$n$$$.
  • Imagine that we already have some $$$r \geq l$$$, then we have 3 ranges to consider $$$[1, l)$$$, $$$[l, r]$$$, $$$(r, n]$$$.
  • For $$$[1, l)$$$, we can maintain $$$\tt{prefix}_a$$$ and $$$\tt{prefix}_b$$$ as $$$\gcd(a_1, a_2, ..., a_{l - 1})$$$ and $$$\gcd(b_1, b_2, ..., b_{l - 1})$$$.
  • For $$$[l, r]$$$, realise that there are only $$$O\left(\log(\max(a))\right)$$$ different values of the gcd of both $$$a$$$ and $$$b$$$, and each values will correspond to a continuous range of $$$r$$$.
  • For $$$(r, n]$$$, the same thing apply.
  • So in fact, for each $$$l$$$, there are only $$$O\left(\log(\max(a))\right)$$$ different values of the result, and each value has a continuous range of $$$r$$$.
  • So if we can find all those ranges and iterate through them, we will have $$$O\left(\log(\max(a))^2\right)$$$ per $$$l$$$, assuming $$$\gcd$$$ take $$$O\left(\log(\max(a))\right)$$$.

To find the ranges for $$$(r, n]$$$, we can simply iterate the arrays in reverse and maintain the gcd ranges, leading to $$$O(n\log(\max(a)))$$$.

To find the ranges for $$$[l, r]$$$, build a sparse table with gcd, and keep expanding the divisible ranges to find the points where the continuous gcd changes. This will take $$$O(n\log(n)\log(\max(a)))$$$ to build and $$$O(\log(n)\log(\max(a)))$$$ to find the ranges for each $$$l$$$.

You can see my implementation in contest: 281217872

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    This solution have since been uphacked by 415411. The test seems to put the algorithm in the worst case and that was slower than model.

    Thanks to the hack, I was able to improve upon the algorithm:

    • Building the gcd sparse table is useless, it allow us to find the $$$[l, r]$$$ ranges as a query in $$$O(\log(n)\log(max(a)))$$$, but this is not necessary.
    • Instead of iterating $$$l$$$ from $$$1$$$ to $$$n$$$, we can do it from $$$n$$$ to $$$1$$$ instead.
    • At $$$l$$$, we calculate all the different $$$r_i < r_{i + 1}$$$ such that $$$[l, r']$$$ have the same $$$gcd$$$ for all $$$r_i \leq r' < r_{i + 1}$$$.
    • When iterate to $$$l - 1$$$, we append the element at $$$l - 1$$$ to the beginning of these ranges.
    • Realise that this is equivalent to adding the range $$$[l, l]$$$ and updating the gcd of the existing ranges.
    • We also merge the equal ranges, so the amount of range is always $$$O(\log(\max(a)))$$$.

    The above actually improve the algorithm to $$$O(n\log(max(a))$$$, except for the calculating answer part:

    • We need to calculate prefix and suffix gcd for both arrays, this is at first glance $$$O(n\log(\max(a))$$$.
    • Howerver, the complexity of prefix and suffix gcd is actually just $$$O(n + \log(\max(a))$$$.
    Proof

    Applying the same idea as above to the ranges we have:

    • We add a new range $$$[l, l]$$$ $$$n$$$ times.
    • Each of these original range would have the amortized time with $$$\gcd$$$ equal to $$$O(\log(\max(a)))$$$.
    • So it's $$$O(n\log(\max(a))$$$.
    • We also have to merge the equal range, which happen $$$n$$$ times and each time we have at most $$$O(\log(\max(a)))$$$ ranges, so it also $$$O(n\log(\max(a))$$$.

    Finally we have to calculate the answer once we have all the ranges. I can't seem to find a way to improve this to $$$O(n\log(\max(a))$$$, so it's still $$$O(\log(\max(a))^2)$$$

    You can see my new code: 281316893. And the sanity check version where I reversed the array (so I don't take advantage of the fact that most interesting stuffs happen at the end of the hack array): 281316958

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

B2 — The Strict Teacher (Hard Version), Why did he find index through upperbound? Can't we do it by lowerbound? In upperbound case, the index-1 value teacher can be in same cell as studentright?

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

can anybody explain the recursive approach of E1

int fun(vi &res,vvi &arr,int i,int j,int ind){
    if(i>=arr.size() || j>=arr[0].size() || ind==res.size())return 0;
    if(dp[i][j][ind]!=-1)return dp[i][j][ind];
    int ans=fun(res,arr,i+1,j,ind)||(fun(res,arr,i,j+1,ind));
    if(arr[i][j]==res[ind]){
        ans|=fun(res,arr,i+1,j+1,ind+1)==0;
    }
    return dp[i][j][ind]= ans;
}
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/2005/submission/281279780 why this is getting tle? I think its complexity is

N*M*5

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

can somebody help me in figuring out why my E1 solution tles? i'm using minimax technique which uses 1 for the win of Tsokav and -1 otherwise. the time complexity is $$$ O(l * n * m) $$$ which is fine, no?

Submission

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

Can anyone tell me why I am getting a WA? I have reviewed my solution many times and I can't seem to find the problem.

https://codeforces.net/contest/2005/submission/281266413

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

    Why are you sorting your q vector? You are supposed to answer the q queries in order Example: q = 5 2 Lets say answer for 5 is x and answer to 2 is y So expected output is: X Y

    But you will output Y X

    Due to sorting

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

      Ohhhhhhhh now I get it, I was sorting because I thought the problem might be solved using two pointers, so I needed to sort both the m and q vectors, but I forgot that by this I would change the order of output. Also, Do you know why I am getting TLE in this solution https://codeforces.net/contest/2005/submission/281314216, while this one is fine https://codeforces.net/contest/2005/submission/281314471, the only difference is that I was using a set in the first one, but changed it to a vector and sort in the second one. Thanks in advance.

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

        the TLE in sets is because the syntax for lowerbound and upperbound is a bit different for sets. doing set.lower_bound(set.begin(), set.end(), x) is actually O(n*logn), while that is O(logn) for vectors. for sets you do: set.lower_bound(x), this is O(logn) in case of sets

        you can refer to this blog for more insights https://codeforces.net/blog/entry/55450

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

For B1, when david is between both the teachers. How about going towards the teacher1 till he finds he is safe and moving back towards teacher2 till he finds he is safe?

Giving WA. 281236022

»
4 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

problem E2

If $$$dp_{k,i,j}$$$ wins, then $$$dp_{k+2,i,j}$$$ also wins.

Why is that true ?

if the grid is

4 2

2 2

and the array is 4 1 3

$$$dp_{1,1,1}$$$ is winning but $$$dp_{3,1,1}$$$ isn't

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

    You are correct! I think the solution is correct as well, but we just explained with a wrong hint there. we'll fix it very soon.

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

    We fixed the editorial. The solution was still correct. We just had a wrong hint there for some reason.

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

      Thanks a lot , for the problems , editorial and kindness

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

why was there no pretest in C that crush solution O(n^2)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Sorry! We overlooked that there might be a solution with that complexity. Unfortunately, none of the testers came up with anything like that as well.

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

E1 can be solved with a complete search using minimax algorithm. It ac's with alpha-beta pruning

Submission

Also, does anyone know how to calculate time complexities of programs like this?

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

Fun Fact: I didn't read the constraints in C carefully and submitted O(n^2) dp solution. It passed pretests but sadly it failed system test. So happy.

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

why for problem A , for n=6 , aeioua is not a right answer ?

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

    Because the string aaeiou only has 6 palindromes a,aa,e,i,o,u. The string aeioua has all those as aaeiou, but also has aea, aia,aoa,aua. So its a suboptimal answer

»
4 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

D can be solved in $$$O(nlog^2(maxA))$$$ with a simple divide-and-conquer formulation. In the merge step, we only consider the $$$log$$$ unique gcds of suffixes in left half and prefixes for right half and store counts in map. Then just brute force the maximum and update counts (taking care to add up counts if maximums are equal). 281328508

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    This should be official solution. Not only it's several times faster but also, its lot clearer and easier to implement, understand and it doesn't separate small and large testcases (🤢).

    On first it looks like $$$O(nlog^3(maxA))$$$ but when you consider the fact that on lower levels of DnQ you have $$$min(log(maxA),len)$$$ elements in map with simple for loop you can calculate that for $$$n = 200000$$$ in total you have ~16.000.000 operations.

    code to check complexity

    My code: 281365054 (tried to make it as crisp as possible)

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

      How do we know the map's size will be $$$log(maxA)$$$ ? If there are $$$log(maxA)$$$ possibilities for each array, then the map of pair of int should be $$$log^2(maxA)$$$ right? (As there are that many combinations?)

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

        As you scan in one direction, either the gcd of first array changes or gcd of second array changes. If we pick the positions where either one changes, you should have the union of these positions, which is $$$2 \cdot log$$$ positions.

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

      Divide and conquer is not even necessary. A single left-to-right sweep is enough: 284726937

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    This is actually a great way to solve the problem! We changed the problem from only asking for max gcd to asking the amount of ways to get it, so we had a very short time to code two solutions and compare them. With the help of the coordinator, we managed to code something. This is why our official solution is messy and weird. We didn't have enough time to find something good.

    I added your comment and my updated video editorial in the blog to have something that's easier.

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

    in merge step, why are you not considering gcd of suffix or prefix ?

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

    Hi Newtech66 can you please write this again in detail, so that person of my level can also understand. means can you break down the solution in different parts. Thank you

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

      First, you divide the array into two halves and solve the problem of finding mx — the best sum of gcd(Ai) + gcd(Bi) and cnt — the number of pairs (l,r) that achieve this mx, for both halves. Then, you find the best answer (either {mx1,cnt1} or {mx2,cnt2} or {mx1,cnt1+cnt2} if mx1 = mx2).

      This is the best answer you can get if you consider each half independently. But you can also choose a segment [l,r] such that l <= mid <= r. In this case, gcd(Ai) will become a gcd of: {a prefix of array A: [1,l-1], a suffix of the left half of array B: [l,mid] such that these two segments become the new left half of A} and {a prefix of the right half of B: [mid,r] and a suffix of A: [r+1,n] such that these two segments become the new right half of A}. Something similar applies for array B. To find the best way to choose (l,r), you calculate every possible value of the gcd of the first half depending on l i.e. you try every possible value of l form 1 to mid and calculate gcd([1,l-1],[l,mid]) and increase the counter of this value by one (so that you can calculate the number of ways to achieve it), and then you do the same for r. After that you brute force on every possible pair of values of the first and second halves, calculating their gcd and updating the answer mxe. Finally you check whether this mxe is better than what we calculated for every half independently.

      I hope this helps!

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

    Another solution using a DnC approach, but without the need to compute prefix or suffix arrays, is to maintain the possible pairs of GCDs in a map, with 3 associated counts: (1) for no swap; (2) for one-way swap; and (3) for two-way swap. Then, the merge step is a matter of traversing the pairs on both sides and multiplying the counts. In the end, we find the maximum sum and its count, over all pairs in the entire range. 281855060

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I realised the number of GCD's we are going to ever obtain are going to be $$$O(log(max(a_1,b_1)))$$$ (ish) and decided to brute force the entire thing.
    Iterating over the indices and maintaining the counts of GCDs obtained by respective swaps.
    My Submission — 282869542

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

Solve A B C E1. Nice dp contest!

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

can i know why i am getting a wrong answer on problem B1 281322308?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    l = min(l,r);
    r = max(l,r);
    

    In case of l = 5, r = 3 (when l is maximum), you are losing the value of l. Maybe you want this: if(l > r) swap(l, r);

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

Submission

can anyone find out what is wrong with this solution for C problem using dp.

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

281345109

Can someone explain why this solution for problem C results with WA on test 11?

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

A actually has a much easier solution, you can just fill the string with equal amounts of vowels and then sort it. It's AC. It does essentially the same thing but fsr people took a long time figuring A out.

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

Why is my submission for D getting TLE on test40? I think my complexity is $$$O(nlog^2n)$$$. And on test37 it needs a long time (over 3000ms) running.

submission 281364038

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

can someone please help me figure out why I am getting runtime error.

Even tho i think i am not accessing anything out of bound. am I missing edge case where it could happen?

my submission : https://codeforces.net/contest/2005/submission/281249882

edit : didnt know CF shows which line error occured once contest is done. It is showing out of bound in prefix[i — 1] . But i will be always between 1 <= i <= n so not understanding why it will go out of bound

  • »
    »
    4 weeks ago, # ^ |
    Rev. 7   Vote: I like it 0 Vote: I do not like it

    check out this test case

    1
    1000000000 1 1
    6
    1000000000
    
    hint
    answer
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the test case you have mentioned is not within the constraints here ai is 100000 and n is 8 ai <= n is not true in the given case

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

        sorry for that ,i changed it

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

          Thanks a lot for your help. I was not aware of this fact. one more question what is the max size of vector i am allowed to create in contest?

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

            i don't know but the largest i have ever created was 1e7

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

Hello mates Help, I am getting TLE in problem C[submission:281406037].Even though i have used the time complexity of O(n*m*25) <= 2.5*10^7..which should run as per my knowledge..Please look into this i want to know why am i getting TLE...

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

Why My code fails in test case 2 for problem C

link: https://codeforces.net/contest/2005/submission/281415696

also I found a testcase to which my code gives wrong answer which is

1
3 3
nara
reka
knae

My Answer: 0

Correct Answer: 2

Got it!

»
4 weeks ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

For Problem C: Another way to do it which does not require thinking about $$$dp_i - 2 \cdot i$$$ is to modify the score: Add a $$$-1$$$ to each occurrence of the letters in "narek" and add a $$$+10$$$ when you complete one instance of the full word "narek", in your $$$dp$$$.

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

plz help me. I can't understand why this code is on time limit of B2. https://codeforces.net/contest/2005/submission/281483618 I've made a empty set and inserted. I know it is not faster than vector, but anyway, is the time complexity M*O(lgM)?

»
4 weeks ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

I didn't quite follow the editorial for E, but here's another way to look at it.

As usual for such problems, we can define winning states as those from which you cannot reach a losing state and likewise. Now, let's try to process the game starting from the last element, and at each point, what we want is to mark each cell on the board as a winning or losing position.

It actually turns out, that such a set can be easily marked by maintaining the set of "innermost" positions of numbers (those cells $$$(r,c)$$$, such that no other cell $$$(r',c')$$$ exists with the same value such that $$$r'>r$$$ and $$$c'>c$$$). Note that this set has size $$$O(n+m)$$$.

As we process, we need to update a set of "dominant" positions $$$S_i$$$. Basically, the next set $$$S_i$$$ for the next value is that subset of "innermost" positions which "dominates" the previous set. That is the subset of "innermost" positions $$$(r,c)$$$ for $$$a_i$$$ such that no element $$$(r',c')$$$ of $$$S_{i+1}$$$ exists with $$$r'>r$$$ and $$$c'>c$$$.

Updating this set is simple: due to the structure of "innermost" positions, we can find any violations in $$$O(\log(n+m))$$$ time with a binary search. I think, even two pointers can work. Tsovak wins if the dominant set $$$S_1$$$ for $$$a_1$$$ is nonempty.

The overall solution works in $$$O(n \cdot m + l \cdot (n+m) \log(n+m))$$$.

My explanation could greatly benefit with diagrams and care, but here's the submission: 281490495

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

test"> test2 test3

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why in problem E2 we need to store two dp's? Why we can't just do dp[i][j] — min k that dp[k][i][j] wins?

https://codeforces.net/contest/2005/submission/281529257 — submission with one dp

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

    agree, it's working for me too with only 1 dp. I don't understand the point to have 2 dp's here.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define all(v) begin(v),end(v)
int callDp(int i, int ind, vector<string> &str, string &s, vector<vector<int>> &dp){
          if(i==str.size()){
              if(ind!=0){
                  return -ind;
              }
              return 0;
          }
          if(dp[i][ind]!=-1)
              return dp[i][ind];
          int take=0,nottake=0;
          int cntC=0,x=ind;
          for(int j=0;j<str[i].size();j++){
              if(str[i][j]=='n'||str[i][j]=='a'||str[i][j]=='r'||str[i][j]=='e'||str[i][j]=='k'){
                  if(str[i][j]!=s[ind]){
                      cntC++;
                  }
                  else if(str[i][j]==s[ind]){
                      if(ind==4)
                      take+=5;
                      ind=(ind+1)%5;
                  }
              }
          }
          take=take-cntC+callDp(i+1,ind,str,s,dp);
          nottake=callDp(i+1,x,str,s,dp);
          return dp[i][x]=max(take,nottake);
}
void dekhteHain(){
     int n,m;
     cin>>n>>m;
    //  vector<vector<char>> str(n,vector<char>(m));
    vector<string> str(n);
     string s="narek";
     unordered_set<char> st={'n','a','r','e','k'};
     vector<vector<int>> dp(n+1,vector<int>(5,-1));
     int cnt=0;
     for(int i=0;i<n;i++){
        cin>>str[i];
     }
     int ind=0;
     cout<<callDp(0,ind,str,s,dp)<<endl;

}
int32_t main() {
    int t;
    cin>>t;
    while(t--){
        dekhteHain();
    }
}

Can someone please explain why is this code giving TLE, It is code of C problem

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

Can anyone please help me, I am getting wrong answer on test case 2 281575266

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

can some one find the counter test case for this E1 solution which is failing at case 36 it's just same as the editorial but I'm using the whole L array https://codeforces.net/contest/2005/submission/281680950

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

Can someone point out what is wrong in my solution of C. 281726079

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

    Maybe rewrite it, and decrease number of states. There's no need for so many states for this problem.

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

https://codeforces.net/contest/2005/submission/281714678 Can someone tell me why my code is giving tle for problem C , my complexity is o(n*m) which should work

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

How can you achieve O(n*m*5) for problem C? I found the solution in tutorial with a complexity of O(n*m*25), and found no ways optimizing the solution to O(n*m*5).

Oh, sorry. I found that If you preprocess the matched types for each character in string before calculating the score for each string, it will be O(n*m*5). (I named state variables as cur_type and matched_type, in my code here https://codeforces.net/contest/2005/submission/281816751)

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

[submission:281823254]the problem C, can someone tell me what fault in my code? I think we can use the end of the previous string to transfer the following string.

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

E1, just cannot understand why the player would win when choosing that "inside" x, he would also win in that bigger matrix

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

    Your turn to play number x. You have two choices x, either go submatrix A or go submatrix B where B is a submatrix of A. If opponent can win from submatrix B, then he also wins from A (use same strategy as from B). If he cannot win from B then you do not care about A, just go B.

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

      oh yes, i was doubting why the it's my turn after i chose a 'x'. the editorial does not say the opponent.

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

For D,I simply found that some prefixes are equivalent(two prefixes are equivalent when them have the same prefix gcd of a[] and b[])and a series of equivalent prefixes form a segment.So the number of these segments is at most 2*log(1e9).Then I do the same thing for suffixes.Calculating the max answer is easy and counting can be solved by enumerating a pair of "segment formed by equivalent prefixes"and"segment formed by equivalent suffixes" and then using two pointers.I think this would be a n*log^3 solution but it's easier to come up with this idea.Your text to link here...

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

For problem D, we have a more direct and simpler implementation method. Note that for any sequence, its prefix GCD (or suffix GCD) can have at most $$$O(\log m)$$$ different values (where $$$ m $$$ is the value range). Thus, we consider enumerating the left endpoint $$$ l $$$ and calculating the contribution of different right endpoints $$$ r $$$ to the answer. Based on this observation, we know that for a fixed $$$ l $$$, the different values of $$$ \gcd_{i=l}^{r} a_i $$$, $$$ \gcd_{i=l}^{r} b_i $$$, $$$ \gcd_{i=r+1}^{n} a_i $$$, and $$$ \gcd_{i=r+1}^{n} b_i $$$ each have $$$ O(\log m) $$$ possibilities. Therefore, we use a monotonic stack and suffix GCD to maintain each of these four values (keeping track of their values and corresponding continuous segments, which are limited to $$$ O(\log m) $$$), achieving a complexity of $$$ O(n \log^2 m) $$$ with a small constant.

Sample solution: https://codeforces.net/contest/2005/submission/282729163

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

E2:where it is written in the problem statement that there are no duplicates in a?

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

    It's not. If you read one of the hints, it tells you that when a number appears for the 2nd time, we can cut the array from there and not consider the right part.

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

      thank you, I didn't see the hints of E1 before.

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

I solved E2 differently from the one in editorial... I just found the pareto optimal points (which are O(n+m) for each element of the grid and brute forced the recursion without any memoization either and it worked loll...

So the recursion works for O(l*(n+m))

Here's the sub : https://codeforces.net/contest/2005/submission/282989751

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

    can you elaborate

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      So take any element in the grid. If the element is at two indices (i,j) and (p,q) where i<p and j<q, then the claim is the choosing the index (p,q) will always leave you equal to or better off, than choosing the index (i,j). (This can be easily verified taking an example).

      Now that means... for each element there will be a set of pareto optimal points. Consider the example:

      1 2 3 4

      2 3 3 4

      3 2 4 1

      1 4 2 3

      Here the pareto points for 4 are (4,2), (3,3), (2,4). Basically all those points (i,j) such that you won't find any more 4's in the grid [i+1:n][j+1:n]

      For every value, there will be O(n+m) pareto points at max and when you choose a point, you will lead the opponent to a grid where this element won't exist again. So every state will be visited once (hence the lack of memoizing).

      So you just run the simulation with the revised set of points for each value. (Iterate over all points and check all winning/loosing states).

      The complexity will be O(l*(n+m))

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

        "choosing the index (p,q) will always leave you equal to or better off, than choosing the index (i,j)" can u prove this claim?

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

          So... think about it this way... take the cells A = (1,1) and B = (3,3). We want to prove that choosing B is always a better option.

          Say you won by choosing A. That means the opponent couldn't make a move in the grid starting at (2,2). But that means he would not have won if i had given him the grid (4,4) as well. (Which is choosing B).

          So essentially B is equally as better as A.

          Now say you chose A and lost. So the opponent was able to find a point C in the grid (2,2). But there are chances that he wouldn't have found this point C if you had chosen B, as the grid would then be further reduced.

          Essentially by choosing B, you are reducing the opponents possible moves while not affecting yours. I hope this helps. If not, try going thru the 1st para of E1's solution.

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

283532488 I was using simple approach of taking and not taking a string, the recursive code seemed to have worked fine and got tle on test 3 but when i memoized it the code gave wrong answer on test 2.

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

Can somebody help? Why won't my submission 285298474 work?