Read the checker's comment. It is said in the question to print those indices where heads will turn from R to L.

Check this Testcase:
6 6
RLRLRL

i did the same like chess...,but figured out the correct answer after the contest(same as editorial)..baaah!!.

But his Note for 1st test case is also confusing. where Black = 4 and white = 2. But he said B=3,W=2.

Consider n = 9

Of course, we first take all the prime number from 2 to 9 and 1 as well.

1 2 3 5 7

Hence, for k = 2 to 5, the minimal imperfection is 1 because the gcd is always 1.

For k = 6, we pick 4 so minimal imperfection is now 2.

For k = 7, we pick 6 so minimal imperfection is now 3.

For k = 8, we pick 9 so minimum imperfection is still 3.

For k = 9, we pick 8 so minimum imperfection is now 4.

In this example, it doesn't hold that we take the smallest composite number every time. Correct me if im wrong.

just declarate array before main and u will get AC.and if u will declarate it before main u not need to initialize array by zero

You are using i for iterating tests and rows both.

ok, my above answer is not correct. initializing array with ={0} is not correct, try initializing with ={} and it passes, 76027021

I believe = {0} syntax is only valid for statically allocated arrays. Though I cannot find a reference for this. It doesn't even compile on my GCC.

Using dynamic programming, you can calculate for each 'R' what the maximum number of moves it will take to get its position in the final array. Formula:

dp[cur 'R'] = max(dp[next 'R'] + 1,'L' cnt on [i + 1, ..., n]).

It only remains to note that for the strategy in the solution, this estimate is achieved.

1
2
-1 -1
-1 1

try this case.

The problem: Given the set of integers from $$$1$$$ to $$$n$$$, $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, find a set, $$$M$$$ of size $$$i$$$ such that max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is minimized.

The solution: Firstly, note that $$$1$$$ must always be included in the optimal set. Next, note that if there are $$$P$$$ primes from $$$[2..n]$$$, then max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is always $$$1$$$. Hence, for the first $$$P$$$ numbers, answer will always be $$$1$$$. Now from the $$$p+1$$$ th number onwards, if we include an integer $$$x$$$, the optimal set always contains at least $$$1$$$ divisor $$$d$$$ $$$(1\le d<x)$$$ of $$$x$$$. Why? Since we have already included all the primes from $$$[2..n]$$$, all the numbers we are left with are composite. Now if we add $$$x$$$ to the set $$$M$$$, max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is the largest divisor of $$$x$$$, since $$$\gcd (\texttt {largest divisor of } x, x) = \texttt {largest divisor of } x$$$. Hence, we have to add elements to set greedily such that the largest divisor of $$$x$$$ $$$\forall$$$ $$$x$$$ $$$\epsilon$$$ $$$M$$$ is minimized. For this, we can find out the largest divisor, $$$d$$$ $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, and store it in a list $$$v$$$. The answer is the sorted list $$$v$$$.

#include <bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

#define MS(x,a) memset((x), (a), sizeof(x))
#define F0R(i,n) for(auto (i) = 0; (i) < (n); (i)++)
#define FOR(i,a,b) for(auto (i) = (a); (i) <= (b); (i)++)
#define ROF(i,a,b) for(auto (i) = (a); (i) >= (b); (i)--)

using namespace std;

const int INF = 1e9+2;
const ll LINF = 1e18+2;
const int MX = 2e5+5;
const ll MOD = 1e9+7;

int lf(int n) {
    int ans = 1;
    for(int i = 2; i*i <= n; i++) {
        if(n%i == 0) {
            ans = max(ans,i);
            ans = max(ans,n/i);
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<int> oof(n); 
    oof[0] = 1;
    FOR(i,1,n-1) {
        int n2 = lf(i+1); 
        oof[i] = n2;
    }
    sort(all(oof));
    FOR(i,1,n-1) cout << oof[i] << " ";
}

Array a consists only of {-1, 0, 1}

array a can contain elements -1,0,1 only so your test case is incorrect

because in your output: BWB BBB there three B where a W is of them(2 in first row,1 in middle of second row).So B=3 here.Again a W has a adjacent B.So w=1.It doesn't maintain B=W+1.

Excellent explanation!

Dude... This is giving TLE..

I was getting TLE in Problem D, and I read "Change endl to \n " and I thought , "Well, sure OK! Why Not!" and it Passed (499ms).

Gotta say I'm Really Surprised how tight the time contraints are!

Anyways, Thanks !

There are 2 black cells with a border to the white one, and the one white one.

So B=2, W=1

B is not equal to total number of B. B is equal to total number off such B whice has a adjacent W. I hope you understand.

This solution is similar to the solution at editorial. So nlogn

Your code give 3 for this case, but it should give 2.

3
1 0 -1

In C we were asked to count number of subarrays that were good (i.e their subarrays must not have zero sum)

Now few observations before starting : 1. If a subarry is good that means all of 'its' subarrays are also good. 2. If a subarray is not good then all subarrays which will contain this subarray is also not good. example: 1 -1 3 4 now sum(1 -1) = 0 so it is a bad subarray so if you include (1 -1 3) this is also bad for same reason and so is (1 -1 3 4)

now main problem is to find subarrays with 0 sum in efficient manner for which we use idea of prefix sum. what we try to do is find sum of all elements coming before it. for example 1 2 3 4 is the array then it's prefix sum is 1 3 6 10. now we can say that there exist a subarray with 0 sum if : 1. prefix itself is 0. 2. prefix in some index is seen before.

let's say 1 2 -3 4 -1 it's prefix sum is 1 3 0 4 3 so there are two cases where subarray is 0 one is (1 2 -3) as prefix index was 0 here and second is (-3 4 -1) as prefix 3 in last index was seen before in 3rd index. we can use maps to find subarray with 0 sum to efficiently. Hope that helps.

Unordered set and unordered map use hashing, so if someone creates anti-hashing testcases ordered data structures are faster. In the worst case data structures that use hashing take O(N) complexity to access a element where N is the number of element in the data structure. Ordered data structures like set and map always have a O(logN) complexity. Use ordered data structures to decrease the risk of getting a TLE.

Sorry for my bad english.

can u explain your code

Got it.

Code in Spoiler, please?

0's should be excluded, so answer is 3

The editorials are already well descriptive.
You will cope with understanding them gradually.
Keep reading until you understand and seek for help if you need.
And be patient.

set dup is empty at the start of every iteration by i. Also you need to use long long instead of int.

I do some fixes. Check it https://mirror.codeforces.com/contest/1333/submission/76047566

here is an explanation, hope it will help you.

Take an NxM board, it is allowed to color a cell as black or white. If a black cell has atleast one adjacent white cell, lets increment variable B. Same holds for W.

The task asks to color such that, B = W + 1. Now, the immediate way that strikes is to color like a chess board. This has one corner case to handle: when value of NxM is even, then we have B == W. So, we have to color one more white spot as black, preferably the position: 0,0 [Since I've assumed coloring all odd sum cells as black. My soln. for reference: link

The editorial provides a much simpler implementation, as in, color only the top-left cell as white and the rest as black. Why is this correct? Well, we have W = 1, since there's only one white cell, also, it has 2 neighboring black cells. We also have B = 2 always, this is because only two cells: (0,1) and (1,0) have neighboring white cell (other blacks only have black neighbors). Thus, the constraint: W = B + 1, always holds. I would recommend visualising/drawing out and seeing.

Bonus: As the editorial mentions, the problem gets a little tricky if 1 <= N,M! I realised why only after typing out this explanation.

You can check my solution here

Do you know the asymptotics of your solution (without sorting)? Its look like n*e operation so O(n), but I'm not sure.

Yes, I also solved for O(n). Here is my C++ solution: https://mirror.codeforces.com/contest/1333/submission/75888071

Thank you! Fixed.

just a simple thing you have to maintain prefix array and then if any value repeats that show that the sum of elements including this indices is zero than you can easily calculate how much subarrays contains this subarrays after counting all subarrays which contain subarray with sum=0 subtract it from total number of subarrays that can be found by n*(n+1)/2

this code can be done in O(n). you don't need to actually change the value in first array you can just check is it possible to make it equal to value at same index in second array

https://mirror.codeforces.com/contest/1333/submission/76229807 I have made some modifications to your code. 1) The first change is this if(a[i]==b[i] || (b[i]>0 && m[1]>0) || (b[i]<0 && m[-1]>0)) Because you want to convert a[i] to b[i], So comparing them is more intuitive. The second change is in for loop for(int i=n-1;i>=0;i--). Hope it helps ;)

You have to use "\n" instead of endl.

hey ... in your submission .... can you pls explain these lines: else { if(ind1<ma[sum[ind2]]+2) ind1=ma[sum[ind2]]+2; if(ind1>ind2) { ma[sum[ind2]]=ind2; ind2++; continue; } ans+=ind2-ind1+1; ma[sum[ind2]]=ind2; } i hope you will answer.... badly in need of that