**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 51;
int n, m;
int a[N][N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n >> m;
set< int > r, c;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> a[i][j];
if(a[i][j] == 1)
r.insert(i), c.insert(j);
}
}
int mn = min(n — r.size(), m — c.size());
if(mn % 2)
cout << "Ashish" << endl;
else
cout << "Vivek" << endl;
}
return 0;
}
```

This problem was prepared by Ashishgup

1365B - Проблематичная сортировка

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e3 + 5;
int n;
int a[N], b[N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n;
bool sorted = 1, have0 = 0, have1 = 0;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
if(i >= 2 && a[i] < a[i - 1])
sorted = 0;
}
for(int i = 1; i <= n; i++)
{
cin >> b[i];
if(!b[i])
have0 = 1;
else
have1 = 1;
}
if(have0 && have1)
cout << "Yes" << endl;
else if(sorted)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
```

This problem was prepared by Ashishgup

1365C - Соответствия поворотом

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 2e5 + 5;
int n;
int a[N], b[N], pos[N];
map< int, int > offset;
int32_t main()
{
IOS;
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
pos[a[i]] = i;
}
for(int i = 1; i <= n; i++)
cin >> b[i];
for(int i = 1; i <= n; i++)
{
int cur = pos[b[i]] - i;
if(cur < 0)
cur += n;
offset[cur]++;
}
int ans = 0;
for(auto &it:offset)
ans = max(ans, it.second);
cout << ans;
return 0;
}
```

This problem was prepared by Ashishgup and ridbit10

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 55;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
ll res = 1;
x %= mod;
while (n) {
if (n & 1)
res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
ll n, m;
char arr[N][N];
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool valid(ll i, ll j) { return i >= 1 && i <= n && j >= 1 && j <= m; }
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t--) {
cin >> n >> m;
for (ll i = 1; i <= n; i++) {
cin >> (arr[i] + 1);
}
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
if (arr[i][j] == 'B') {
for (ll k = 0; k < 4; k++) {
ll ni = i + dir[k][0];
ll nj = j + dir[k][1];
if (valid(ni, nj) && arr[ni][nj] == '.')
arr[ni][nj] = '#';
}
}
}
}
queue> que;
bool visited[n + 5][m + 5];
memset(visited, false, sizeof(visited));
if (arr[n][m] == '.') {
que.push({n, m});
visited[n][m] = true;
}
while (!que.empty()) {
pair curr = que.front();
que.pop();
for (ll k = 0; k < 4; k++) {
ll ni = curr.first + dir[k][0];
ll nj = curr.second + dir[k][1];
if (valid(ni, nj) && !visited[ni][nj] && arr[ni][nj] != '#') {
que.push({ni, nj});
visited[ni][nj] = true;
}
}
}
bool good = true;
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
if ((arr[i][j] == 'G' && !visited[i][j]) or
(arr[i][j] == 'B' && visited[i][j])) {
good = false;
break;
}
}
}
cout << (good ? "Yes" : "No") << en;
}
return 0;
}
```

This problem was prepared by Vivek1998299

1365E - Максимальное значение подпоследовательности

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 505;
int n;
int a[N];
int32_t main()
{
IOS;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = i; j <= n; j++)
for(int k = j; k <= n; k++)
ans = max(ans, (a[i] | a[j] | a[k]));
cout << ans;
return 0;
}
```

This problem was prepared by Ashishgup and ridbit10

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tc;
cin >> tc;
while(tc--){
int n;
cin >> n;
map< pair < int, int >, int > pairs;
vector< int > a(n), b(n);
bool possible = 1;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
cin >> b[i];
if(n % 2 == 1 && a[n / 2] != b[n / 2])
possible = 0;
for(int i = 0; i < n / 2; i++){
pair< int, int > p = {min(a[i], a[n — 1 — i]), max(a[i], a[n — 1 — i])};
pairs[p]++;
}
for(int i = 0; i < n / 2; i++){
pair< int, int > p = {min(b[i], b[n — 1 — i]), max(b[i], b[n — 1 — i])};
if(pairs[p] <= 0)
possible = 0;
pairs[p]--;
}
if(possible)
cout << "Yes" << endl;
else cout << "No" << endl;
}
}
```

This problem was prepared by FastestFinger, Ashishgup and Vivek1998299

**Tutorial**

Tutorial is loading...

**Code**

```
#include
using namespace std;
#define ll long long
#define vint vector< int >
const int Q = 13;
ll query(vint v){
cout << "? " << v.size() << ' ';
for(ll i : v)
cout << i + 1 << ' ';
cout << endl;
fflush(stdout);
ll or_value;
cin >> or_value;
return or_value;
}
int main(){
int n;
cin >> n;
vector< vint > ask(Q);
vint assign_mask(n);
vector< ll > or_value(Q), answer(n);
int assigned = 0;
for(int i = 1; i < (1 << Q); i++){
if(__builtin_popcount(i) != Q / 2)
continue;
assign_mask[assigned] = i;
for(int j = 0; j < Q; j++)
if((i >> j & 1) == 0)
ask[j].push_back(assigned);
assigned++;
if(assigned == n)
break;
}
for(int i = 0; i < Q; i++)
if(!ask[i].empty())
or_value[i] = query(ask[i]);
for(int i = 0; i < n; i++)
for(int j = 0; j < Q; j++)
if(assign_mask[i] >> j & 1)
answer[i] |= or_value[j];
cout << "! ";
for(ll i : answer)
cout << i << ' ';
cout << endl;
}
```

This problem was prepared by FastestFinger

..

I don't know what is the point of making A is the hardest problem !

UPD:after reading the editorial , problem A is easy but I understood it wrongI think A is simple, I misunderstood the statement, and I thought cells that share sides, and it was cell that share columns or rows

(I assumed something that was not in the statement and that is my fault)Yeah,me too.And during the contest I felt stupid enough to come up with an approach for D and not A

Can anyone solve this if we consider this variant of problem?

It seems to be quite interesting one.

deleted.

I calculated a few Grundy numbers for small cases. Maybe someone can see some pattern in them.

Table of Grundy numbersCodeI did the same mistake, misread the statement

me too!!!

I also assumed the same , and could not solve the problem A due to that .

me too

I also did the same

I just ORed each row and column anc got count of 0's in each Now if mincount of 0's among those two is odd then Ashish wins otherwise Vivek

I too solved B, C and D and wasn't able to solve A :(

It wasn't that hard, you just had to determine the number of totally unassigned rows and columns. Take the minimum of them. Ans by checking the number even of odd.

Thanks for easy explanation...

Welcome

What if both unassigned rows and columns are equal?how to find min of them

Then take any of them

There is a brute force O(n^3) solution too. Whenever you find zeros, traverse that particular row and column to check if there are no ones. In that case, increase the counter and set that particular a[i][j] to 1. At the end, if the counter is odd Ashish wins, else Vivek wins

yeah, I thought that the question was talking about boundary of claimed cells

same here buddy

Video Tutorial of A,B,C,D,E

Wow, that was fast.

Next Time, editorials before contest!

Good round! Thanks for fast editorial

Amazing contest! Had fun solving the problems ^_^

FastestFinger fastest editorial <3

He is FastestEditorial

It says tutorial is not available. Anyone else having same problem ?

UPD : It's working now

Yes

Maybe come later

The tutorial isn't out yet I guess. Only the solutions are available at the moment.

One of the fastest editorial I'd say :-)

Hardest A ever seen.

You should look at round 646 A. So many corner cases!

is it in russian?

I was so tired and sleepy that I read it as is it rated?

Had 15min left for round so didn't try E and now I see this

Ah!! I thought I am the only one who missed E thinking won't be able to solve and code it in 15 min.

How is the solution to E is easier than the problem itself?

You understand me bro !!

i had 28 mins :( as i have never solved E in contest i just went to sleep

Can't believe an O(n^3) solution with n = 500 gets AC with Python. Just didn't attempt thinking it'll get a TLE.

Yeah, it's nearly on edge, it took 1591ms !

.

i am no better than you. but we all have bad days and also good days. just don't give up!

It's fine. I also couldn't solve A,B,C during contest time. Be happy that, in this editorial you can learn something new more than those contest where you could solve more problems.

Exaxtly.we are not supposed to give up.

I also can't solve any question in the contest. Some times its looks like I don't know anything. But it ok to take time to learn new concept. Coding needs much practice. Worst part of coding is to find your error in your code.

Never loose hope. One day you will.

And hence as a result, always stay beginners.

I feel so stupid after reading the editorial for problem B

This is the best code I've seen for B so far.

Fortunately, I did the exact same thing for B :)

I have the same feelings but for E

Me too bro

Didn't know that type is attached to the index and not to the value. Was swapping type also with the elements.

those were some really interesting problems tbh rather than pure bash it's observation only (except D but that was fun too)

For C, isn't the time complexity still

`O(n)`

if you use a HashMap?Since we only need to consider shifts by 0,...,n-1, I think we should even be able to use an array/vector for the counting (but I used std::map in my solution during the contest).

Edit: Yep, works (82880486). But doesn't seem to help much, only makes it run in 514ms instead of 608ms.

Here is my solution using map and array, It made a huge difference in my case.

Using Map (514 ms)

Using Array (139 ms)

P.S :- I submitted both accepted solutions during the contest so my previous solution (using map) got skipped

Well your improvement is a lot larger because you had used maps for inverting the permutations as well (mp1 and mp2), whereas I only used one to count the differences. Also, I just did some tests, and it seems like my array-solution was so much slower than yours just because of the missing "ios_base::sync_with_stdio(false);" — guess that's not so useless after all xD

yes

Map works for O(logn) It is optimized binary search tree

But HashMap (unordered_map in C++) has O(1) time complexity for adding and removing (with a high constant factor though)

i tried bubble sort in B when condition satissfies that is when A(i) >A(J) AND B(i)!=B(j) then swap it.And at last checked if its sorted or not? why its giving WA

Link your submission

Read the question carefully. It is not bubble sort but you can switch any two numbers if their type is different. I made the same mistake.

4 3 2 1 ``

1 1 1 0

`` try bubble sort on this

thank you got it

no problem :)

Hey giorgitarkh, Can you please help debug my code? I think you will get the logic when you read the code. 82855417

Thanks in advance :)

imagine

`` 5 7 4

1 0 0 ``

with your logic there will never be a swap, your logic implies that only neighbors can be swapped, but in the problem if two indexes have different b, you can swap them, so your solution won't check the case when you can swap 5 with 4, swapping b would work if you had swapped 5 with 4, then the state would become

`` 4 7 5

0 0 1 ``

and then you would've swapped 7 with 5, but I think that kind of solution would be n^3 or maybe n^2 if optimized with some algorithm not sure

oh yeah! got it , thanks a lot

Try

1

3

2 1 1

0 1 0

try this test case:

1

3

3 1 2

0 1 0

ans should be "YES". :)

because that doesn’t work. Check this input: 4

1 3 5 4

0 1 1 1

Your solution will result in No. But it can be sorted

can you explain this example , How it can be sorted?

Sure. First swap 4 with 1 Then it will look like this 4 3 5 1 Then 1 with 5 4 3 1 5 Then 4 with 1 1 3 4 5

Because you can't be sure that in single bubble sort you get the answer. I mean it is possible that when you are applying bubble sort and then checking whether the array is sorted or not and it gives not sorted, then also it is possible that if you apply bubble sort again by the method which you specified, it becomes sorted So exactly dont know how many times you have to apply bubble sort. That,s why you require some other approach for solving this

For wrong answer on E, try this ->

2 12 6. I got it after the contest :(Can you please find out the error in my code : https://codeforces.com/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<<i) to my ans.

I thought we could only switch adjacent numbers in B..

wasted my 1 try thinking this.then read the statement carefully xD

Damn I feel so stupid after seeing E's solution

What is __builtin_popcount?

This gives total number of set bit in binary representation of number

it is an in built function which is used to count setbits

Nice contest! Didn't quite get understand the proof for E while doing the contest, but proof by example and proof by AC is good enough for me :)

Can you explain the proof you got?

Proof by example means I just came up with examples I solved manually. This is not a rigorous way to prove things.

Proof by AC means I coded a solution I think might work and tried to see if CodeForces would accept it. This is actually not a real way to test if your code works.

Where are the memes

To me A was harder than B.

Don't read stroyI skipped A and solved B quite easily. Again read C, skipped and tried D. Couldn't prove the idea (same as editorial), and again focused on A. I again tried to prove D. When 14-15 min was left I coded D without proving. Finished 20 sec after the contest. Anyways, I don't know why I am commenting...

Thanks for nice problems. Though I couldn't solve A,B,C during contest time, I am still happy. Cause Now I know what I should know that I don't know.

D was fun to solve.

I am getting a RTE in problem D. My logic is the same as that used in the editorial. Can someone please help me in debugging: Link : https://codeforces.com/contest/1365/submission/82791264

You must check for every index to be valid i.e, after you do this--> int xx = i + x[k]; int yy = j + y[k]; you must check xx>=1 && xx<=n && yy>=1 && yy<=m Also you have provided the wrong link for the solution ;p

Hey, Thanks for the help, but it did not work Link : https://codeforces.com/contest/1365/submission/83055198 Because anyways i'm using 1 based indexing and the remaining cells are always filled by walls(the ones outside m*n matrix) so this condition xx>=1 && xx<=n && yy>=1 && yy<=m anyways gets checked in the base case of the check(dfs) function!

Your check function is in infinite loop. Try this case:

1 2 3 BBB GG.

Thanks!! I figured out the problem.

No relevant memes this time? We need TheOneYouWant as Co-Author from next time ig.

Did you mean TheMemeYouWant?

can any one explain problem (E. Maximum Subsequence Value not the solution just the statments.

Here, if we OR the elements, then we'll get all the set bits, but we need to get the bits that are in at least k-2 elements in a subseq of size k(k>3 else 1) so when we go throught the binary repr of the numbers, we find out that not all bits are contributing towards max (cases with dense set bits is exception to this obsv) but when we decrease the size of the array (ie get a subseq), our k-2 decreases and narrowing down to large numbers while also aiming to make it denser(ie in [1,2,4,8,10], 10,1,4 cover all bits), our value increases. So, how long do we need to decrease this subseq size, that goes down to that atleast max(1,k-2) must be set, therefore for k<=3, we have that any set bit contributes and at k=3 our subseq size is max.

example: [2,4,8,16,32,64] => [16,32,64] 112

[1,2,4,8,10] => [10,1,4] 15

Thank you so much

Can someone tell me why my E fails? Feels like I've done the same thing

Code

what if biggest number shouldn't be in the solution, for example 11000000 is the biggest, but it would be better to use 10011111, you always use the biggest number in your solution.

Thanks, I feel extremely stupid rn

no problem.

You are doing a greedy solution. It's not always correct to select in this way.

For example, consider the following test case (all numbers in binary)

The optimal solution selects rows 2, 3, 4. Yours selects row 1, 3 and 4.

This was completely Mathforces!

I wish!

Felt more like Thinkforces than Mathforces, nice easy implementations after you get the logic, but not that much Math.

Thinking is mathematics. Olympiad combinatorics is mainly "thinkforces". Also, problem F was finding a strong invariant in the process.

Most probably I will be losing my rating in this Contest. But No worries, the questions were too good [Especially the E qn]. I definitely want Ashishgup to host contests more frequently.

Great contest with problems that focus on elegant observations. Look forward to more such!

Great contest and hands down the hardest A and B i have seen in a long long time.

Has the record for fastest editorial ever been broken?

As a low rated coder I enjoyed it too, thanks!

Can anyone explain why my solution for D failed? First, I checked if any B has G as a neighbor or not. Then, I replaced all empty spots around B as walls. Then I ran a dfs from the right-bottom. https://codeforces.com/contest/1365/submission/82867892 Thanks.

In your dfs code why are you moving left and top only?

1

5 5

G . . . .

G . . . .

# # G # .

B B # # .

B B B # .

I love how you separated the editorial into key idea and solution so people have a second shot at upsolving without looking at the solution

My idea for the solution to D is check if the bad guys can reach the end, if yes, then block all the neighbouring cells. Then check if all good guys can reach the end. Why does this fail on pretest 7?

Link to my submission : https://codeforces.com/contest/1365/submission/82872417

B and G are next to each other is auto fail, since B can just hop onto whatever path G is on

I have included that condition also

if B and B are next to each other, u can't block off the adj B cell

if not that then idk what other edge cases there are

Yeah, my solution fails for that case. I am blocking off any adjacent cell which is not a wall. Thanks for replying.

You have a typo, when you are checking for s[i][j-1]=='G', you are actually checking if i-1>0, and the same typo when checking for '#'

Thanks for pointing it out. This is the punishment for copy pasting without checking properly

Having a row and col array really makes the code a lot less messy and easy to debug

Check out my submission link

Yeah that makes a lot of sense. I'll try to do that from the next time. Thank you!

I actually used a similar approach in the contest but I'm getting TLE on test case 16. Here's my code:82884958. Don't know what's wrong in it.

Yeah after correcting the typo, my code also TLE's. So instead of checking if every good guy can reach the end, check if you can reach every good guy from the end. This requires only one traversal whereas the first approach requires one traversal for every good guy.

If you want to look at the code: https://codeforces.com/contest/1365/submission/82879263

Thanks for the help!

You have a typing mistake in 1st and 2nd for loops 4th if condition.

`if(i-1>=0 && s[i][j-1] != '#')`

is definitely wrong. Other than this it looks ok, Even though you could've optimized your code A LOT. For example,SpoilerI tried the exact same solution and have put in the exact same conditions, but still, I failed on pretest 4.

https://codeforces.com/contest/1365/submission/82867892

Yeah, I copy pasted that part without checking properly. And thanks for the tips. I'll keep that in mind from the next time.

[deleted]

Why the editorial solution only checks for

`maze[n][m] == '.'`

before enqueue? Shouldn't be`!= '#'`

?I think it doesn't matter. As long as you have the escape cell empty, you can reach every good guy if it's possible with only one cell in the queue initially.

That's the point. He just adds the scape cell, but only if it is empty. So if there's a good guy on the scape cell, the code doesn't even run the BFS

It is mentioned in the problem that the escape cell is empty. So unless you build a wall there in which case nobody can escape, the escape cell is empty.

Thanks, didn't notice!

The intended solution to problem G is pretty. Unfortunately for me, the solution I found was much uglier, and was a slight modification of the binary search idea.

Given two integers $$$i \neq j$$$, either there is a bit set in $$$j$$$ which is not set in $$$i$$$, or $$$\mathrm{popcnt}(i) > \mathrm{popcnt}(j)$$$ (where $$$\mathrm{popcnt}(k)$$$ is the number of bits set in $$$k$$$), in which case there is some bit un-set in $$$\mathrm{popcnt}(j)$$$ which is set in $$$\mathrm{popcnt}(i)$$$. Applying this directly would require 10 queries that examine values of $$$i$$$ with various set bits, and 4 queries that examine values of $$$i$$$ with various unset bits in $$$\mathrm{popcnt}(i)$$$, which doesn't quite fit within the bounds of the problem. But there are enough 10-bit values of $$$j$$$ with $$$2 \leq \mathrm{popcnt}(j) < 10$$$ (to enable using only 3 queries based on $$$\mathrm{popcnt}(j)$$$) to barely nudge this idea across the finish line by first mapping into that pool of values.

EDIT: Now that systests are over, I was able to produce a submission demonstrating this approach. (82885957)

After reading the editorials for all problems that I tried solving but could not solve, I am feeling dumb for not thinking the way it is mentioned in the editorial. SMH

Oh my god, I feel so stupid. I got the observation for E, but for some reason I thought n^3 was too slow. I spent almost an hour trying to figure out how you can know which 3 give the largest value. Well, at least I won't make this mistake next time (hopefully).

Other than that, I really liked the contest. Fun problems.

I'm still stuck at the point where I can't reach why a subset of 3 is enough. Can you help with a better explanation?

Let's say we have a subset with more than 3. We can call the numbers in the subset a1, a2, a3, ..., an. The value of the subset is the sum of all the bits present in at least k-2 of the ai. But, if a bit is in k-2 of them, it must be present in at least one of a1, a2, a3. If it wasn't, we'd have at most k-3 ai with that bit. This means: any bit which contributes to the value of a1, a2, ..., an, also contributes to the value of a1, a2, a3. So in fact, the value of a1, a2, a3 is at least as large as the value of the whole subset. Thus you can always reduce the subset to one of size 3.

My performance timelapse: Link. Hope you enjoy :)

Problem D video editorial: sOlUtiOn

We all should appreciate them for this quick editorial

consider for question A, m =5 and n =2 and filled with all 0s. min(m,n) is 2, so as per question Vivek should win. but, actually ashish will win this.

first step,ashish,

row 1 :1 0 0 0 0,

row 2 :0 0 0 0 0

second step,vivek,

row 1 :1 1 0 0 0,

row 2 :0 0 0 0 0

3rd step ,ashish,

row 1 :1 1 1 0 0,

row 2 :0 0 0 0 0

4th step vivek,

row 1 :1 1 1 1 0,

row 2 :0 0 0 0 0

5 th step ashish,

row 1 :1 1 1 1 0,

row 2 :0 0 0 0 1

The question said row or column. so, this must be optimum, just a doubt,please clear

if n = 2 and m = 5, it should look like this

Ashish can pick any position

Now Vivek has the option of picking in the bottom row except the first column. So,

Now, Ashish has no options. So, Vivek wins.

Here it's clearly written that no row or column should be picked by anyone if already have 1 in any cell. So your approach is not following the given constraint . Please read it carefully, I think you misinterpret .

i got my mistake, i misinterpreted the question and wasted 1 hour thinking why i am getting wrong ans.thank you i considered if either row or column is not filled ,u can consider it

Can any one explain E ? As i not understand why can not we xor of all element . I think it will automatically fetch all max ? But as here is condition that you need at least k-2 element with bit 1 in binary representation. So any other proof which gives this answer.?

Saw E thought it would be much harder and tried D and now I am here crying.

Really it's looks easy but for that you need one tick which is 3 in mind . Bro don't worry . But if you had solved D then you are awesome.

I felt like dumb.. even though it's stupid for me to think so but I am glad others found A and B hard..

Nice problemset. Anybody else know where can I practice such bit manipulation problems?

Ashishgup is the hardest problemsetter for me till date. It's a given now..

I want to know what is the story behind FastestFinger's handle

how to solve A if cell having common edge with claimed one are not to be taken ??

Gotta be careful with these maps.

One map is sufficient.

F is a truly beautiful problem. Love this kind of problems where you don't have to even know some complex data structures or algorithms. Even someone inexperienced with deep insight could solve it and the solution is brilliant. This contest once again reminded me that solutions themselves can sometimes be the simplest (as in E and F).

Feeling very dumb of me, right now. I got to the intended

`O(n^3)`

solution of Problem-E. But, thought, it would give TLE (So dumb of me) and so, tried a greedy approach to solve it, but was't able to pass the pretests! :(Problems were too amazing. You just get the basic approach, and that's it! No heavy implementation. (Except D, but that was fun too).

Thanks to the authors.

Awaiting more such rounds on CF.

Feeling sad for E

Yeah,I'm still wondering how an n^3 solution works for n=500. I thought that 10^6 iterations meant one second of runtime and that this would overshoot it by a lot. Ended up selecting the max everytime and iterating over the other n^2 possible pairs.:(

A good rule of thumb is 4 * 10^8 easy operations (nothing like mods or pows) will take 1 second.

Most CPU can run at 3GHz-4GHz (There's 3e9-4e9 Clock Cycle Time in a second). Different operation will cost different Clock Cycle Time: add, minus, multiply, bitwise operation usually cost 1-3 Clock Cycle Time while divide cost more than 10 Clock Cycle Time. If data is at RAM, read and write will cost about 100 Clock Cycle Time. If data is at CPU cache, read and write will cost only 1-10 Clock Cycle Time. Most CPU have a 4-16Mb L3 cache, so our program which use little consequent memory will run rather quickly, especially DP. And there's many other optimization such like out-of-order execution.

For ordered pairs, $$$C_{500}^3 = 2e7$$$. Our program use about 500*sizeof(int)=2-4kb memory, this is very small. Our array will be placed at CPU L1/L2 Cache entirely and has a very fast read write speed. Suppose read and write use 3 cycles, bitwise operation use 1 cycle, our program will cost about 2e7*3/4e9 = 0.015s.

You can use these rule to evaluate time usage of your code.

Does the placement of running program in L1/L2/L3 cache or RAM depends entirely on the size of the program or are there any other factors too, as you indicated that the program(2-4kb) is small enough to be placed in L1/L2 cache?

https://stackoverflow.com/questions/763262/how-does-one-write-code-that-best-utilizes-the-cpu-cache-to-improve-performance

What should be the difficulty of B?

today i face very unique problem during contest on problem D . I run same code on 3 different ide and i get 3 different output on each ide for first test case. anyone know how it is possible? https://codeforces.com/contest/1365/submission/82870625

Your use of memset is wrong, the second and third parameter switched. Such things happen much less often if using vector instead of arrays.

thanks

can some one tell test case where my solution of problem D fails . I solved for finding the path recursively instead of bfs .submission

In your main method, you have a condition

It should've been j+1 < m

Ok. nvm .You were storing the values from 1 to n instead of 0 to n-1. My bad.

I have used 1 based indexing.

Your code will fail the consecutive Bad guy case. For example,

https://codeforces.com/problemset/problem/1174/B B was the same problem as above with just a slight change in statement, now i see why practice helps.

In B, I considered

swapping only adjacent elementswith given properties. That was SAD!!!I feel you. Spoiled my whole time because of that.

sadCan anyone tell me what is wronge with my code Trouble Sort https://codeforces.com/contest/1365/submission/82849016

consider

1 3 4 2

0 1 1 1

Thanks for replying Having at least one element of each group is the only condition for above problem?

Tricked me in E. If problem E was placed at C, I would have solved it. Regret missing on such a simple logic.

Yes! I realised that you don't need more than three elements and I noticed that $$$O(N^3)$$$ would pass, but somehow I just didn't think of checking all triples...

Who knew the correct solution to problem

Ecould be a simple brute force?..Could you help me with my logic, I have posted my doubt below...

Haha. Same Happened with me. I was trying to solve E in O(N^2). Finally managed to solve it(after the question). Link to my solution: 82882054

Where are the memes?

Easiest Div2E I have ever seen. For me it was simpler than all other problems in this contest.

Great editorial !!**I think Every editorial must contain Key Idea.so that we can proceed by ourselves**

this was an unfair contest question F was easier compared to earlier questions

Could anybody please explain me why in Div .2 B array can always sorted if 0 type and 1 type is present

Suppose you want to swap positions

`i`

and`j`

where`b_i = b_j = 1`

. Now suppose there is some index`k`

such that`b_k = 0`

. The following sequence of swaps will do the job —`(i, k), (i, j), (j, k)`

.I can't think how my E failed , I just grouped and sorted numbers by the last set bit and took the or of three largest numbers in the top 3 bits...should not it be correct

Try this case.

`4`

`34 33 8 14`

The optimal solution is

`59`

, here (`33 | 8 | 14`

)But, your solution will give

`51`

.No. Consider the following case:

Array is: [1,2,6,8]

According to you, the output should be 8|6|2 = 14.

But the answer is: 8|6|1 = 15

There are two problems —

1) Your code doesn't follow your logic exactly. I think you have made a typo in "sort(all(lb))". It should be "sort(all(lb[i]))".

2) Your logic will give wrong answer for the following test case.

4

12 4 2 1

According to your logic, you will pick (12, 4, 2) while the optimal choice is (12, 2, 1).

Consider these 4 numbers

11100 1100 100 11

Your code will ignore '11' but that's not the optimal solution

Very nice problemset, not as a CP contest, but they are very beautiful indeed.

https://codeforces.com/contest/1365/submission/82842665

what is the use of function check() and asdasd() in this solution for E.

Can someone help me in my code why i am getting runtime error on one particular line https://codeforces.com/contest/1365/submission/82879289

fuuuuuuuuuuuuu,.... , this C , damn itttt.

I solved the Problem D using DP. At first I make all the side of bad person("B") to "#"(except if the side has a bad person("B")).After that I will make all the remaining "B" to "#".So I get rid of that "B". Check that if we made the (n,m) cell to "#" then the answer is "No". Otherwise we now backtrack from (n,m) cell to all the possible direction cell we can go.As we can go to same cell many times so we will save that information in an array.If we visit that cell make dp[i][j]= true otherwise false.Beside that If we get a good person("G") through backtracking, we will save that. After backtracking we now check how many good person we get through backtracking.If the number is the same as all the good person then our ans is "Yes" otherwise "No". My code is here:82880358

thats not dp, thats bfs, i did the same thing as you.

If someone can really tell me why is this runtime error on Test Case 28 ! I will be thankful

HERE

If you scored less points for problem d than for c....... Welcome to the club.....

Hey guys, I am new at CP. So I am quite confused. The "game" tag for A is it because A is a game theory problem? I solved A using brute force and it passed successfully. But I am in doubt. Is A game theory problem?

I think it has game tag because the question is who will win or lose.

G is brilliant! Looked impossible at first.

Miss the memetorials.

How to solve problem C ,if we have repeated elements in array a and b?

In A, Dry running the editorial code should return "Ashish" for this test case, but the answer given is "Vivek". Here mn = min(5-1,10-1) = 4 (which is even, should return "Ashish"), or am I making some mistake?

Hey, if

`mn`

is even, then`Vivek`

is the one, who wins the game and not`Ashish`

.The answer is "Vivek".

sorry, my mistake (sleepy)

Amazing problems! $$$G$$$ is really nice and unique.

BTW problem $$$F$$$ in

OEIS— https://oeis.org/A037223If the given numbers are unique that is, assume $$$A$$$ is a $$$[1..N]$$$ and $$$B$$$ is a permutation of $$$A$$$. But it can be easily generalized to something like this:

Video Tutorial for problems A,B,C,D,E

Can someone suggest what changes I can make to my submission D in python (I used pypy compiler), it gives TLE for test 13. I have implemented the same as editorial to my knowledge. https://codeforces.com/contest/1365/submission/82883245

You are applying dfs from every good vertex. worst case it would take >1 second.

What you can do is just do a single dfs from n,m and then check if every good vertex is visited and bad isn't like stated in the editorial

Why were the constraints for f so low ? Given that we can solve in nlogn ?

500 Cases

Would be awesome if someone can let me know why my same exact idea/concept TLEs when implemented in DFS but somehow passed in BFS :/ https://codeforces.com/contest/1365/submission/82870178 https://codeforces.com/contest/1365/submission/82883583

wtf... when I moved the graph/2d array to be a global variable rather then being passed through recursion, it passed :/

Can someone explain why ? :(

https://codeforces.com/contest/1365/submission/82884840

Its probably due to the overhead of vector being copied each time your are calling your dfs function.

Check the below submission, i changed your code to passing by reference and it got accepted https://codeforces.com/contest/1365/submission/82885046

Always pass constants by reference. Lesson learned. Thank you :)

Weird constraints. It taught me a lesson though.

can anybody tell me why my submission is getting WA 82884730

wow! editorial come so early

There is a typing mistake in F code

Hey everyone, I am hoping to get some help on why my submission to problem F fails. What am I doing wrong here? Thanks in advance.

82883731

Are you aware of what the count method does?

Try this case:

Your code outputs "Yes"

Apparently not as well as I thought lol Thanks for the comment!

Can u please help me why i am getting WA at test 38 for problem F. My logic is same as explained in the tutorial. Link to my submission https://codeforces.com/contest/1365/submission/83329650

Thanks in advance for your reply:)

Try this:

Also, your logic isn't exactly the same, the editorial says "so we only need to check if the

multisetof these pairs in $$$b$$$ is the same as themultisetof pairs in $$$a$$$."Thanks for your reply. I got it now, i was using set because of which i was not able to chk the count of same pairs. ;)

Can anyone tell why my approach is giving TLE? I first made walls to bock all the B. Then I checked if any B could reach (n, m). If they can reach, ans will be "No". Otherwise, I checked if all the G get to (n, m) or not. Please help. This is my submission.

if you check separately for each G then it will lead to TLE since worst case lets say there are approximately n*m G's. (can ignore the -1 due to last being '.')

Now dfs/bfs from each vertex would take approx n*m*4 steps.

so it would lead to net worst case time complexity of t*n*m*n*m*4 which would take >1 second.

I had made the same mistake initially. What you can do is just perform dfs/bfs from n,m and then check if each 'G' vertex is visited.

Got it thanks!

Thanks for nice problems, as well as quick and detailed editorial as well. Couldn't solve much during contest but learned a lot:)

There is something wrong with the codes.

and

in problem F

In problem C.

Now for each shift, we can find the number of matching pairs and take the maximum.Can someone please explain this line and in which step it is happening in editorial code?

basically 'curr' is obtaining the number of shifts required for element at ith position to match. and then its frequency is being stored.

then in the above part of code the maximum frequency is obtained and is the answer.

How offset[cur]++ is storing the no. of matching pairs in each shift?

thanks

how the maximum frequency of shifts is answer?

Because if you shift the array by the amount of positions the result is that much number of positions with same value. Because you want to have the shift with maximum such positions, you choose the one with max freq.

yeah understood! thanks

First, you calculate the offset between the positions of $$$x$$$ in $$$a$$$ and $$$b$$$, for all $$$x$$$. Let $$$d$$$ be the offset that appears more often. Then you shift the sequence $$$d$$$ times, and have the maximum number of correct digits. See my code:

The offset is (digita[i] — digitb[i] + n)%n, because digita[i] — digitb[i] can be negative.

I'll have to go with antontrygubO_o here. Problem G stands for Problem Genius!

Thanks for a fun contest! Well written problem statements — brief, good grammar etc. — to the point and very effective. Thanks for making this about solving the problem, rather than understanding the problem statements.

I liked the way of mentioning the

Key Ideain the beginning of the tutorial :)how can div2E pass n^3 solution? isn't that 10^8 for n=500

time limit is 2 seconds.

(500)^3 = 1.25 * 10^8

it can further narrowed down to 500^3/6 bc of permutations

$$$\sum ^{n}_{i=1}\sum ^{n}_{j=i+1}\sum ^{n}_{k=j+1}1=\dfrac 1 6 n^3-\dfrac 1 2 n^2+\dfrac 1 3 n$$$. Plug in $$$n=500$$$ the result is about 2e7.

E is too easy, I think it should just be B or C, or should increase the limit

Can someone please explain why this doesn't work? -

https://codeforces.com/contest/1365/submission/82893654

Why did we choose bfs instead of dfs in D?

Hey you can choose either of them.

My solution for D:

Make sure every bad person is surrounded by a grid of walls, something like this

After that, run a DFS from (n,m) and count the number of G's (count_G) and B's (count_B) on your path without crossing any #(wall).

CodeThanks bhai

2 2

`BG`

`#.`

can anyone explain how its answer is no please

You can only block the path of $$$B$$$ if you place a wall on the cell $$$(2,2)$$$, which would also block the path of $$$G$$$. Hence, it is not possible.

in this case, it is not possible to block the bad person to go to the destination cell (2, 2) if the good person can go in the destination cell (2, 2). The bad person will just follow the path of the good person as there is no way to separate them by using some walls.

NB. You have to perform the blocking operation before moving any person i.e before the journey starts.

since you can't put a wall on G's, the B will just be able to go along the path the G would go to.

Video Solutions for A to E:

https://www.youtube.com/watch?v=1s0bDFWTArY

assign the masks in such a way that no two masks assigned to two indices are submasks of each other. Anyone please explain. Problem G

Problem setters need to understand one thing that the questions difficulty must be maintained in increasing order because in last to last contest also, problem A was difficult to solve than as compared to B and C. Who else agrees with the fact?

FastestFinger In the code section of problem F "map, int> pairs; " should be "map<int, int> pairs;" I think.

Problem A

n=2, m=3

0 0 0

0 1 0

For this test case, shouldn't the answer be Vivek? Correct me if I have understood it wrong.

Ashish can claim either cell (1, 1) or (1, 3) (since he goes first); then Vivek won't have any cell to choose (since the cell chosen by Ashish will make any other cell on line 1 unable to be chosen, and the other cells also can't be chosen), thus according to the statement of the problem, Vivek will lose and Ashish will win.

Oh so it is entire row then. I understood it as a row border/column border. So I thought after Ashish make a choice

0 0 1

0 1 0

Vivek can choose (1,1). And then Ashish has no choice. So he loses. My bad.

Thanks though!

initially, there are only 2 possible moves for Ashish, either choose the cell(1, 1) or cell(1, 3). After one of these two moves, the grid will be looked like

or

After this, there is no way to choose a cell following the criteria described in the statement.

Hence the result is "Ashish" .

Test cases for F is not strong enough.

I believed I hacked some AC submissions using this data set. Obviously the right answer is No, but they all returned Yes.

1 3 8 9 8 9 8 9

Submissions:

https://codeforces.com/contest/1365/submission/82823958 https://codeforces.com/contest/1365/submission/82854157

Uphacking on that problem caused an

`unexpected verdict`

.It seems that the validator(or checker) crashed :(

fastestfinger Please try to fix this, thanks.

Is it just me or does anyone else also feel that

problem Cis the newBandProblem Dis the newCin the recent rounds?Can anyone explain why my solution for D failed? I used dfs and marked visited all the G whenever I encounter B then I return back and after the dfs is completely executed, I checked whether there is any G left to be unvisited. I also checked for the condition whether there is any G adjacent to B. Please help!

Link to my solution: https://codeforces.com/contest/1365/submission/82868517

I am getting memory limit exceeded in test case 4 of problem D. The link to my solution is https://codeforces.com/contest/1365/submission/82901871. Can anyone help me in knowing where I am going wrong.

can anyone help me figure out what i am doing wrong in div2-D? 82900500

Can anyone please explain this for DIV2B question, By swapping any two elements at indices i and j, their b[i] and b[j] are also swapped? Or only element values are swapped at indices i and j not b[i] and b[j].

Yes both the value as well as b[i] and b[j] will get swapped Consider each value-key pair as one unbreakable unit.

For problem E , Why maximum element isn't always considered in finding or?

Consider a[] sorted max element first, descending. Let $$$b(x)$$$ be the set of bits in x.

If $$$b(a_1)=b(a_2 + a_3)$$$ then it is always better to not choose $$$a_1$$$, because all bits of it a covered by the other two elements. And we can add $$$a_4$$$ instead of $$$a_1$$$ to getter a better result.

i was wondering if it was possible to use a comparator function in B. If someone has done it, please share the solution.

Can we solve $$$E$$$ using $$$DP$$$? I tried solving using $$$DP$$$ in the contest time but got $$$wa$$$ on pretest $$$6$$$. My $$$DP$$$ idea was pretty simple.

codeStill not understanding why got $$$WA$$$. Please help

N.B: It is failing on cases like

6

18 8 1 4 6 16

Consider input

The bits of second and third element of the array equals the first one. If you start adding from left to right, you would need to find that 6 is covered by 4 and 2, so you can remove it to add 1 instead.

In solution of E:

"Let i be any number such that the i-th bit is set in at least k−2 elements of s"

What does it mean by "let i be any number" ? the ith element from the sequence ?

nope referring to the bit

could someone help me debug my solution for D

Can someone please find out the error in my code : https://codeforces.com/contest/1365/submission/82866772 I tried greedily since picking the max set bit would always be useful. I set k to the cnt of numbers having the max bit set. Now I went through all bit positions and checked if there cnt was more than max(1,k-2). If yes I added (1<<i) to my ans. Giving wrong answer on 6th pretest.

same here

Your idea is wrong, try with this case:

Ans should be 14.

The reason is that if you pick the two 8s, your code would check if it could pick one 4, then if it could pick one 2... but if you pick 4 numbers then the 4 and the 2 won't be taken into account, as there isn't at least 2 of each type.

what was the point of making so small constraints for F when expected solution was O(n*logn)?

To trick someone that solution is not that easy as it is. Check the ashishgup’s last contest’s C question. No point there also of giving such low constraints even the solution just have linear time complexity.

In this case, notice that the sum of $$$n$$$ over all test cases is unbounded, i.e. there can be test files where $$$t=500$$$ and $$$n=500$$$, for each $$$t$$$. Hence, you'll have to account for number of test cases while computing time complexity (in this case, the intended solution has complexity $$$O(t*n*logn)$$$ for each test 'file', which is reasonable for 2 seconds).

I think it was set this way to increase the number of possible test cases on which the solution runs (expected answer was simply a "Yes/No", so you'll require more test cases to verify solution's correctness), while keeping the number of test files same.

Can someone tell me why this code is getting WA for problem D?? https://codeforces.com/contest/1365/submission/82938464

Solved!!

https://codeforces.com/contest/1365/submission/82955051 In my code for question D I have used only one 2D array of size 51*51 though in the test case 8 it is showing MEmory limit exit . What is the reason?

Most likely one of the while loop runs and grows infinite.