#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Tutorial

Solution

#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;
}

1335B - Construct the String

Idea: MikeMirzayanov

Tutorial

Solution

#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;
}

1335C - Two Teams Composing

Idea: MikeMirzayanov

Tutorial

Solution

#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;
}

1335D - Anti-Sudoku

Idea: vovuh

Tutorial

Solution

#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)

Idea: MikeMirzayanov

Tutorial

Solution

#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)

Idea: MikeMirzayanov

Tutorial

Solution

#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;
}

1335F - Robots on a Grid

Idea: MikeMirzayanov

Tutorial

Solution

#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;
}

Solution (actually _overrated_, fastest 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();
	}
}

string alphabet = "abcdefghigklmnopqrstuvwxyz"; while (t--) { int n, a, b; cin >> n >> a >> b; char *s=new char[n+1]; for (int i = 0; i < n; i++) { if (i < a) { s[i] = alphabet[i % b]; } else { s[i] = s[i - a]; } }

#include<bits/stdc++.h> using namespace std ; map<int , int > m ; map<int , int >::iterator itr; int main () { int t ; cin >> t ; while(t!=0){ int n ; cin >> n ; int a[n] ; for(int j = 0 ; j < n ; j++){ cin >> a[j] ; m[a[j]]++ ; } int mx = 1; for (itr = m.begin(); itr != m.end(); ++itr) { mx = max(mx, itr->second) ; } int ans, s = m.size() ; if(s == mx ) ans = mx — 1 ; else ans = min(mx, s) ; cout << ans << "\n" ; t-- ; } return 0 ; }

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);

} map<ll int,ll int> s;

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++; //i=i+x-1;

} 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

li = [] x = 'abcdefghijklmnopqrstuvwxyz' sl, n, d = [int(x) for x in input().split()] for i in x: li.append(i) if len(li) < d: continue else: break for i in range(sl): print(li[i % d], end='')

Comments (206)

Show archived | Write comment?

Sadat999

5 years ago, # |

+32

That anti-sudoku approach is the coolest approach ever possible!!

→ Reply

scribblr

5 years ago, # ^ |

I have done that in contest! :D

manojeet24

+11

After reading the solution, I feel very stupid now. Wasted more than 1 hour for this problem. :(

Pallove

-11

O(n*200) = O(n) approach for E-1/E-2 this code

sid_rasa

4 years ago, # ^ |

Another approach for D 109670932

stillAnewBie

3 years ago, # ^ |

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.

OI_Master

-23

I like Problem D, it's really interesting.

Snoudin

-13

Idea is good, but problem is obvious.

-16

Maybe.

jhjh878787

-9

How to solve problem A ?

tusharjaiswal

learn stars and bars algorithm it will help you even if there are more than 2 variable

HeWinxin

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!

Gats

check this: 78 39 26

anirudhcode77

← Rev. 2 →

In alphabet string, you have repeated 'g' twice, hence for test case 10 10 10 It fails.

Accepted Thank you very much!

sxpg

← Rev. 4 →

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.

satyam_0751

take input char str[1000000]='abcdefghijklmnjklmnopqrstuvwxyz' and yes u repeat g twice

Dapper-Dodo

Can someone please help me with my submission for problem C? Here is the link: 76600537

Angeltapia

Check this:

1 1

aysin

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.

#include<bits/stdc++.h>
using namespace std ;
map<int , int > m ;
map<int , int >::iterator itr; 
int main ()
{
	int t ;
	cin >> t ;
	while(t!=0){
		int n ;
		cin >> n ;
		int a[n] ;
		for(int j = 0 ; j < n ; j++){
			cin >> a[j] ;
			m[a[j]]++ ;
		}
		int mx = 1; 
    	for (itr = m.begin(); itr != m.end(); ++itr) { 
			mx = max(mx, itr->second) ;
		}
		int ans, s = m.size() ;
		if(s == mx )
			ans = mx &mdash; 1  ;
		else
			ans = min(mx, s) ;
		cout << ans << "\n" ;
		t-- ;
	}
	return 0 ;
}

anshuman.singh

← Rev. 3 →

You need clear your map at the starting of each test case using m.clear()

I submitted your code 76658706

nitesh26589

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

AswatthaFei

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

BJMinhNhut

Actually, you just pass through all positions of each characters. So in total, you just pass through N elements, which means n segments. Therefore, time complexity is just O(Nk)

-7

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.

saarang

+12

Note that we are making an array of size K such that the ith element 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 to N. In the solution, we are traversing through each vector, say v, and just keeping two pointers at the ith and (v.size()-1-i)th positions 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 in O(v.size()*K). Since there are K vectors, the overrall complexity is O(v1.size()*k + v2.size()*k +.... v200.size()*k) = O(NK).

-8

I got it! The total number of all vector v is not nk but n. So the time complexity is O(nk) .

Thanks bro!

zarif_2002

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.

ncuPeterliang

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.

code_father_

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.

grandesonnerie

Problem E2 is very nice. What is the Mo's algorithm approach?

E2 was super nice and it fooled me.

bugbuster_

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!

rohan537

-6

There would be approx n^2 ranges....how can I do it with Mo's algo

92anurag

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.

ujjwalmittal

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?

geekychaser

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.

pandastic

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.

Roll_Num_56

Can someone share the Mo's algorithm approach for problem E2 ? Thanks in advance.

sohamnag01

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); }

TheScrasse

Each char has got a different ascii code. By adding i % b, you take the char with ascii code 97 + 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 % b is the remainder of i when divided by b.
For example, the string with b = 5 is
abcdeabcdeabcde...
because 'a' + 0 % 5 = 'a' + 5 % 5 = 'a', 'a' + 1 % 5 = 'b', etc.
Notice that, for each substring of length b, b different letters are printed out because the remainders are all different. So the strings of length a
- contain at least b distinct characters because they contain a string of length b
- contain at most b distinct characters because the whole string contains only b distinct characters
Hence the condition is true for each substring of length b.

Jayshil

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

Kavit_Kheni

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.

rachit901

What does AL denote in the time complexity of Problem E2?

The alphabet size which is 26 for E1 and 200 for E2.

supriyanta

In problem F solution, what fans & sans array meant for?

tsaraf

+16

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).

architrungta120

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.

nprakhar0411

You should apply multi-sourced bfs instead of dfs to assign the numbers.

DeadlyCritic

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.

stunareeb_09

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 :

$$$u$$$ and $$$v$$$ are in the same component.

$$$fs_u$$$ is equal to $$$fs_v$$$.

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.

LuciferStorms

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.

sheeban

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

yash1402_

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.

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.

manoj_269

Editorial of problem F is awesome!!

jenil1999

I didn't get it. could you explain with more details?

mkitkat

How to solve E1 with Top down dp?

rounak_0501

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?

ghoshsai5000

This idea of the graph looking like cycles and ordered trees going into cycles is also found in this problem — Scheme

+17

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.

mynk322.0

I liked the way the 2D matrix is stored in the fastest solution of F.

mohaned2014

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 ?

strugglerr

That solution to D. OMG.

rivalq

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))

aayush_bhat1999

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.

rishabhsrivastava

can anyone tell me whats going wrong with the code.https://codeforces.net/contest/1335/submission/76681472

oleh1421

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?

MoldovanAndrei

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?

ineffablekenobi

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.

shivaram_22

Can Anyone please tell me why the complexity of E2 described above is n.AL ? I think it should be N*(AL^2).

Number_72

19 months ago, # ^ |

Same issue here.

lazy_learner

Can someone help me debug my solution for E1 https://codeforces.net/contest/1335/submission/76608293

covalent_bond

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)?

Hd7

you defined int as ll isn'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

aberent

For Robots on a Grid (problem F) there is an easier, O(nm) way of finding the loops and equivalence classes:

Start by marking all cells as unvisited.
While there are unvisited cells:
- Follow the path from the first unvisited cell, marking each cell with a path number and step number. When you hit a visited cell it is either on the current path or a previous path:
  - If it is on the current path then you have found a new loop, and you know its size from the step number of the visited cell. You now have ls new equivalence classes of cells, where ls is the size of the loop. Mark each cell on the path with its equivalence class. Also, for each new equivalence class created remember whether you have found a black cell in that equivalence class.
  - If the visited cell is on an old path, then you know the equivalence class of the visited cell, so you can work back along the path working out the equivalence classes of the cells on the new path. Mark these, and check for black cells in each equivalence class.
Print the total number of equivalence classes, and the number of them that contain black cells.

See https://codeforces.net/contest/1335/submission/76714155

shubh_nitdgp

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

NerfThis

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.

spookywooky

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.

shahzebAhmad

still I cant get the logic behind three block Palindrome please help me out.. thank you in advance

fuad036

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 )

Hamelin

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.

mehulcoder

DeadlyCritic I am also getting MLE on test case 9, even after defining int as ll. 88900051

krooger

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.

supermatthew

+21

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?)

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.

_Bishop_

Isn't $$$O(n*200)$$$ memory too much for problem E2 since $$$n <= 2e5$$$?

xwx

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$$$ :).

sumitbishti

Could someone explain me why are we doing this?

#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

And how do we come up with this equation: 'a' +i%b ??

en-passant

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??

nimish4july1998

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.

tmstrixx

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.

Hritwik_gok

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.

+23

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.

immortalfox

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:

 for(int j = 1; j < 201; j++)
	if(j != ss[i])
		middle = max(middle, nm[j][index] - nm[j][i]);

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.

omg_pankaj

Can somebody please explain the solution of problem E

700

Please explain E1/E2 i could not understand editorial.

Jon.Snow

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]

Hamim99

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.

vedhant

If someone wants to see a small and simple implementation of F : https://codeforces.net/contest/1335/submission/77002174

sonusingh.nitaa

Please explain what you are doing in your solution.

Thanks in advance

barood

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

stack_overflows

Anti-Sudoku problem broadens our perspective towards tricky problems and was really interesting and amazing!!!....Thank You @vovuh

Java

How to avoid MLE on F, I keep getting MLE on test 5: https://codeforces.net/contest/1335/submission/77190353

msdy

int anti-sudoku problem, I am changing diagonal elements to 9(if initially not 9) else changing to 1(initially 9). Getting WA.

krispr

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

real.emerald

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.

walleeva

If anyone is interested in E2 Here is explanation with example and code

tusharjape007

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.

ritikagupta8734

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.

sunilkj

include<bits/stdc++.h>

qpwoeirut

Well, your code exceeded the time limit, so you get time limit exceeded. As for why, the issue seems to be here:

for (int i=0;i<n;i++) {
    int x=count(a.begin(),a.end(),a[i]);
    s[a[i]]=x;
    maxm_count=max(maxm_count,x);
}

count has O(n) complexity, and since you call it n times, your code has O(n²) complexity. Since the maximum bound for n is 2 * 10⁵, your code runs around 10¹⁰ operations, which is around 100 times too many.

This can be fixed by iterating through a and incrementing s[a[i]]. Then maxm_count can be calculated with maxm_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.

Mohsin_Bantu_cf

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

Kellanved

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...

yaswanth

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, lognm has to be a ceil(log(nm) / log(2)).

roudra323

why I'm getting a runtime error in problem B? What is the problem with my code? Here's my code in python::::

monna4335

Your code will work for just 1 test case. But there can be multiple test cases.;)

jainanshuman

4 years ago, # |

is there any video solution for problem E?

Ingenious

here is my approach for solving E2 in 200*n*log(n). 95645153; not so hard to understand.

code_warrior

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 ?

Karliver

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?