1335A - Candies and Two Sisters
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (n - 1) / 2 << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n, a, b;
cin >> n >> a >> b;
for (int i = 0; i < n; ++i) {
cout << char('a' + i % b);
}
cout << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(n + 1);
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
int mx = *max_element(cnt.begin(), cnt.end());
int diff = n + 1 - count(cnt.begin(), cnt.end(), 0);
cout << max(min(mx - 1, diff), min(mx, diff - 1)) << endl;
}
return 0;
}
Идея: vovuh
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
for (int i = 0; i < 9; ++i) {
string s;
cin >> s;
for (auto &c : s) if (c == '2') c = '1';
cout << s << endl;
}
}
return 0;
}
1335E1 - Three Blocks Palindrome (easy version)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> cnt(26, vector<int>(n + 1));
forn(i, n) {
forn(j, 26) cnt[j][i + 1] = cnt[j][i];
++cnt[a[i] - 1][i + 1];
}
int ans = 0;
forn(i, 26) ans = max(ans, cnt[i][n - 1]);
forn(l, n) fore(r, l, n) {
int cntin = 0, cntout = 0;
forn(el, 26) {
cntin = max(cntin, cnt[el][r + 1] - cnt[el][l]);
cntout = max(cntout, min(cnt[el][l], cnt[el][n] - cnt[el][r + 1]) * 2);
}
ans = max(ans, cntin + cntout);
}
cout << ans << endl;
}
return 0;
}
1335E2 - Three Blocks Palindrome (hard version)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<vector<int>> cnt(200, vector<int>(n + 1));
vector<vector<int>> pos(200);
forn(i, n) {
forn(j, 200) cnt[j][i + 1] = cnt[j][i];
++cnt[a[i] - 1][i + 1];
pos[a[i] - 1].push_back(i);
}
int ans = 0;
forn(i, 200) {
ans = max(ans, sz(pos[i]));
forn(p, sz(pos[i]) / 2) {
int l = pos[i][p] + 1, r = pos[i][sz(pos[i]) - p - 1] - 1;
forn(el, 200) {
int sum = cnt[el][r + 1] - cnt[el][l];
ans = max(ans, (p + 1) * 2 + sum);
}
}
}
cout << ans << endl;
}
return 0;
}
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int n, m, lognm;
vector<string> c, s;
vector<vector<int>> used, nxt;
void getnext(int x, int y, int &nx, int &ny) {
if (s[x][y] == 'U') nx = x - 1, ny = y;
if (s[x][y] == 'R') nx = x, ny = y + 1;
if (s[x][y] == 'D') nx = x + 1, ny = y;
if (s[x][y] == 'L') nx = x, ny = y - 1;
}
void dfs(int x, int y) {
used[x][y] = 1;
int nx = -1, ny = -1;
getnext(x, y, nx, ny);
assert(0 <= nx && nx < n && 0 <= ny && ny < m);
int v = x * m + y, to = nx * m + ny;
if (!used[nx][ny]) dfs(nx, ny);
nxt[v][0] = to;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
cin >> n >> m;
lognm = 0;
int nm = n * m;
while ((1 << lognm) <= nm) ++lognm;
c = s = vector<string>(n);
for (auto &it : c) cin >> it;
for (auto &it : s) cin >> it;
used = vector<vector<int>>(n, vector<int>(m));
nxt = vector<vector<int>>(n * m, vector<int>(lognm));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!used[i][j]) dfs(i, j);
}
}
for (int deg = 1; deg < lognm; ++deg) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int id = i * m + j;
nxt[id][deg] = nxt[nxt[id][deg - 1]][deg - 1];
}
}
}
vector<vector<int>> black, white;
black = white = vector<vector<int>>(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int v = i * m + j, to = v;
for (int deg = lognm - 1; deg >= 0; --deg) {
if ((nm >> deg) & 1) to = nxt[to][deg];
}
if (c[i][j] == '0') ++black[to / m][to % m];
else ++white[to / m][to % m];
}
}
int all = 0, good = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (black[i][j]) {
++all;
++good;
} else if (white[i][j]) {
++all;
}
}
}
cout << all << " " << good << endl;
}
return 0;
}
Решение (действительно _overrated_, самый быстрый O(nm log nm))
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
using namespace std;
const int N = 1e6 + 7;
const int K = 24;
int f[N];
int dp[N];
int ndp[N];
int sel[N];
int fans[N];
int sans[N];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
sel[i * m + j] = (s[j] == '0');
}
}
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
int to = -1;
if (s[j] == 'U') to = (i - 1) * m + j;
if (s[j] == 'D') to = (i + 1) * m + j;
if (s[j] == 'L') to = i * m + (j - 1);
if (s[j] == 'R') to = i * m + (j + 1);
f[i * m + j] = to;
}
}
n *= m;
for (int i = 0; i < n; i++) {
dp[i] = f[i];
}
for (int j = 0; j < K; j++) {
for (int i = 0; i < n; i++) {
ndp[i] = dp[dp[i]];
}
for (int i = 0; i < n; i++) {
dp[i] = ndp[i];
}
}
fill(fans, fans + n, 0);
fill(sans, sans + n, 0);
for (int i = 0; i < n; i++) {
fans[dp[i]]++;
sans[dp[i]] += sel[i];
}
int fs = 0, ss = 0;
for (int i = 0; i < n; i++) {
fs += (fans[i] > 0);
ss += (sans[i] > 0);
}
cout << fs << ' ' << ss << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> q;
while (q--) {
solve();
}
}
That anti-sudoku approach is the coolest approach ever possible!!
I have done that in contest! :D
After reading the solution, I feel very stupid now. Wasted more than 1 hour for this problem. :(
O(n*200) = O(n) approach for E-1/E-2 this code
Another approach for D 109670932
Yr way of writting sid_rasa is in yr snippet is reallly amazing. Can I get to know how would you do it>
Just search Ascii text generator and you can easily do it.
I like Problem D, it's really interesting.
Idea is good, but problem is obvious.
Maybe.
How to solve problem A ?
learn stars and bars algorithm it will help you even if there are more than 2 variable
for question B，why my solution is wrong.Can you give me some advice?This is my first time participating in a contest. Thank you!
check this: 78 39 26
In alphabet string, you have repeated 'g' twice, hence for test case 10 10 10 It fails.
Accepted Thank you very much!
Instead of hardcoding alphabet to get 'c' letter you can write 'a'+2, to get 'h' write 'a'+7.
Also, managing char* is more difficult than strings. You can make an empty string of length n by typing string s(n) and then you can access elements by s[i].
except the mistake of alphabet, this solution is wrong itself...
I found this mistake, thanks, I'm really stupid:)
My fault, when a gets bigger, so does the step.
take input char str[1000000]='abcdefghijklmnjklmnopqrstuvwxyz' and yes u repeat g twice
Can someone please help me with my submission for problem C? Here is the link: 76600537
Check this:
1
2
1 1
Я думаю что, если бы в задаче Е2 ограничения алфавита были побольше то пришлось бы решать с помощью персистентного дерева отрезков.
для див3 сильно сложно. но задачи понравились. составители — красавцы :)
My solution for C is similar to the one mentioned here just that I use map instead of vector but something weird happens when I input first two numbers i.e t and value of first 'n', it gives me an unexpected output instead of waiting for the array elements 'a[i]' . Not asking anyone to debug my whole code (logic) just point out why this happens because I am not able to solve this issue. If I seem too desperate, don't down-vote me and tell me to correct my approach.
I submitted your code 76658706
What is the logic behind this approach?? And why s==mx gives ans as mx-1?? Plz help me out
consider the case
1
7
1 1 1 1 2 3 4
here s = mx = 4
if we use 4 distinct elements 1 2 3 4 in the first set, we are left with only 3 1's for the second set and as the size of both the sets should be equal it is invalid, similarly if we use 4 1's in the second set then we are left with only 3 distinct elements for set 1. hence if s == mx, Ans = mx-1
Why the time complexity of solution E is $$$O(Nk)$$$. It seems that it enumerates all possible lengths in $$$O(N)$$$ and iteraters all possible pair $$$(a, b)$$$ in $$$O(k^2)$$$.
UPDATE: Here is my code:76588322
Actually, you just pass through all positions of each characters. So in total, you just pass through
Nelements, which means n segments. Therefore, time complexity is justO(Nk)Thanks, but I still don't quite understand.
I have added my code to the post. Would you give an explanation based on the offical solution or my solution. Thanks in advance.
Note that we are making an array of size
Ksuch that theithelement contains a vector of the positions of value i. So its quite clear to see that the total number of elements in the entire array is equal toN. In the solution, we are traversing through each vector, sayv, and just keeping two pointers at theithand(v.size()-1-i)thpositions and then we are iterating through all values from 1-200 and finding the answer. So for each vector, we are finding a possible answer inO(v.size()*K). Since there are K vectors, the overrall complexity isO(v1.size()*k + v2.size()*k +.... v200.size()*k) = O(NK).I got it! The total number of all vector
vis notnkbutn. So the time complexity isO(nk).Thanks bro!
Actually, possible pair (a, b) is not calculated in O(k^2), it's calculated in O(k). It seems like O(k^2) but it's not. Just take pen and paper and check the sample case. You would get it. I got the exactly same solution but became fool thinking of my solution would be O(n*k^2) and didn't submit that. I got to know mine is O(n*k) later.
I think I have figured out how it works. Thanks bro.
why the C problem can do that,can you explain?
Analyse these 3 cases.
4
1 1 2 3
5
1 1 1 2 3
4
1 1 1 3
You will be able to get yourself now.
ok，thanks very much.
Can someone please tell me what's wrong in my 76608051 as it gave runtime error while running perfectly fine on my local system.
My basic approach was I made a vector of vector of size 201 as the range of input is between 1 to 200 and I stored the occurrences of each number in the corresponding position. Finally, I iterated each of the numbers from 1 to 200 and I calculated the maximum possible answer.
I calculated the answer as I iterated the current element taking indexes from starting and ending while calculating the maximum possible frequency of another distinct element that can be inserted in between. I calculated the maximum frequency in range by binary search.
Please help me with it.
Problem E2 is very nice. What is the Mo's algorithm approach?
E2 was super nice and it fooled me.
The solution described in editorial iterates over all 200 elements to find maximum frequency between indices l and r. This iteration can be avoided using Mo's algorithm. Finding maximum frequency in a range is a classical problem. See this
Oh, I see it now. Thanks!
There would be approx n^2 ranges....how can I do it with Mo's algo
I have same doubt, Can someone please explain this in detail?
I can never understand how this down voting thing works here and I know I will be getting many more downvotes on this , but I just asked a doubt, that sometimes feels like a curse. I thought the whole idea of codeforces is to make people better at algorithms.
same doubt ..have u got the answer ?? if u got then plz explain
I got that... for every x from 1 to 200 take first k occurences from the left(from 0th index) and same from right....and between them count the maximum frequnecy using mo's algo
It is mentioned in the editorial that there are O(n) segments only.
Is there any reason why system testing has been really slow for the past few contests?
Why D Anti-Suduko in giving wrong if we replace any number in a row and only giving right if we replace one ?
For every row, column and block, the nine numbers shouldn't be distinct.
In beginning all the numbers are different so if I repeat any one of them then there won't be 9 distinct elements in rows/col.
What about the blocks?
how is changing all 1's to 2's handling the blocks ?
In the original Suduko, every row, column and block contains 1-9, 9 different numbers. After you change 1's to 2's, every row, column and blocks will contains a couple of 2, which meets the Anti-Suduko constraints.
After replacing all 1's with 2's, the entire sudoku table has no 1's, hence only 8 distinct elements. The number of distinct elements per row/column/block can not exceed the number of distinct elements in the entire table.
Or, another way to think about it, choose an 1. In the initial table its row, column and block contain 9 distinct elements each (including 2s). If you replace the 1 with a 2, you get a duplicate in each of them. That way you take care of 1 row, 1 column 1 block by 1 replacement. The initial table contains a total of 9 1s, replacing each of them takes care of 1 row, 1 column, 1 block, all of them different from the ones handled by previous replacements, because in the initial array there were no 2 1s in the same row or column or block.
Instead of 1 and 2 you can pick any 2 distinct numbers between 1 and 9 (both inclusive) and apply the similar process. The solution will still work.
Can someone share the Mo's algorithm approach for problem E2 ? Thanks in advance.
Can someone please explain what this does in Problem B? I am a total newbie to these cp. This was my first contest.
for (int i = 0; i < n; ++i) { cout << char('a' + i % b); }
Each char has got a different ascii code. By adding
i % b, you take the char with ascii code97 + i % b. This value is always between 97 and 122, so it represents a valid lowercase letter.Thanks for the reply. But how does it ensure that b number of distinct letters are printed out in the sub string of length a? Also, how does it print the other random characters? Sorry for making so many questions.
i % bis the remainder ofiwhen divided byb.For example, the string with
b = 5isabcdeabcdeabcde...because
'a' + 0 % 5 = 'a' + 5 % 5 = 'a', 'a' + 1 % 5 = 'b', etc.Notice that, for each substring of length
b,bdifferent letters are printed out because the remainders are all different. So the strings of lengtha- contain at least
bdistinct characters because they contain a string of lengthb- contain at most
bdistinct characters because the whole string contains onlybdistinct charactersHence the condition is true for each substring of length
b.In the que:"E:Three Blocks palindrome" the sol gives wrong answer for the array: 1 2 2 1 3 1 2 1 It gives ans as 5 but correct answer is 6 i.e. by removing a[4]:-(3) and a[6]:-(2) Please see into it. and explain if i am wrong
After removing 4th and 7th element as you say array look like : 1 2 2 1 1 1, but this is not a Three Blocks palindrome.
What does AL denote in the time complexity of Problem E2?
The alphabet size which is 26 for E1 and 200 for E2.
In problem F solution, what fans & sans array meant for?
In problem F, this is how I approached it. Since each vertex has out-degree = 1 and the matrix can be thought of as a directed graph, hence we can say that the graph contains multiple components and each component has exactly one cycle. Now multiple paths might converge into the same cycle. Hence the maximum number of robots that can be placed is equal to the sum of length of each cycle.
For the second part of the question: Think of the graph to be inverted.(We don't actually need to invert it) Number each cycle from 0...(length of cycle — 1). Mark all vertices of this cycle as visited Now apply dfs from each vertex of the cycle and assign a number to each vertex : number[child] = number[parent]+1 (still thinking of graph to be inverted) Now for each black cell we take the modulo of its number with the length of the cycle in its component.
Answer to second part = sum of distinct remainders for each component.
Is this logic correct? I am getting WA on test 2 (1248th number differs by 1).
It seems to be correct and is exactly what I did. My implementation is a little over complicated but if you can check it out in my submissions and it was accepted.
You should apply multi-sourced bfs instead of dfs to assign the numbers.
Yes its correct, can you please share your code? then probable i can help you solving your problem.
Please check this code i added some comments, i hope it will help you.
I forgot to update. I had corrected my code. There was a small implementation mistake. Thanks for reaching out though.
Can you please Explain your approach to part 2 more clearly !!!
For every cycle choose a vertex in it as root of this cycle, then for every vertex in this component calculate how many turns it takes to reach the root for the first time module length of the cycle and store it in $$$fs_v$$$, then two robots one starting at $$$v$$$ and other at $$$u$$$ will collapse iff the condition below holds :
It can be proved easily, it's quite different with what he said but after thinking a bit you will find out that they are both the same.
In problem D is it necessary to only replace all 2 with 1 or can we replace any other particular number with something different. For eg: all 3 with 4?
You can. It's just random.
Hello everyone, This is the first time I participated in a contest. I couldn't find a good explanation or solution to construct the string problem in Python 3.
Can anyone help me to get through the problem solution?
Thanks
It's easy when you observe some pattern in making such string,
There is a requirement of generating n sized string of which all substring of size a have only b unique characters.
Consider this example :
n=17 a=5 b=3
So take any unique characters for b, say b_pattern = "abc" or "wdf" or anything, make sure they are unique for length b
Now make a string of a characters by repeating b, So a_pattern = "abcab"
Now make a string of n characters by repeating a, So final_anwser = "abcabcabcabcabcab"
Now you have made sure that a_pattern contains only b unique characters as it is made from b_pattern
So when you consider all substring of final_answer you will see that there are only b unique characters
For above testcase, substring like :
from [0:5] = "abcab" {a_count=2, b_count=2, c_count=1}
from [1:6] = "bcabc" {a_count=1, b_count=2, c_count=2}
from [2:7] = "cabca" {a_count=2, b_count=1, c_count=2}
from [3:8] = "abcab" which is equal to 1st substring, so there is repeating pattern in substring also, so we conclude thatfrom this approach our answer will be correct
Now in case of its implementation we don't need any counters or etc, we just now care for n and b,
create b_string, repeat it for n/b times in final answer and append n%b characters in final answer
This is my submission for python 3 : 76678117
Hi Yash,
Thanks a lot for making it simple. :)
I was afraid that I may have made it complex but works for you...Well wish you great codeforces journey! :)
No :P
I made this problem so complex in my head that I started thinking solutions using complex methods.
Anyways, as it was my first contest and I saw you have quite good ratings. Hard work!
I would like to ask that though the contest was for Div-3, it has problems A, B, C..in the order of increasing difficulty and meanwhile I practiced only A and B level problems on the problem page.
What was your strategy, in the beginning, should I go ahead and try to solve D,C..E level problems of the contest or get back to problem page.
Thanks
Well I am a beginner just like you...
For consistency, I daily do A, B problems from recent contests and follow editorials if not able to solve...
Meanwhile, I learn new DS and algorithms and solve problems of that kind
When I will feel that I am comfortably able to solve A, B then I will leave my comfort zone by daily practicing harder problems...this technique works for me but you should use whatever you feel right! :)
Just make sure you strengthen your DS and algorithms.
Editorial of problem F is awesome!!
I didn't get it. could you explain with more details?
How to solve E1 with Top down dp?
For problem E I tested my code on various editors for test one they gave correct answer,,, but codeforce gives this error in 1st test case itself ??Why can any one explain????
Solution link:https://codeforces.net/contest/1335/submission/76633420
Diagnostics detected issues [cpp.g++17-drmemory]: Dr,2020-04-14.M Dr. Memory version 1.11.0
Dr,2020-04-14.M Running "program.exe"
This application has requested the Runtime to terminate it in an unusual way. Please contact the application's support team for more information.
C:/Programs/mingw-w64-7/lib/gcc/i686-w64-mingw32/7.3.0/include/c++/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index -1, but
container only holds 3 elements.
Objects involved in the operation:
sequence "this" @ 0x11357920 { type = std::__debug::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >; }Dr,2020-04-14.M
Dr,2020-04-14.M NO ERRORS FOUND:
Dr,2020-04-14.M 0 unique, 0 total unaddressable access(es)
Dr,2020-04-14.M 0 unique, 0 total uninitialized access(es)
Dr,2020-04-14.M 0 unique, 0 total invalid heap argument(s)
Dr,2020-04-14.M 0 unique, 0 total GDI usage error(s)
Dr,2020-04-14.M 0 unique, 0 total handle leak(s)
Dr,2020-04-14.M 0 unique, 0 total warning(s)
Dr,2020-04-14.M 0 unique, 0 total, 0 byte(s) of leak(s)
Dr,2020-04-14.M 0 unique, 0 total, 0 byte(s) of possible leak(s)
Dr,2020-04-14.M ERRORS IGNORED:
Dr,2020-04-14.M 2 potential error(s) (suspected false positives)
Dr,2020-04-14.M (details: K:\invoker-prod\work\codeforces6\60c583d1d5042c09b8b90fe60fe5fe0b\check-acfb434e06065bfe7c8a7fcb2d8ca975\run\DrMemory-program.exe.3432.000\potential_errors.txt)
Dr,2020-04-14.M 22 unique, 26 total, 39452 byte(s) of still-reachable allocation(s)
Dr,2020-04-14.M (re-run with "-show_reachable" for details)
Dr,2020-04-14.M Details: K:\invoker-prod\work\codeforces6\60c583d1d5042c09b8b90fe60fe5fe0b\check-acfb434e06065bfe7c8a7fcb2d8ca975\run\DrMemory-program.exe.3432.000\results.txt
Dr,2020-04-14.M WARNING: application exited with abnormal code 0x3
Can someone recommend problems similar to F?
This idea of the graph looking like cycles and ordered trees going into cycles is also found in this problem — Scheme
Notice that for problem F, once you draw the graph, you'll find that it is a bunch of components which each look like a directed cycle with some ordered trees going into them. Then for each component, the maximum number of robots you can place is equal to the cycle length in that component (since sooner or later they all end up in the cycle). Find a node in the cycle corresponding to one component and do a reverse BFS from this node and compute all distances in the component to this node. Notice that if two robots are placed at the same distance from this node modulo cycle length, they will collide after some time. So greedily try placing robots on black nodes which have different distances modulo cycle length, else place on white node.
I liked the way the 2D matrix is stored in the fastest solution of F.
problem F and if nm has the deg-th bit on, just jump from the current vertex 2deg times (set v:=nxt[v][deg]). why should i only jump if deg-th bit is on in nm ?
That solution to D. OMG.
E2 using Mo s algorithm https://codeforces.net/contest/1335/submission/76679523
could u plz explain ?? there will be approximately n2 ranges so how u solved for most frequent value in a range using mos algorithm ?? . i would be highly thankful to you if u help me.. plz help
no there will be n/2 ranges.our problem was just to find most frequent element in ranges. and these ranges are made by indexes of element having same value. consider below example
arr=[1,1,2,3,2,2,1,1] one of the range will be (consider 1-based indexing) l=2,r=7 (as first 1 and last 1 will form "a" in three block palindrome and then we just have to find max frequent element in range [index of first[1] + 1,index of last[1]-1] which will be "b")
if i am not wrong u are saying that for each k from 1 to 200 we are just traversing over size[k]/2 in the first 2 loops (summation of these k will give atmost n) and in the third loop we are checking for each k hence overall o(nk).... so if we do use mo's algo then in vector there will be atmost n (basically n/2) ranges which we can solve easily .... please do tell me if i am correct or wrong
yes u are right. we just make query structure in which we store l,r,cnt (cnt will store the 2*x, basically segment formed by "a") and then we will apply mo s algo to find max(answer to the range+cnt) for all ranges and hence overall time complexity will be (n/2+n)sqrt(n) which is basically O(n*sqrt(n))
instead of using mo you could have used prefix sum to store the frequencies of each element at each point and then you could have taken the element with max frequency.
yes u are right,for this question prefix sum approach is better because of additional constraint on count of distinct elements.
can anyone tell me whats going wrong with the code.https://codeforces.net/contest/1335/submission/76681472
Today I've got an interesting masage from codeforces: Attention!
Your solution 76548547 for the problem 1335E2 significantly coincides with solutions oleh1421/76548547, oleh1421/76549567. Such a coincidence is a clear rules violation.
Well,as you can see, both of those solutions are my, so... does this realy violates the rules?
The solution for E1 that is explained here but written in python got TLE on test 12. Is this because python is slow? What can i do to solve this in py?
Can anyone explain why this O(n) solution of Problem C was giving me TLE? https://codeforces.net/contest/1335/submission/76571599
This is because of initialization of memory to an array named r inside the while loop which has a size of 1e6 and 2nd test case has t as 1000 so you are initializing memory for 1e9 ints which I think can take time. Well you don't need 1e6 elements in array r as constraints of this problem says 1<=a[i]<=n...
Here is the solution which I modified from your source and passed tests : 76697932
Thanks for your help! But the given time limit said 1 sec per test. So in a single test I'm only initializing 1e6 int right?
In a single test there are 1<=t<=1e4 test cases.
And you are initializing memory of 1e6 per test case, which makes 1e6*1e4 = 1e10 memory initialization per test. Your code has to process a maximum of 1e4 test cases in 1 second which can lead to a heavy memory operation for 1e10 memory inits, so it would be better if you initialize your array only once in outside the loop as I did in the previous submission of yours and then just loop it through per test case for resetting its values.
Can Anyone please tell me why the complexity of E2 described above is n.AL ? I think it should be N*(AL^2).
Same issue here.
Can someone help me debug my solution for E1 https://codeforces.net/contest/1335/submission/76608293
Why am I getting Memory Limit Exceeded on E2 even though my code is logically the same as given in the tutorial (even the data structures used are the same)?
you defined
intasllisn't necessary in this case.Using ll instead of int gave me problems for the first time. Thanks for the help!
Why the time complexity of problem E2 is $$$O(n.AL)$$$? I came up with this approach but I calculated the time complexity is $$$O(n*AL^2)$$$? Anyone can help me, thanks.
I understand now thanks to this comment section
For Robots on a Grid (problem F) there is an easier, O(nm) way of finding the loops and equivalence classes:
See https://codeforces.net/contest/1335/submission/76714155
EVen i am using the same concept ,but I got a wrong answer on test 50 offile 2. https://codeforces.net/contest/1335/submission/76685166
Don't you need to consider black cells in the same equivalence class eventually collides with each other? For all black cells that are in the same equivalence class, only the ones that won't collide can be considered as robot placing candidates.
Yes, everything in a particular equivalence class will eventually collide. That is why you count the equivalence classes containing black cells, not the black cells. Each equivalence class is counted at most once.
I do not understand.
The question is for the max number of possibly used black cells. This should be the minimum of "black cells in the equivalence class" and the "size of the loop". Not?
What you may be missing is that I am creating multiple equivalence classes for each loop (as is the solution in the tutorial), one for each position in the loop. Even if there are multiple black cells in a single equivalence class one cannot use them, since robots in the same equivalence class will collide.
can anyone help me with the code for the last question. I have used dp on trees,i guess. Like the crux is i am finding the cycles and the sum of the length of the cycles is the no.of robots that can be added. Also i am trying to create equivalence classes too for the cycles so that i can find the vertex to be used to fit the robot in.
Here is the link — https://codeforces.net/contest/1335/submission/76685166
I am having a wrong answer on test case 50 of the 2nd test file.
still I cant get the logic behind three block Palindrome please help me out.. thank you in advance
As the problem says we can use at most two distinct elements. say these tow distinct elements are a and b. Then the possible combinations are aba, bab . now say we select aba as combination.
Then we will select how many a we will consider as prefix for our palindrome let this count be 2 and so total count of a should at least be 4 (we have to check this if we can or not). Let l denotes the position where we found 2nd a form the begin ant r denotes the position of 2nd a from the end. then we will count the number of b in range l+1 to r-1. The result for this aba combination will be 2 + (count of b in the l+1 to r-1 range) + 2.
In this way we can check for all combination and result be the maximum of all these results. Hope it helps.
Can someone please explain this 76572022 solution for problem F. What does st[x],val[x],len[x] mean or explaining the idea in some words would help more (I have given a quite good time still don't get it properly )
Can Anyone Please help me why I am getting runtime error on Problem E2. My code here 76738146 Edit: I changed long long to int and it worked, i still dont know why? anyone explain?
Don't define big arrays in $$$main$$$, or any other function, because a function can have much less memory than application's limits, for example if the memory limit is $$$256MB$$$, then your functions cant have more than $$$32MB$$$, and it will cause runtime error, just define your $$$dp$$$ array before main then you will get ML instead of RE :).
When using big global arrays and multiple test cases, its preferred to iterate over the part of array that you need instead of using memset, as
memset(arr, 0, sizeof arr)will fill the array with zero and it will take about $$$O(sizeof arr)$$$ time and its too much to clear the whole array for every small test case.First of all, Thanks for the tip. This will stay for life time.DeadlyCritic . You mean, by declaring long long, the memory limit of function exceeded and that is the reason of run time error? right? BTW: you are so nice for giving me the advices.
You welcome, yes the reason of run time is that, also you should use int instead of long long in this problem as the memory limits are though and you don't actually need long long. The numbers i said in my last comment are not completely right.
DeadlyCritic I am also getting MLE on test case 9, even after defining int as ll. 88900051
please tell me how the answer for prob C testcase 2 1 5 4 3 is 1
First two important lines of the problem:
The first team should consist of students with distinct skills (i.e. all skills in the first team are unique).
The second team should consist of students with the same skills (i.e. all skills in the second team are equal).
so what will the teams look like in this case ? (1,2), (3,4) excluding 5?
You mean 3 is equal to 4?, the second team should have $$$equal$$$ numbers.
no i meant 4 teams in total 1,2 and 3,4 , excluding 5th but again, we are allowed exactly 2 teams . i don't understand how we can divide a team of odd number of members in 2 equal parts . even if the ans is 1 , as in this case , repeating members are not allowed so one will be excluded in the end
You must have 2 team not 4.
if x=1 for 2 1 5 4 3 , then how are the teams formed please tell me that
Teams can be consisted of only one student no matter what is the skill of the student, any choosing two students out of this 5 students then putting one in the first team and the other in the second team will give us a valid solution(i.e $$$team1 : 2$$$ and $$$team2 : 5$$$ is valid).
@vovuh Hey, problem D was cool. Your constraint was to use at most 9 changes. I've been thinking if it is possible to do it in lesser moves (like what if someone uses the problem to give a smaller constraint?). Haven't been able to come up with anything for this version though. Do you have a proof as to why you need to make at least 9 changes? If it's possible to do it in lesser, do you have any suggestions on how to go about it? Also, if there's any obvious knowledge that I might be missing, please consider sharing.
Say you make 8 or less moves. Then there is at least one 3x3 square (or at least one row, or at least one column ...) which was unchanged, so it still has the sudoku property.
Isn't $$$O(n*200)$$$ memory too much for problem E2 since $$$n <= 2e5$$$?
Sum of n over all test cases does not exceed 2e5. So total iterations will be 200*2e5, wiz O(1e7), wiz O(n)
In fact it will take about $$$160$$$ MB memory, I've got lots of ML verdicts for the problem, as i used 2 arrays of size $$$n*200$$$ :).
Could someone explain me why are we doing this?
And how do we come up with this equation: 'a' +i%b ??
It is used to take input from a text file and dumping the corresponding output of the code in output.txt on the local machine
Ok. But where has he defined the identifier _DEBUG in the source code? Then how the redirection will take place??
https://www.geeksforgeeks.org/cpp-preprocessor-directives-set-2/
since it is not defined that's why it won't execute.If it would have been defined then if condition would have been executed
If it's not getting executed then why even bother to put it?
Because while the author is testing his/her code at his/her local system it reads input from the file("input.txt", present at his/her system) instead of user entering values himself. But to submit it doesn't have to read from any such file and have to use standard input stream(stdin) so when the author submits the code he removes the #define DEBUG line from his/her code.
Ok. So where would have the author placed the identifier DEBUG??
Have a look at this code and check the 3rd line. If you delete the third line and run it will accept integers from your terminal, otherwise it will read integers from the file https://pastebin.com/sgrCGMxw
Got it completely. Thank you so much.
Майк, держу в курсе, асимптотику неправильно посчитал на Е2. У Вас получается работает за O(MaxA ^ 2 * N), а не за O(MaxA * N)
how for E O(n^2⋅AL) algorithm pass? n^2 means 10^10 operations. about 10^8 operations takes 1 sec I guess
$$$O(n^2.AL)$$$ solution is for E1, for E2 you should solve it in $$$O(n.AL)$$$ and it's included in editorial.
O(n2.AL) solution is for E1.I know how this can pass time constraints of E1. n^2 means 10^10 operations. about 10^8 operations takes 1 sec I guess
Yes you are right, it passes E1 but not E2, the editorial's solution for E1 only works for E1, not for E2.
why O(n2.AL) solution pass E1? that's what I am asking
Oh, E1 constraints are $$$n <= 2000$$$ and $$$a_i <= 26$$$, so that $$$O(n^2.AL)$$$ will pass it, in fact the solution works much faster than $$$n^2.AL$$$ time, it will work about twice faster, then it will do less than $$$4e7$$$ operations which is fine, it actually worked in $$$70MS$$$ for me.
ohk got that didn't saw it was 2000 not 20000. thanks
t is not included in finding order of algorithm? if t got included it will be like n^3 A as t=2000
No its not like this, as the sum of $$$n$$$ over all test cases is less than or equal to $$$2000$$$, but yes the true order is $$$O(n^2.AL + t.n)$$$.
ok thanks.
If anyone could help how can I optimise my code so that it could be accepted.It is working fine but is giving TLE for #12 testcase (1 2000).
https://codeforces.net/contest/1335/submission/76779927 Thanks in advance.
Avoid using arrays, vectors, sets and other data structures in function arguments, for example you have used $$$arr$$$ as an argument for $$$getSubsequence$$$. Try using global arrays.
Nice problem set, problems E2 and F were fine even for Div.1 participants, Div.3 contests are more like global ones, having interesting problems for every participant. Job well done MikeMirzayanov and vovuh.
Hey I solved E1 using brute force and E2 I improved my code using binary search so my complexity is O( $$$nlognA_i$$$ ) where $$$A_i$$$ is the maximum value. I cant find a way to make it O( $$$nlogn$$$ ) or thats it ? the actual solution with O( $$$nlogn$$$ ) complexity? here is the part I cant get rid of which causes the $$$A_i$$$ complexity:
my full code 76745546
Your solution is actually $$$O(nlog_2n + nA_i)$$$, i didn't understand what did you binary search on, but it doesn't mean that i'm not sure about the complexity of your code, also $$$O(nlog_2nA_i)$$$ wont accept without optimizations.
Cfn somebody explian why my E2 submission passed all the tests? It is really strange.
Can somebody please explain the solution of problem E
Please explain E1/E2 i could not understand editorial.
For every alphabet 'x' do the following:
go through all possible pairs of occurences of x
consider those 2 indexes (say {i, j} ) of each pair as boundary for middle block
for each such pair, take the most frequent element within this boundary to construct the middle block of required palindrome
using prefix sum of all alphabets you can calculate size of constructed palindrome ( min(left,right) + middle + min(left,right) )
Optimisation for hard version:
you need to realise that you don't actually need to go through all pairs of alphabet, as only the minimum frequency from left OR right will contribute to answer
so just go through those pairs which satisy freq[1..i][x] == freq[j..n][x]
In problem E2 is not tutorial solution complexity is O(n*al^2)?
Amortised complexity of outer 2 loops will be O(n). So total complexity will be O(n*200)
Thanks.Got it.
If someone wants to see a small and simple implementation of F : https://codeforces.net/contest/1335/submission/77002174
Please explain what you are doing in your solution.
Thanks in advance
For problem E2. Hey, can someone please tell why am i getting a TLE error for writing a very similar code given in editorial? Here is a link to my code: https://codeforces.net/contest/1335/submission/77012506
Anti-Sudoku problem broadens our perspective towards tricky problems and was really interesting and amazing!!!....Thank You @vovuh
How to avoid MLE on F, I keep getting MLE on test 5: https://codeforces.net/contest/1335/submission/77190353
int anti-sudoku problem, I am changing diagonal elements to 9(if initially not 9) else changing to 1(initially 9). Getting WA.
Its because you need to make changes such that every 3x3 square also has one element repeated. Changing the diagonal elements doesn't do the job.
it will, because diagonal elements will get repeated number, either 9 or 1 9 8 9 1 9 3 4 6 9
blinks
How about the lower left 3x3 square? Or the upper right? It will stay untouched... (If you're changing elements along the main diagonal)
Otherwise, the lower right 3x3 square or the upper left... well you get the idea.
In problem E2 is not tutorial solution complexity is O(n*al^2)?
If anyone is interested in E2 Here is explanation with example and code
I'm getting memory limit exceeded in test case 5 for F. Submission: 77895714
The logic I've tried to implement is to break the graph into components. Each component would have some equivalent nodes which would collapse if two or more blocks from one equivalence classes are chosen simultaneously. Answer for each component should then be cycle size and no of equivalence classes which have at least one black node.
I would appreciate any input on my mistake.
Problem solved. DFS used led to stack over flow. However, BFS did not cause this problem.
Can you elaborate on your approach? It seems interesting
It has been long since this comment was made. I have looked at it now only. Have you figured it out by now?
No not yet
There are finite no of cells available. Thus, for any cell, robot starting at that cell will end up in a closed loop after some time.
The matrix can be broken down into components, with each component having cells which end up in the same closed loop.
For a component, there is one closed loop and some chains of cells leading into it. The maximum no of blocks that can be occupied for a component is equal to no of cells that part of the loop.
In order to maximize robots occupying black cells, we classify cells such that any two cells which cannot have robots placed on them simultaneously (because they will overlap in future) are assigned equal ids. Again, no of ids assigned = no of blocks part of the loop.
For every class, we take one cell (preferably black). Thus we get max no of black cells that can be occupied at the beginning.
include<bits/stdc++.h>
define ll long long
using namespace std;
int main() {
std::ios::sync_with_stdio(false); cin.tie(NULL);
ll int t; cin>>t; while(t--) { ll int n; cin>>n; vectora; for( ll int i=0;i<n;i++) { ll int k; cin>>k; a.push_back(k);
ll int maxm_count=-1; ll int dist_count=0;
for(ll int i=0;i<n;i++) { ll int x=count(a.begin(),a.end(),a[i]); s[a[i]]=x; maxm_count=max(maxm_count,x);
} dist_count=s.size(); if(dist_count<maxm_count) cout<<dist_count<<endl;
else if(dist_count==maxm_count) { cout<<maxm_count-1<<endl; } else { cout<<maxm_count<<endl;
}
} }
why time limit exceeded
Well, your code exceeded the time limit, so you get time limit exceeded. As for why, the issue seems to be here:
counthas O(n) complexity, and since you call it n times, your code has O(n2) complexity. Since the maximum bound for n is 2 * 105, your code runs around 1010 operations, which is around 100 times too many.This can be fixed by iterating through
aand incrementings[a[i]]. Thenmaxm_countcan be calculated withmaxm_count = max(maxm_count, s[a[i]]);.Also, in the future, it helps to link your code submission instead of pasting the code. So for this post you could write 78250328 to keep it short and avoid the weird formatting that occurs when directly pasting code into a comment.
PROBLEM — E1
test case : — (1,1,3,1,5) shouldn't answer be (1,1,3,1) so length = 4 but judge gives answer as 3
please help
Could someone explain why the solution for F is supposed to be O(n*AL)? It looks like a clear O(n*AL^2) to me (O(AL)-loop inside O(n)-loop inside O(AL)-loop). I mean this approach is fast enough to get accepted anyway (I just tried), but still...
Regarding the tutorial for F, we don't need to jump exactly nm times to find the equivalence classes. Anything >= nm will do. We can just take the maximum deg(
lognm) calculated in the previous steps and derive equivalence classes from them. Of course,lognmhas to be aceil(log(nm) / log(2)).why I'm getting a runtime error in problem B? What is the problem with my code? Here's my code in python::::
Your code will work for just 1 test case. But there can be multiple test cases.;)
is there any video solution for problem E?
here is my approach for solving E2 in 200*n*log(n). 95645153; not so hard to understand.
In problem F, we don't even need to do binary lifting . We just need to check where will a robot be after pow(2,ceil(log2(n*m))) because it is guaranteed that after this many number of moves any robot is bound to enter into a cycle.
Can you share the proof ?
On the problem E2, consider the following example :
12 1 1 2 2 2 1 1 2 1 1 1 1 I run author's code that shows the answer is 9 here. But can't we take this subsequence : 1 1 2 2 2 1 1 1 1 1 1, so that the resulting answer is 11?
O(200N) complexity gives tle for E2 ??
229116617
Please don't necropost. I can see the downvotes coming to both your and my comment.
according to
the total time complexity is O(n⋅AL)
The problem with your code is either the implementation or Java is slow.
btw is it rated?
Okay
n%2==0 c=n/2-1; n%2==1 c=n/2; printf("%d\n",c);