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 wrong
I 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.
I did the same mistake, misread the statement
I also assumed the same , and could not solve the problem A due to that .
me too
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
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
It says tutorial is not available. Anyone else having same problem ?
UPD : It's working now
Yes
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.
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.
And hence as a result, always stay beginners.
I feel so stupid after reading the editorial for problem B
I have the same feelings but for E
Me too bro
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
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
4 3 2 1 ``
1 1 1 0
`` try bubble sort on this
thank you got it
no problem :)
Hey giorgtarkha, 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
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.net/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
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
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.net/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.net/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 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.net/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.net/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.net/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,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.
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)
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
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
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 ??
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
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.net/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.
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.net/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 elements with given properties. That was SAD!!!
I feel you. Spoiled my whole time because of that.
sad
Can anyone tell me what is wronge with my code Trouble Sort https://codeforces.net/contest/1365/submission/82849016
consider
1 3 4 2
0 1 1 1
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 E could 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
iandjwhereb_i = b_j = 1. Now suppose there is some indexksuch thatb_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.
434 33 8 14The 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.
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.....
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
mnis even, thenVivekis the one, who wins the game and notAshish.Amazing problems! $$$G$$$ is really nice and unique.
BTW problem $$$F$$$ in OEIS — https://oeis.org/A037223
If 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.net/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.net/contest/1365/submission/82870178 https://codeforces.net/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.net/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.net/contest/1365/submission/82885046
Always pass constants by reference. Lesson learned. Thank you :)
Weird constraints. It taught me a lesson though.
wow! editorial come so early
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.net/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 multiset of these pairs in $$$b$$$ is the same as the multiset of 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. ;)
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 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.
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 Idea in the beginning of the tutorial :)
how can div2E pass n^3 solution? isn't that 10^8 for n=500
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
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).
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.
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
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.
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.net/contest/1365/submission/82823958 https://codeforces.net/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 C is the new B and Problem D is the new C in the recent rounds?
I am getting memory limit exceeded in test case 4 of problem D. The link to my solution is https://codeforces.net/contest/1365/submission/82901871. Can anyone help me in knowing where I am going wrong.
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.
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.
Still 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.
Can someone please find out the error in my code : https://codeforces.net/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.
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.
https://codeforces.net/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.
Even I am getting memory limit exceeded on test case 4. Still not able to figure it what is wrong. Help will be highly appreciated. Link to my latest submission: https://codeforces.net/contest/1365/submission/83106539
Got the reason for Memory limit exceeded.
Looks like the dfs runs in infinite recursion if there are two "." next to each other.
Can you check mine once? 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. Thanks!
Link to my solution: https://codeforces.net/contest/1365/submission/82868517
Why this?
If there are no G there still can be unblockable B, then answer would be No.
If there is no G present then we can directly block the destination as the problem statement says
"It is guaranteed that the cell (n,m) is empty. Vivek can also block this cell."
Good point, I did not see that.
Edit: Ah, got it. Assume grid like
The G will never reach Escape, but your dfs will reach the G.
Hi can someone please point out the mistake in https://codeforces.net/contest/1365/submission/82922169 I am getting WA on pt3 and can't understand why. Thank you.
if(g==0||b==0){cout<<"Yes\n";continue;}It is possible that the goods cannot escape because the escape cell is blocked, even if there are no bad ones.But the last cell is guaranteed to be empty
Oh sorry ..I get it.... it's possible that last cell is surrounded by walls Thanks a lot..
In A,does it make a difference if I directly declare the array like int a[51][51] instead of declaring a constant int N and using it as a[N][N] ?
No difference.
I have doubt in 1365A if mn is odd then Ashish win and if it is even than Vivak win then why sir Ashishgup use this
if(mn % 2) cout << "Ashish" << endl; else cout << "Vivek" << endl;If I am thinking wrong please tall me, I am beginner in coding.This is because
if(mn % 2)tells if mn is odd or even. tutorialDuring Contest Time:
In E, the values can be upto 10^18, isnt the complexity actually (n^3).log(10^18), and that seems off the limit for 2 seconds. Where did i go wrong?
Complexity is is O(n^3). For what you would need the log part?
Bitwise or, max
The bitwise or is in all common programming languages a simple operation, like for example addition.
but they do take O(digits) time
No, they take O(1) time.
Of course all operations take some more time on "bigger" datatypes, but usually we ignore this fact when referring to the big O notation. This is because it does not make sense to multiplicate everything by 8.
And in fact, processors do ORs in one tic, even on 64 bit types.
thanx, I understood
i used to think that is the reason why most problems of O(n) have inputs of size <= 10^6 (and not 10^7 or 10^8) so that these factors could be accommodated
Why left shift of $$$a$$$ is same as right shift of $$$b$$$?
Because they are shiftet relative to each other.
Assume shift of a by x to right. Then the element a[i] fits to the element b[i+x].
Assume shift of b by x to left. Then the element b[i-x] fits to a[i].
Clearly $$$i+x-x=i$$$
Does it mean that after shifting arrays one by one to the left/right, they will be the same?
In this problem, yes, it defines it like this.
Can anyone help me with D? I think i've checked every possible cases.Please help me with what i am missing. https://codeforces.net/contest/1365/submission/83117062
This loop in dfs is wrong. That way implemented your people can go diagonal, too. You should simply omit the inner for loop.
83114496 can anyone tell me why am i getting a WA
Am I the only one who read E multiple times but still couldn't understand the problem?
Can someone tell me what is wrong with my approach for the E problem? I am first finding the largest value and then using 2 separate loops finding 2 other values such that the bitwise OR of all the three values is maximum.
See this comment for an example where this fails.
Thanks for the reference!
Problem F was an absolute beauty. Kudos to the setters !! Can someone suggest problems similar to F involving some beautiful observations and then pretty straightforward implementation?
can anyone suggest some problems like this problem C .?? It will be helpfull for me .
It is tagged with "data structures" "greedy" "implementation", so try this.
In Problem B , Do we require to swap the type also after swapping the elements. If yes then the solution given will be wrong , else it will be Correct.
According to the problem statement we do not swap the type too. meaning type is bound to the element (does not get exchanged when swapping).
but lets say we have to swap the types even, even then if we have atleast one element with a different type. lets say elements
a,b,c, typest1andt2, positioni,j,k.a t1 ib t2 jc t1 kIf we want to swap a and c of the same type. we can do the following
swap(a,b) -> (a t2 j) and (b t1 i)
swap(b,c) -> (b t1 k) and (c t1 i)
swap(a,b) -> (b t2 j) and (a t1 k)
so finally
a t1 kb t2 jc t1 ia and c have swapped positions while b remains same, in the end we swap b to its correct place and thus the element would be in sorted order.
Conclusion — It doesn't matter if type's are swapped or not.
It matters in this case eg: — (25 , 1 ) (45 , 1) (48, 0) (421 ,1) Here (num , type)
i didn't get what you are trying to say.
isn't it already sorted? 25 45 48 421.
To add -
lets consider (45, 1) (25,1) (421,1) (48, 0)
You can swap the first two using 48,0 like i mentioned before in the above post. it wouldn't affect (48,0)
so we have (25, 1) (45, 1) (421, 1) (48, 0). and now swap (48,421) leading to final sorted array
(25, 1) (45, 1) (48, 1) (421, 0)
Try it out on paper for various cases. it is as the editorial stated. since even if types are swapped it is possible to swap(a,c) of same types if we have b of different type. so the ans would be 'yes' if such a b exists. else we check is its already sorted or not.
Please help me understand problem E.. i didnt get what we have to do in the problem(not the logic) but what the question means
Same here! Please help us.
Suppose you have chosen k elements from the sequence a. List them down after writing them in base 2. Now for each non-negative i, check how many of these numbers have the ith bit set (i.e., the ith bit from right is 1) and call this number num(i) for now. If
num(i) > max(1, k-2)then you have to add2^ito the answer. Do this for each i from 0 to 63.The best editorial I have seen ever. Tutorials and codes are easy to understand. Thank you all authors of this round.
Agreed!
Video Solution to D: https://youtu.be/R4aj3I7yxg0
Can anyone say why my submission of D is getting TLE.. submission link: https://codeforces.net/contest/1365/submission/83147673
You do the bfs() for every G in the grid which are up to $$$m*n$$$, and the bfs twice iterates the grid which is again $$$m*n$$$, so it is $$$O(n^4)$$$.
Since it is up to 100 testcases, it gets basically $$$O(n^5)$$$ which is to much.
Really liked the idea behind problem E.
Can anyone pls see my code of problem C why am i getting WA? i have done as the tutorial says. here is my submission link : https://codeforces.net/contest/1365/submission/83156137
I think the last loop is not correct. In array shift[] you have the shifts of the positions, so shift[j] is the number of positions element a[j] must be shifted to fit with b[i]. In array cnt[] you have the frequency of shift[]. And your loop is
It should be something like
Funny thing is that the first 12 testcases work either way.
Man ... still got WA on test case 4. submission link: https://codeforces.net/contest/1365/submission/83163159
what does uninitialized value usage means?
I think this is because you use 1 based indexing, so shift[0] never gets initialized.
Better use vector than arrays to prevent such errors. Edit: But in this case of course you need to iterate shift[] starting at 1 instead of 0.
Man.. it is still getting WA on tc 4. https://codeforces.net/contest/1365/submission/83164700
In this loop you need to use 0 based indexing, since cnt[i] is the frequency of pairs if shifted by i.
In testcase 4 the maximum is 1 pair at shift of 0. So run the loop from 0 to n-1.
Anyone plz tell me what is wrong in my code for D anyone please help me out. https://codeforces.net/contest/1365/submission/83125707
In dfs you need to travers not only up/left, but also down/right. And if you do, you need to prevent endless loops by checking the vis[][] array.
In Probem D Solve the Maze Tutorial, the following test case is not working..why?
1 2 2 .. .G
I think output should be "Yes". What does not work?
It is guaranteed that the cell (n,m) is empty.
What is wrong in my code for problem E , anyone please help me. https://codeforces.net/contest/1365/submission/83165332
It is wrong logic. The question is why you think this would work? Did you check tutorial for the simple solution?
I am finding all possible subsets having set bits satisfying the given conditions using dynamic programming. Can you tell me what is wrong in this logic?And in editorial it is given time Complexity of Solution is O(n^3) which is going beyond 10^8 operations thats why i was thinking for a better approach please help me sir.
In spite of the downvotes... it is wrong logic.
That your implementation is some kind of dp is obvious. But what is your recurrence, I do not understand the idea of your code, and cannot think of a working dp solution at all.
Ohk, I got my mistake. But please tell me why O(n^3) approch is working here. As n is of range 500 and 500^3 is 125000000 which is above 10^8 operations.
$$$10^8$$$ is just a guess. If it is fast operations (often referred to as a small 'constant factor') $$$10^9$$$ or even more is ok, too.
Here we got very simple operations.
Edit: And just to be right, If we calc with these numbers, it would be $$$\frac{500^3}{2}$$$
Ohk i got it , thank you very much for your time:)
solution with explanation to problem D solution
First Look for B first and block all neighbors of B that have '.' by replacing with wall. If any B has neighbor 'G' then it will return No
Than DFS/BFS to check if all G can go to n,m
I got Memory limit exceeded on test 8 on problem D. My code here. Please, someone, explain this. Thanks in advance.
Try making global array rather than making new array for each test case. This can help!
You are doing wrong BFS. You have to make visited true when you push in queue not when you pop it from queue. You are pushing the same value in queue therefore using extra space. I hope this will help.
Thank you very much. It worked.
Glad to hear that brother
In D my code getting TLE for test case — 16. I've tried several hours to find bug but can't.I will be glad a lot, If anyone make me understand why getting TLE.
my submission: 83191177
You do the dfs() for every G. see here
My solution for A was pretty straightforward — traverse the grid, if there is a 1 anywhere, mark that row and column as unusable. Next, traverse the grid again, if a column and row is usable, place advance to the next turn and mark this row and column unusable. I just kept on incrementing a count and printed the result on the basis of wether the count was odd or even.
char arr[N][N]; for (ll i = 1; i <= n; i++) { cin >> (arr[i] + 1); }
1365D — Solve The Maze How is this code working ? Someone please explain it ?
The arrays are $$$0$$$-indexed, where you are trying to use the $$$N^{th}$$$ row or column which is out of memory. You can do
for (ll i = 0; i < n; i++)to avoid this problem.Wow, solution for G is actually really clean. Really nice problem.
One tip for the editorial, though: it is really confusing that the example for the optimal solution has $$$n=4$$$ AND $$$q=4$$$. If you had something like $$$n=6$$$ and $$$q=4$$$ using the same masking mechanism, it would've been much easier to follow. It took me a while to realize that there were $$$n$$$ different $$$q$$$-bit masks, not $$$q$$$ different $$$n$$$-bit masks. In hindsight this should've been more clear from the complexity, but it would've been nice to have been explicitly stated somewhere.
Problem G is insanely awesome!
If anyone need Div2 D detail explanation Here
My proof for DIV2 E
Let us define bar as the minimum no of elements that should have a bit,for that bit to be added to the result, for a size of k, bar is k-2.
First observation, when we add more elements,bar also increases(for k>=3), hence some of the bits may get excluded, if we add more elements, and this is the reason why the result may decrease if we add more elements.
Let's assume the optimal answer has k elements, now let's remove one element, the result will now decrease if and only if there was a bit i, which was added to the result before, but now cannot be added after removing, because it doesn't satisfy the bar,i.e earlier the bit i must have been set in exactly k-2 elements, and after removing it doesn't satisfy the bar, but the bar also decreases to k-3 for k>3(as the current number of elements is k-1) ,hence removing an element doesn't decrease the result for k>3.But for k<=3, bar doesn't decrease upon removing an element,it always stays as one.Hence the optimal answer can be achieved with k<=3.
Let us also prove that when k<3 adding an element will not decrease the result. When k=1 or k=2 bar is 1, it remains 1 for even k=3 hence adding an element will not increase the bar,hence will not decrease the result(refer "First oberservation").
Hence optimal answer can be achieved by choosing an appropriate subset of size 3
D don't deserve to be 1700. haha