Blog entries - Codeforces

#	User	Rating
1	Benq	3650
2	Radewoosh	3648
3	tourist	3579
4	ecnerwala	3551
5	Um_nik	3494
6	Petr	3452
7	ksun48	3432
8	jiangly	3349
9	maroonrk	3338
10	Miracle03	3314

#	User	Contrib.
1	1-gon	210
2	awoo	188
3	Errichto	186
3	rng_58	186
5	SecondThread	182
6	Um_nik	176
6	Ashishgup	176
8	maroonrk	172
9	antontrygubO_o	171
10	-is-this-fft-	169

This is the editorial for the Unofficial Div 4 Round #2 by ssense SlavicG.

We hope everyone had fun and enjoyed the contest!

Problem A — Catching the Impostor.

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
int main()
{
    set<int> s;
 	int n, m;
 	cin >> n >> m;
 	for(int i = 0;i < m;i++){
 		int x;
 		cin >> x;
 		s.insert(x);
 	}
 	if(s.size() == n - 1){
 		cout << "YES";
 	}else{
 		cout << "NO";
 	}
}

Problem B — Rabbit Game

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
int main()
{
        int n;
	cin >> n;
	int a[n];
	for(int i=0;i < n;i++)
		cin >> a[i];
	int Rabbit1 = 1;
 
	for(int i = 1 ;i < n;i++)
	{
		if(a[i] >= a[i-1]){
			Rabbit1++;
		}else{
			break;
		}
	}
 
	int Rabbit2 = 1;
 
	for(int i = n-2;i>=0;i--)
	{
		if(a[i] >= a[i+1]){
			Rabbit2++;
		}else{
			break;
		}
	}
	cout << min(n , Rabbit2 + Rabbit1);
}

Problem C — Similar Arrays

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0;i < n;i++){
    	cin >> a[i];
    }
    sort(a,a+n);
    long long ans = 0;
    int median = a[n/2];
    for(int i = 0;i < n;i++){
    	ans += abs(median - a[i]);
    }
    cout << ans;
}

Problem D — Sanda's Job

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long n,m;
    cin >> n >> m;
    m-=n;
    if(m <= 0){
        cout << "NO";
        return 0;
    }
    string s = to_string(n);
    string k = to_string(m);
    sort(s.begin(), s.end());
    sort(k.begin(), k.end());
    if(k==s){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

Problem E — Count Substrings

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;

int main()
{
    string s, t;
    long long n;
    cin >> n >> s >> t;
    long long l = 0;
    long long ans = 0;
    for(int i = 0; i < n-1; i++)
    {
        if(s[i] == t[0] && s[i+1] == t[1])
        {
            long long from = i-l+1;
            long long to = n-(i+1);
            ans += from*to;
            l = i + 1;
        }
    }
    cout << ans << endl;
}

Problem F — Game on Grid

Tutorial

we can find the answer by looking at the cases depending on n % 4, or we can use a formula. In either case, below is proof of why it works.

Proof

Let's solve this problem for a more general case of rectangular grid $$$n \times m$$$, with rows and columns counted starting from $$$1$$$. Let even cell denote a cell with both even coordinates, all shown on the right drawing.

0d81a5a0260d344872ceb8c26f6ef9a07ed294ac

Consider $$$X = \left \lfloor{ \frac{n}{2} }\right \rfloor \cdot \left \lfloor{ \frac{m}{2} }\right \rfloor$$$ squares with even bottom-right corners, as shown on the left drawing. Since the squares are disjoint and Bob colors only one cell per move, he can block Alice from at most one of those $$$X$$$ squares per turn. Alice starts so she can color $$$\left \lceil{ \frac{X}{2} }\right \rceil$$$ of the $$$X$$$ squares and thus guarantee the score of $$$4 \cdot \left \lceil{ \frac{X}{2} }\right \rceil$$$, no matter what Bob does.

There are $$$X$$$, even cells. Alice covers exactly one of them per move because any possible $$$2 \times 2$$$ square contains exactly one even cell. If Bob colours an even cell every time too, they will spend $$$X$$$ moves in total to block all even cells, and then Alice won't be able to move. This way Bob can guarantee that Alice makes at most $$$\left \lceil{ \frac{X}{2} }\right \rceil$$$ moves and gets the score of $$$4 \cdot \left \lceil{ \frac{X}{2} }\right \rceil$$$.

Alice can make her score to be at least $$$4 \cdot \left \lceil{ \frac{X}{2} }\right \rceil$$$ and Bob can make Alice's score to be at most $$$4 \cdot \left \lceil{ \frac{X}{2} }\right \rceil$$$. Her score is thus exactly:

$$$A = 4 \cdot \left \lceil{ \frac{X}{2} }\right \rceil = 4 \cdot \left \lceil{ \left \lfloor{ \frac{n}{2} }\right \rfloor \cdot \left \lfloor{ \frac{m}{2} }\right \rfloor }\right \rceil$$$

Bob's score must be $$$B = n \cdot m - A$$$ because he can always finish the whole grid. We can compare $$$A$$$ with $$$B$$$ to get the answer.

Alternatively, you can consider cases depending on $$$n \bmod 4$$$ and $$$m \bmod 4$$$. For example, if $$$n = m = 4 \cdot k + 1$$$ then $$$X = 2k \cdot 2k = 4 \cdot k^2$$$ so $$$A = 4 \cdot (2 \cdot k^2) = 8 \cdot k^2$$$. That's smaller than half of full grid area $$$(4 \cdot k + 1)^2$$$ so Bob wins.

(We don't claim anything about the optimal moves of Alice and Bob. In particular, Alice doesn't have to choose exactly those squares marked on the drawing.)

Solution 1

#include "bits/stdc++.h"
using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
	    int n;
	    cin >> n;
	    if(n%4==2){
	    	cout << "Alice\n";
	    }else if(n%2==0){
	    	cout << "Draw\n";
	    }else{
	    	cout << "Bob\n";
	    }
	}
}

Solution 2

#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long n;
    cin >> n;
    long long cover = ((n / 2) * (n / 2) + 1) / 2;
    long long as = 4 * cover;
    long long bs = n * n - as;
    
    if (as == bs) cout << "Draw\n";
    else if (as < bs) cout << "Bob\n";
    else cout << "Alice\n";
}

I_Love_YrNameCouldBeHere's blog

Hello Codeforces!