Noobs Round #1 (Div. 4) Editorial

We are sorry for our many mistakes.

There Have many Solution and approach of any problem . We will discuss here only one approach for every problem which we found easy way .

Contest Announcement link : https://codeforces.com/blog/entry/83016

Previousely you could only virtually , now the contest is open for practice .

Invitation link for the contest : https://codeforces.com/contestInvitation/df49ade9db566204acd3653a7c3cacad088f6f1e

A. Square Field

Tutorial

Solution in c++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    ll l;
    cin >> l;
    ll x, y;
    cin >> x >> y;
    ll mx=max(max(max(l-x,x-1LL),y-1LL),l-y);

    cout<<mx*mx<<endl;

    return 0;
}

Idea & Tutorial & Solution : Rudro25

B. Win Or Lose

Tutorial

Solution in c++

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int a[1000005];

int main()
{
    int n, ct = 0;
    cin >> n;

    vector <int> ve;
    ve.push_back(ct);
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] == 0) ++ct;
        else{
            ve.push_back(ct);
            ct = 0;
        }
    }
    ve.push_back(ct);

    sort(ve.rbegin(), ve.rend());
    int alice = (ve[0] + 1) / 2;
    int bob = ve[0] / 2;
    bob = max(bob, ve[1]);

    if(bob >= alice) cout << "Bob" << endl;
    else cout << "Alice" << endl;

    return 0;
}

Idea : Rudro25 Tutorial & Solution : Muhammad_Saidul_Islam

C. Delete and insert

Tutorial

Solution in c++

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

#define      FastIO      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

int cnt[26];

int main(){
    FastIO

    string s;
    cin>>s;
    long long len=s.length();

    for(int i=0;i<len;i++) cnt[s[i]-'A']++;

    long long ans = 1e18;
    for(int i=1;i<=len;i++){
        long long sum = 0;
        for(int j=0;j<26;j++){
            if(cnt[j]) sum += abs(cnt[j]-i)*1ll*(j+1);
        }
        ans = min(ans, sum);
    }
    cout<<ans<<endl;

    return 0;
}

Idea : Muhammad_Saidul_Islam Tutorial & Solution : Rudro25

Muhammad_Saidul_Islam's solution with less complexity :

Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll ct[27];
int main()
{
    string st;
    cin >> st;

    for(int i = 0; i < st.size(); i++)
        ++ct[st[i] - 'A' + 1];

    ll ans = 1e17;
    for(ll i = 1; i <= 26; i++){
        ll c = 0;
        if(ct[i] > 0){
            for(int j = 1; j <= 26; j++){
                if(ct[j] != 0){
                    ll v = abs(ct[i] - ct[j]);
                    c += (v * j);
                }
            }

            ans = min(ans, c);
        }
    }

    cout << ans << endl;

    return 0;
}

D. Triple Fighting

Tutorial

Here we have make a team with x energy one with two other people greater than equal 3x energy as much as can. So its always optimal to get lowest n killed. Just sort the array .
Use two loop like below with two pointers .

  j=n+1;   
  for i=1 to i=n   
    for j=present_value to j=3*n     
       if(found two people geater than equal 3x eanergy than i-th people) ans++,j++,break;

Solution in c++

#include<bits/stdc++.h>
using namespace std;
#define   ll        long long
#define   FastIO    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

int main()
{
    FastIO

    ll n;
    cin>>n;
    n*=3;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin>>a[i];

    sort(a.begin(),a.end());

    ll ans = 0,j=n/3;
    for(ll i = 0; i < n/3; i++){
        ll cnt=0;
        for( ;j<n;j++){
            if(a[j]>=(3LL*a[i])) cnt++;
            if(cnt==2LL){
                j++,ans++; break;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Idea & Tutorial & Solution : Rudro25

E. Absolute value and divisors

Tutorial

Here we can solve it easily using k vaule . Cause max value of k is 10^3.

In the input can be contain with duplicate value but we don't need those .Cause we have to find unique pair.. So we just take the unique value by set . And store those value to a vector.Cause we can access vector index easily.
Then we use 2 loop.

   for i=1 to v.size()
      for j=i+1 to v.size()
         ll dif=v[j]-v[i] , if(dif>k) break, else if(dif%k==0) ans+=2;  // here we use +=2 cause if there have pair 
                                                       (1,5) then there have must be (5,1) pair and both are unique.

Here, the main tricks is ,, 2nd loop continue at most 10^3 time .Cause vector is sorted (we use set before) and there have not any duplicate value.. So,(v[j]-v[i]) > 10^3 before continue the 2nd loop for 10^3+1 times.
So, max complexity is(10^5 * 10^3 = 10^8) And it passed easily with time limit.

Solution in c++

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

#define      FastIO      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

int main() {
	FastIO

	int n, k;
    cin >> n >> k;
	set<int> se;
	for (int i = 1; i <= n; i++) {
		int a; cin >> a;
		se.insert(a);
	}
	vector<int> v(se.begin(), se.end());
	n = v.size();
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int d = v[j] - v[i];
			if (d > k) break;
			if (k % d == 0) {
				ans += 2;
			}
		}
	}
	cout << ans << '\n';
    return 0;
}

Idea : Muhammad_Saidul_Islam Tutorial & Solution : Rudro25

Muhammad_Saidul_Islam's solution with less complexity :

solution

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

vector <int> di;
void divisors(int x){
    for(int i = 1; i * i <= x; i++){
        if(x % i == 0){
            di.push_back(i);
            if(i * i != x) di.push_back(x / i);
        }
    }
    sort(di.begin(), di.end());
}

int main()
{
    int n, k;
    cin >> n >> k;
    divisors(k);

    vector <int> ve;
    map <int, int> mp;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(mp[a] == 0){
            ve.push_back(a);
            mp[a] = 1;
        }
    }

    sort(ve.begin(), ve.end());
    long long int ans = 0;
    for(int i = 0; i < ve.size(); i++){
        for(int j = 0; j < di.size(); j++){
            int v = ve[i] + di[j];
            if(mp[v] == 1) ++ans;
        }
    }

    cout << ans * 2 << endl;


    return 0;
}

F. Home Work

Tutorial

Solution in c++

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

#define      loser       return 0
#define      ll          long long
#define      FastIO      ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

string ss[30];

int main(){
   FastIO

   ll n;
   string s,answer;
   cin>>s;
   ll len=s.length();
   for(ll i=0;i<len;i++){
    ll ch=s[i]-'a';
    ll mx=0;
    string aux;
    for(ll j=0;j<=ch;j++){
        if((ss[j].size())>mx){
            aux=ss[j];
            mx=ss[j].size();
        }
    }
    ss[ch]=aux+s[i];
    if(ss[ch].size()>answer.size()) answer=ss[ch];
    else if(ss[ch].size()==answer.size()) answer=min(answer,ss[ch]);
   }
   cout<<answer.size()<<endl;
   cout<<answer<<endl;

  loser;
}

Idea & Tutorial & Solution : Rudro25

Comments (5)

Show archived | Write comment?

humlefool

4 years ago, # |

waiting for the next round and thanks for the editorial.

→ Reply

snorkel

Since these problems are unofficial and CF does not give them ratings, Can you mention what are them based on your experience?

dhiraj-01

← Rev. 2 →


last problem can be solved using dp => dp[N][26]
dp[i][j] => upto index i max sorted subsequence ending at char('a' + j)

state 
dp[i][j] = dp[i - 1][j]
dp[i][s[j] - 'a'] = 1 + max(dp[i - 1]['a' to s[j] - 'a'])

Code (C++)


void solve(int &T)
{
    string s;
    cin >> s;

    ll n = s.size();
    s = "#" + s;

    vector<vector<ll>> dp(n + 1, vector<ll>(26, 0));
    loop(i, 1, n + 1)
    {
        ll mx = 0;
        loop(j, 26) {
            dp[i][j] = dp[i - 1][j];
            if(j <= s[i] - 'a') {
                mx = max(mx, dp[i][j]);
            }
        }
        dp[i][s[i] - 'a'] = mx + 1;
    }

    ll len = 0;
    loop(j, 26) {
        len = max(len, dp[n][j]);
    }
    cout << len << endl;

    string ans;
    ll i = n, j = 26;
    while(len > 0)
    {
        loop(k, 0, j)
        {
            if(dp[i][k] == len and s[i] == 'a' + k)
            {
                j = k + 1;
                ans += ('a' + k);
                len--;
                break;
            }
        }
        i--;
    }
    reverse(all(ans));

    cout << ans << endl;
}

Iceberg

In problem D : Let's take this input :

1 3 3 4 6 6

The editorial solution output is 1 team, but it can be 2 like this : 1 3 4 and 3 6 6

Am I wrong ?

Giaco

4 years ago, # ^ |

$$$ 3 \times 3 \nleq 6$$$

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Rudro25's blog