Thanks for participating!
The top 5 contestants from this week's contest are:
Great job guys!
Here's the Editorial for the contest. Feedback of any kind is appreciated in the comments.
Approach 1:
Sort the array using an efficient sorting algorithm. For every element check if the next two in the array are equal to it. If you find such an element output it. Time complexity is $$$O(nlogn)$$$.
Approach 2:
Notice that elements have an upper bound of $$$n$$$, you can use an auxiliary array to store the count of each value. Go through each value and see if its count is bigger than or equal to $$$3$$$. Time complexity is $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
vector<int> cnt(n + 1, 0);
int ans = -1;
for(int i = 0; i < n; i++) {
int x; cin >> x;
if(++cnt[x] >= 3) {
ans = x;
}
}
cout << ans << endl;
}
}
Note that the columns don't affect each other, so we can solve for each column by itself.
For each column, go from the bottom to the top, and keep track of the row of the last obstacle seen; call it last. Note that initially, last$$$=n+1$$$, since we treat the floor as the $$$n+1$$$ th row of obstacles. Whenever we see a new obstacle, we should update last.
Now, if we ever see a stone, we should move it to row $$$last−1$$$, since it will be one row above the last obstacle seen (it will fall on top of it). Afterwards, we should also decrease last by $$$1$$$, because if any future stones fall on top of it, they will land on the row above this stone.
This solution works in $$$O(nm)$$$. We also accepted slower solutions that run in $$$O(n^2m)$$$ that simulate each stone falling.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n, m;
cin >> n >> m;
char g[n + 7][m + 7];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
}
}
for (int j = 0; j < m; j++) {
int last = n — 1;
for (int i = n — 1; i >= 0; i--) {
if (g[i][j] == 'o') {last = i — 1;}
else if (g[i][j] == '*') {swap(g[i][j], g[last][j]); last--;}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << g[i][j];
}
cout << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
Let's call $$$b_i$$$ local minimum if $$$b_i−1>b_i<b_i+1$$$ and local maximum if $$$b_i−1<b_i>b_i+1$$$. It's clear that in the arrangement satisfying the conditions from the statement, if $$$b_i$$$ is a local minimum, $$$b_i+1$$$ is a local maximum, and vice versa. Local minimums and local maximums will be alternating.
Then it's easy to see that such an arrangement can't exist for odd $$$n$$$. Indeed, suppose that the conditions from the statement are satisfied for $$$b_1,b_2,\dots,b_n$$$. If we suppose that $$$b_1$$$ is local minimum, we get that $$$b_2$$$ is local maximum, $$$b_3$$$ is local minimum, …, $$$b_n$$$ is local minimum, $$$b_1$$$ is local maximum. Clearly, $$$b_1$$$ can't be a local maximum and a local minimum at the same time, leading to a contradiction.
Let's now consider the case of even $$$n=2m$$$. Sort the array $$$a$$$, so that $$$a_1≤a_2≤\dots≤a_{2m}$$$. Let's show that if $$$a_i=a_i+m−1=x$$$ for some $$$2≤i≤m−1$$$, then there is no arrangement satisfying the conditions from the statement. Indeed, consider such an arrangement: we have $$$m$$$ numbers $$$x$$$, and no two of them can be adjacent, so they occupy every second position. In addition, as local maximums and local minimums are alternating, we get that all $$$x$$$ are local maximums or all $$$x$$$ are local minimums. The first would imply that $$$a_{2m}<x$$$, which isn't possible. The second would imply that $$$a_1>x$$$, which isn't possible.
It turns out that if there is no such $$$i$$$, the arrangement exists. Indeed, we can arrange numbers on the circle in the following order: ($$$a_1,a_{m+1},a_2,a_{m+2},\dots,a_m,a_{2m}$$$). Here $$$a_k<a_{m+k}>a_k+1$$$ for $$$1≤k≤m−1$$$, $$$a_{m+k}>a_k+1<a_{m+k+1}$$$ for $$$1≤k≤m−1$$$, $$$a_{2m}>a_1<a_{m+1}$$$ and $$$a_m<a_{2m}>a_1$$$.
#include <bits/stdc++.h>
using namespace std;
int n, w, t[200005];
int main()
{
ios_base::sync_with_stdio(false);
cin >> w;
while (w--) {
cin >> n;
for (int i=1; i<=n; i++) {
cin >> t[i];
}
sort(t+1, t+n+1);
int cnt=0, f=n/2;
for (int i=1; i<=n; i++) {
if (t[i]==t[f]) cnt++;
}
if (n%2 || 2*cnt>=n && t[f]==t[f+1]) {
cout << "NO\n";
} else {
cout << "YES\n";
for (int i=1; i<=f; i++) {
cout << t[i] << " " << t[i+f] << " ";
}
cout << "\n";
}
}
return 0;
}
First let's notice that the first player makes $$$\lceil \frac{n-1}{2} \rceil$$$ turns and the second one makes $$$\lfloor \frac{n-1}{2} \rfloor$$$.
So, if numbers are $$$1$$$-indexed and sorted, first player can make the answer not more than $$$\left(n−\lceil \frac{n-1}{2} \rceil\right)$$$-th by deleting maximal number every time. The second can make it not less than $$$\left(\lfloor \frac{n-1}{2} \rfloor+1\right)$$$-th.
But $$$n−\lceil \frac{n-1}{2} \rceil=\lfloor \frac{n-1}{2} \rfloor+1$$$, because $$$n−1=\lceil \frac{n-1}{2} \rceil+\lfloor \frac{n-1}{2} \rfloor$$$.
So the answer has minimal and maximal values, which are the same. So the answer is $$$\left(\lfloor \frac{n-1}{2} \rfloor+1\right)$$$-th number ascending.
Asymptotics is $$$O(n⋅log(n))$$$ or $$$O(n^2)$$$
#include <bits/stdc++.h>
using namespace std;
int a[1000];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
cout << a[(n - 1) / 2];
}
Read the statement carefully!! The given string is a palindrome.
Let's remove some index $$$i$$$ from the first half of $$$s$$$ and check whether the resulting string is a palindrome or not, the other half has the same approach. The prefix of length $$$i−1$$$ already matches with the suffix of the same length because the initial string was a palindrome, so we just need to check if $$$t=s[i+1\dots n−i+1]$$$ is a palindrome.
For $$$t$$$ to be a palindrome, $$$s_{n−i+1}$$$ should be equal to $$$s_{i+1}$$$ which was initially equal to $$$s_{n−i}$$$, again which should be equal to $$$s_{i+2}$$$ and this goes on. Here we can see that $$$s_i=s_{i+1}\dots=s_{n−i}+1$$$. So the answer is simply equal to the number of contiguous same characters in the center of the string which can be calculated in $$$O(n)$$$.
#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
void solve(){
ll n,count=1;
string s;
cin>>n>>s;
for(int i=1;i<(n+1)/2;i++){
if(s[i]!=s[i-1])count=1;
else count++;
}
if(n%2) cout<<2*count-1<<endl;
else cout<<2*count<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
Let the number of buses with two axles is $$$x$$$ and the number of buses with three axles is $$$y$$$. Then the equality $$$4x+6y=n$$$ must be true. If $$$n$$$ is odd, there is no answer, because the left part of the equality is always even. Now we can divide each part of the equality by two: $$$2x+3y=\frac{n}{2}$$$.
Let's maximize the number of buses. Then we should make $$$x$$$ as large as possible. So, we will get $$$2+\dots+2+2=\frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is even, and $$$2+\dots+2+3=\frac{n}{2}$$$ otherwise. In both cases the number of buses is $$$\lfloor \frac{n}{2} \rfloor$$$.
Now let's minimize the number of buses. So, we should make $$$y$$$ as large is possible. We will get $$$3+\dots+3+3+3=\frac{n}{2}$$$ if $$$\frac{n}{2}$$$ is divisible by $$$3,3+\dots+3+3+2=\frac{n}{2}$$$ if $$$n≡2$$$ (mod $$$3$$$), and $$$3+\dots+3+2+2=\frac{n}{2}$$$ if $$$n≡1$$$ (mod $$$3$$$). In all cases the number of buses is $$$\lceil \frac{n}{3} \rceil$$$.
Also don't forget the case $$$n=2$$$ — each bus has at least four wheels, so in this case there is no answer.
Time complexity: $$$O(1)$$$.
#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
void solve(){
ll n;
cin>>n;
if(n<4 || n%2==1){
cout<<"-1"<<endl;
return;
}
if(n%6==0) cout<<n/6<<" ";
else cout<<n/6+1<<" ";
cout<<n/4<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
Imagine that all elements of $$$a$$$ are distinct. This way, sorting $$$a$$$ in increasing order will fix the order of $$$b$$$.
If $$$b$$$ turns out sorted in a non-decreasing order, then the answer exists. Otherwise, it doesn't. To obtain the sequence of swaps, you can sort $$$a$$$ with any comparison-based sorting algorithm you want: even bubble sort will not exceed the allowed number of swaps.
What changes if $$$a$$$ has repeated elements? Distinct elements are still ordered among themselves, but now there are also blocks of equal elements. For each block, look into the corresponding values in $$$b$$$. Obviously, these have to be sorted in a non-decreasing order. Rearrange them as they should be.
In fact, this is exactly the same as sorting the sequence of pairs $$$(a_i,b_i)$$$ with a default comparator — first by $$$a_i$$$, then by $$$b_i$$$.
Since we fixed the wanted order, we can proceed with the same steps we made in a distinct case.
Overall complexity: $$$O(n\cdot log(n))$$$ or $$$O(n^2)$$$ per testcase.
#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
void solve(){
ll n,count=0;
vector<pair<int,int> >v;
cin>>n;
vector<ll> a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(a[i]>a[j]){
if(b[i]<b[j]){
cout<<"-1"<<endl;
return;
}else{
count++;
swap(a[i],a[j]);
swap(b[i],b[j]);
v.push_back(make_pair(i,j));
}
}else if(a[i]<a[j]){
if(b[i]>b[j]){
cout<<"-1"<<endl;
return;
}
}else{
if(b[i]>b[j]){
count++;
swap(b[i],b[j]);
v.push_back(make_pair(i,j));
}
}
}
}
cout<<count<<endl;
for(int i=0;i<v.size();i++) cout<<v[i].first+1<<" "<<v[i].second+1<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
The solution is to check the sum over all diagonals for each cell.
For a cell $$$(i,j)$$$ we can iterate over all elements in all its diagonals. This will be in total $$$O(max(n,m))$$$ elements.
The complexity will be $$$O(n\cdot m\cdot max(n,m))$$$.
$$$O(n\cdot m)$$$ solutions involving precomputation are also possible but aren't needed.
#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
void solve(){
ll n,m,ans=0;
cin>>n>>m;
vector<ll> k(m),a(n+m-1,0),b(n+m-1,0);
vector<vector<ll> > v(n,k);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>v[i][j];
if(j>=i) a[j-i]+=v[i][j];
else a[m-1+i-j]+=v[i][j];
b[i+j]+=v[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ll k=b[i+j]-v[i][j];
if(j>=i) k+=a[j-i];
else k+=a[m-1+i-j];
ans=max(k,ans);
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
At first, let's check wether the given table is good. If it is not then there is a row that has elements that should be replaced.
Let's say that this row is $$$a$$$ and $$$b$$$ is the sorted row $$$a$$$. Then let's find the set of positions $$$i$$$ that $$$a_i\neq b_i$$$. If there are at least $$$3$$$ such positions then the answer is $$$−1$$$ because by making a swap we remove at most $$$2$$$ such bad positions. If there are no more than $$$2$$$ such positions then let's swap the corresponding columns and check whether each row is sorted. If the table is good we found the answer. If it is not then the answer is $$$−1$$$ because we can not sort $$$a$$$ and get a good table after that.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<int>> &a) {
int n = a.size(), m = a[0].size();
vector<int> bad;
for (int i = 0; i < n && bad.empty(); i++) {
vector<int> b = a[i];
sort(b.begin(), b.end());
for (int j = 0; j < m; j++) {
if (a[i][j] != b[j]) bad.push_back(j);
}
}
if ((int)bad.size() == 0) {
cout << 1 << " " << 1 << "\n";
return;
}
if ((int)bad.size() > 2) {
cout << -1 << "\n";
return;
}
for (int i = 0; i < n; i++) {
swap(a[i][bad[0]], a[i][bad[1]]);
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
if (a[i][j] < a[i][j - 1]) {
cout << -1 << "\n";
return;
}
}
}
cout << bad[0] + 1 << " " << bad[1] + 1 << "\n";
return;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#endif
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
solve(a);
}
return 0;
}
First note that parts of the picture separated by $$$\texttt{W}$$$ are independent. That is, any stamps used on one part doesn't have any impact on the other, since a character $$$\texttt{W}$$$ means no stamp has been placed on that cell. So let's split the string by $$$\texttt{W}$$$ s (for example, with $$$\texttt{split()}$$$ method in Python), and consider the resulting strings containing only $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Call one of these parts $$$p$$$.
In the final stamp we place on $$$p$$$, we must have placed $$$\texttt{RB}$$$, so it should have both the characters $$$\texttt{R}$$$ and $$$\texttt{B}$$$. Therefore, if the string has only $$$\texttt{R}$$$ or only $$$\texttt{B}$$$, the answer is $$$\texttt{NO}$$$.
Otherwise, the answer is $$$\texttt{YES}$$$. Let's show it. As we have just shown, we must have $$$\texttt{R}$$$ next to $$$\texttt{B}$$$ for the string to be possible. Consider the way to make $$$\texttt{RBRRBBBB}$$$. The final stamp can be $$$\texttt{RBR$$$\underline{\texttt{RB}}$$$BBB}$$$. For the rest of the cells, we can make them one by one as below.
$$$\texttt{WWWWWWWW} \rightarrow \texttt{$$$\underline{\texttt{RB}}$$$WWWWWW} \rightarrow \texttt{R$$$\underline{\texttt{BR}}$$$WWWWW} \rightarrow \texttt{RB$$$\underline{\texttt{RB}}$$$WWWW} $$$,
so now we have made the prefix of the string before the final stamp. Similarly:
$$$\texttt{RBRBWWWW} \rightarrow \texttt{RBRBWW$$$\underline{\texttt{RB}}$$$} \rightarrow \texttt{RBRBW$$$\underline{\texttt{RB}}$$$B} \rightarrow \texttt{RBRB$$$\underline{\texttt{RB}}$$$BB}$$$.
Now we have made the prefix and the suffix by stamping "one character" at a time (actually, we stamp two characters, but then cover it up with another stamp).
Finally, we can put the final stamp to make the whole string.
$$$\texttt{RBRBRBBB} \rightarrow \texttt{RBR$$$\underline{\texttt{RB}}$$$BBB}$$$.
This method easily generalizes to any string. We can find the final stamp and then make the prefix and suffix one by one. The solution runs in $$$O(n)$$$.
#include <bits/stdc++.h>
typedef long long int ll;
#define ld long double
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll INF = 1e18;
void solve(){
ll n,a=0,b=0;
string s;
cin>>n>>s;
for(int i=0;i<n;i++){
if(s[i]=='R') a++;
else if(s[i]=='B') b++;
else{
if((!a && b)||(!b && a)){
cout<<"NO"<<endl;
return;
}
a=0;
b=0;
}
}
if((!a && b)||(!b && a)){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
Comments (0)
