I_Love_YrNameCouldBeHere's blog

By I_Love_YrNameCouldBeHere, history, 2 months ago, In English

Happy New Year, Codeforces!

Once a user wrote me the message: "Please change my handle from I_love_Valya to I_love_Sveta, as I no longer love Valya ..." — since this is a story I have been enjoying for so many years, I decided that it's the high time to show my gratitude to Mike and actually change my handle name to I_love_[YourNameCouldBeHere]. If you actually want to be a part of my existence for 1 year, write down your name!

I will choose one of these names in 2 days and proudly change my name to I_love_[YourName]!

UPD:

Spoiler

There were a lot of good options and it was very hard to choose one, I hope no one gets upset. Having this said here are the reasons why I have chosen that name:

  1. It will make all the girls that broke up with me when I have lost expert jealous when I get expert back
  2. A lot more people actually suggested this name
  3. It is in the top 10 most upvoted comments
  4. It can mean something different from person to person
Spoiler

Sadly because CF allows up to 24 characters I had to get rid of the '[', ']' and abbreviate 'Your' :(

Read more »

 
 
 
 
  • Vote: I like it
  • +153
  • Vote: I do not like it

By I_Love_YrNameCouldBeHere, history, 4 months ago, In English

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

We hope everyone had fun and enjoyed the contest!

Video Editorial by HealthyUG

Problem A — Catching the Impostor.

Tutorial

Solution using frequency array:

Initialize an array of length $$$n$$$ with all the elements 0. This will be our frequency array. For every element we have in our list, we increase its frequency by one in the frequency array, $$$freq[arr[i]]+=1$$$. After we do this, we iterate through the frequency array and see how many elements have a frequency higher than 0 (it means they were mentioned in the list), let this number be $$$cnt$$$. Now if $$$cnt = n-1$$$ them we know for sure that who is the impostor, because all the other people are mentioned in the list. If $$$cnt ≠ n-1$$$ then we can't for sure know who is the impostor, so the answer is no.

Solution using set:

We introduce all the elements of the list in a set. A property of a set is that it doesn't contain a multiple elements of the same value. We just need to see how big the size of the set (how many distinct people are on the list). If this size is equal to n-1 then the answer is "YES", else "NO".

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

We iterate from the start and see how many carrots the first rabbit can eat, let this be $$$cnt_1$$$. We iterate from the end to see how many carrots the second rabbit can eat, let this be $$$cnt_2$$$. If $$$cnt_1 + cnt_2 > n$$$ then some carrots will be eaten by both rabbits, but this is not possible because they stop whenever they meet. The answer is $$$min(n, cnt_1+cnt_2)$$$.

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

The array we make should consist only of the median of the array (the middle element after sorting the array). If $$$n$$$ is even and there are two medians, both medians and all values between them are optimal choices.

Proof that median is the best answer

The median is an optimal choice because if $$$x$$$ (any element from the array) is smaller than the median, the sum becomes smaller by increasing $$$x$$$, and if $$$x$$$ is larger than the median, the sum becomes smaller by decreasing $$$x$$$. Hence, the optimal solution is that $$$x$$$ is the median.

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

We need to find if the difference between $$$n$$$ and $$$x$$$ is also a permutation of $$$x$$$'s digits. There are many ways to do this, and our solution is to transform $$$x$$$ and $$$n-x$$$ into strings, then sort the strings and see if they are equal. This is possible in C++ using to_string(int value) function.

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

We iterate through string $$$s$$$, and whenever we encounter a substring $$$t$$$, we add to the answer the number of unique substrings we can make using it. We can calculate this with the formula (number of characters since the start of the last encounter)$$$\cdot$$$(the number of characters until the end of the string). This is because the start of the substring must be between the start of the last $$$t$$$ substring in $$$s$$$ and the start of the $$$t$$$ substring just encountered(so we don't double count previous substrings). The end must be between the last element of this $$$t$$$ substring and the last element of string $$$s$$$.

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

Read more »

 
 
 
 
  • Vote: I like it
  • +108
  • Vote: I do not like it

By I_Love_YrNameCouldBeHere, history, 5 months ago, In English

Hello Codeforces!

ssense and I are glad to invite you to Unofficial Div 4 Round #1. The round will not be rated for any participants since it is unofficial. Sadly, We can not post the contest on the Gym Section, so you can virtually participate in the contest by clicking this link:

https://codeforces.com/contestInvitation/d477e058f265a72092af5c11074234d720a0fb5f

You will be given five tasks and two hours to solve them.The problems were created and prepared by ssense and I_Love_YrNameCouldBeHere for users with a rating range from 0 to 1400 but anyone is welcome to participate in the round!

We would like to thank everyone who was involved in the round preparation:

Even though the contest is unrated we believe it is a really good way of practice, especially for Div 4 users. We tried our best to keep the statements short and clear and we hope you will like our problems!

UPD: You can participate whenever you want, just click the link above and virtually participate.

UPD2: Tutorial will be posted September 19 by ssense.

UPD3: Editorial is out and contest is open for practice!

Editorial

Congratulations to the winners:

  1. extremum

  2. Proszek_na_ludka

  3. Denisov

  4. conqueror_of_tourist

  5. iamnifer

  6. brunomont

Read more »

 
 
 
 
  • Vote: I like it
  • +154
  • Vote: I do not like it