Why?

That's cool.

Thanks Mate

Because if n>60 , We can always find a contiguous triplet (a,b,c) such that a > b^c.

to avoid the case of having 3 or more consecutive numbers with the same heighest set bit equal the array length have to be <=60 because we have 30 bits to represent the numbers and 2 consecutive numbers with the same highest set bit is allowed then 2 * 30 = 60 — max array length

now imagine that we have such array and we want insert a new number X be aware that the array has to be in non-decreasing order and we have consecutive segment of the array like the following

a, b, c, d "without loss of generaility for the specific heighest set bit"

a highest set bit is the 3rd bit

b and c both have the same highest set bit which is the 4th bit

d highest set bit is the fifth bit

X has the the 4th bit as the heighest set bit so X have to be placed before d and after a which mean a, b and x have to be consecutive.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

So when value of n is 10^5 then no. of test cases will definitely be 1. When test cases are 10^4, then value of n in all test cases are such that their sum will be atmost 10^5.

There is a statement, "Sum of $$$n$$$ over all test cases doesn't exeeds $$$10^5$$$". That basically means $$$t*n<=10^5$$$. So, overall operations doesn't exeed $$$100*10^5=10^7$$$ which is acceptable in the given time limit.

For n <= 1e9, There can be atmost two numbers having same most significant bit. Therefore the bound will be atmost twice the number of bits i.e. 2 * log2(1e9) which is 60.

Jurys anser is 1 1 2 0 1 0 and yours is 1 2 3 0 1 0

abs(a — b) + abs(c — d) is not equal to abs((a+c) — (b+d)).They both are different.

find abs of (row) and col seperate for all four corner

int ans=Math.max(row-1+col-1, Math.abs(n-row)+Math.abs(m-col));

       ans=Math.max(ans, row-1+Math.abs(m-col));
       ans=Math.max(ans, col-1+Math.abs(n-row));

how to solve div1D in $$$O(N)$$$ ?

For example, assume you have segment $$$(10, 20)$$$ and you set your number $$$011??$$$, your number will be in the segment whatever you set two lowest bits, then they are free.

Here x is 11, which is the time required to add a platform.

This is your test case:

n = 2, p = 2, k = 1; s = "10"; x = 11, y = 1.

x is the cost of adding a platform, y is the cost of removing the first cell. In your case, there is only 1 option: that is to add a platform at position 2, giving 11 as your answer.

Ya! Exactly. I too think it's a typo.

Thanks, corrected! I missed "more than".

You are essentially keeping a separate index list for each possible color. The total houses is N, so the total entries in all index lists sum up to N.

yeah, it should not be. I mean we don't require any extra space. https://codeforces.com/contest/1457/submission/99854109

The only space that is variable with input is the array used to store doors colors.

nothing else will change with the input.

https://codeforces.com/blog/entry/85081#comment-727466

I will explain more the 4 and 5 hints. - Given that the first cell on which the ball will land is cell i, we know it will visit cell i, i+k, i+2k, ... , i+xk<n, right! so we want to count how many index j in {i, i+k, i+2k, ..., i+xk<n} such that s[i] = '0'. In other words, we need to how many cell in the group of cells the ball will visit, does not have a platform. we will of course need to put a platform in each one of them. we have no choice.

• Let cnt[i] denote the min number of platforms we must add if the ball starts the journey at index i.

• Let's consider the bruteforce first. It's a simple for loop.

we simply iterate over indecies i, i+k, i+2k, ... and if no platform we increment a counter. right!

for (int i = p; i < n; ++i) {
  for (int j = i; j < n; j += k ) {
      if (s[j] == '0') cnt[i]++; 
  }
}

• In the previous code, we calculated cnt[i] for every index we are interested in.
• This code is O(n^2)

• Now, we need to optimize this code using DP

• to do that, you need to realize the recursive nature of cnt[i].
• cnt[i] clearly depends of cnt[i+k]

cnt[i] = (s[i] == '0' ? 1 : 0 ) + cnt[i+k]
// it means that number of platforms to add if ball starts at i is equal to number of balls to add if ball starts at i+k, plus 1 if cell i also needs a platform. 

• Now, we can write a recursive code.

int cnt(int i) {
    if (i>=n) return 0; 
    if (s[i] == '0') return cnt[i+k] + 1;  
    else return cnt[i+k]; 
}
int mem[n] = {};
for (int l=p; l<n; ++l) 
   mem[l] = cnt(l);

• Now, It should very clear how dp or memoization should be used. we are simply calling the function cnt(l) for n-p times and in each call, it will need about (n-l) / k call. but the function has only 1 parameter with at most n values. so, there must be repetitive calls. use memoization. I hope it's clear now.

int mem[n]; 
int cnt(int i) {
    if (i>=n) return 0; 
    int &ret = mem[i]; 
    if (~ret) return ret; 
    if (s[i] == '0') return ret = cnt[i+k] + 1;  
    else return ret = cnt[i+k]; 
}


for (int l=p; l<n; ++l) 
   cnt(l);

Fixed, some testers' solution got hacked too.

I bet 1800

$$$K$$$ means a range that must be consecutive.

So in the test,you can choose [1,6] or [2,7] or [3,8] or [4,9] to change the color.

bro because we can choose from i to i+k-1 element and we should not choose 1 in them because they r of same colour before itself so 2 days required