Home Codechef Contests 2022
Post
Cancel

Codechef Contests 2022

Febtruary

CodeChef Starters 24

Badminton Serves

Chef is playing badminton today. The service rules of this singles game of badminton are as follows:

  1. The player who starts the game serves from the right side of their court.
  2. Whenever a player wins a point, they serve next.
  3. If the server has won an even number of points during a game, then they will serve from the right side of the service court for the subsequent point.

Given the number of points P obtained by Chef at the end of the game, please determine how many times Chef served from the right side of the court.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
void solve()
{
    ll p;
    cin >> p;
    cout << p/2 + 1 << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        solve();
}

Avoid Contact

A hostel has N rooms in a straight line. It has to accommodate X people. Unfortunately, out of these X people, Y of them are infected with chickenpox. Due to safety norms, the following precaution must be taken:

  • No person should occupy a room directly adjacent to a room occupied by a chickenpox-infected person. In particular, two chickenpox-infected people cannot occupy adjacent rooms.

For example, if room 4 has a chickenpox-infected person, then nobody should occupy rooms 3 and 5. Similarly, if room 1 has a chickenpox-infected person then nobody should occupy room 2.

What’s the minimum value of N for which all the people can be accommodated in the hostel, following the above condition?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
void solve()
{
    ll x,y,ans = 0;
    cin >> x >> y;
    ans = x == y ? x+y-1 : x+y;
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        solve();
}

EVM Hacking

There are three cities and thus three EVMs. An insider told Chef that his party got A,B,C votes respectively in these three cities according to the EVMs. Also, the total number of votes cast are P,Q,R respectively for the three cities.

Chef, being the party leader, can hack at most one EVM so that his party wins. On hacking a particular EVM all the votes cast in that EVM are counted in favor of Chef’s party.

A party must secure strictly more than half of the total number of votes cast in order to be considered the winner. Can Chef achieve his objective of winning by hacking at most one EVM?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
void solve()
{
    ll a,b,c,p,q,r;
    cin >> a >> b >> c >> p >> q >> r;
    ll diff = max({p-a, q-b, r-c});
    if(diff + a + b + c > (p + q + r)/2)
    cout<<"YES\n";
    else
    cout << "NO\n";
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        solve();
}

Yet Another Constructive Problem

You are given a positive integer X which is at most 108.

Find three distinct non-negative integers A,B,C that do not exceed 109 and satisfy the following equation:

1
(A∣B)&(B∣C)&(C∣A)=X

Here, ∣ denotes the bitwise OR operator and & denotes the bitwise AND operator.

It can be shown that a solution always exists for inputs satisfying the given constraints.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
void solve()
{
    ll x;
    cin >> x;
    ll a = 0, b = x, c = b +1;
    while(c < INT_MAX){
        if(( (a|b) & (b|c) & (c|a)) == x)
            break;
        c++;    
    }
    cout << a <<" "<< b <<" "<< c <<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        solve();
}

Anti Palindrome

A (1-indexed) string S of length N is said to be anti-palindrome if, for each 1≤i≤N, Si≠S(N+1−i).

You are given a string S of length N (consisting of lowercase Latin letters only). Rearrange the string to convert it into an anti-palindrome or determine that there is no rearrangement which is an anti-palindrome.

If there are multiple rearrangements of the string which are anti-palindromic, print any of them.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

bool cmp(pair<char, ll>& a,
         pair<char, ll>& b)
{
    return a.second < b.second;
}
  

void solve()
{
    ll n;
    bool to_front = true;
    string str, front="", rear="", ans = "";
    vector<pair<char, ll> > vec;
    map<char, ll> mp;
    cin >> n >> str;
    if(n%2){
        cout << "NO\n";
        return;
    }

    
    for (auto& ch : str) {
        mp[ch]++;
    }
  
    for (auto& e : mp) {
        vec.push_back(e);
    }
  
    sort(vec.begin(), vec.end(), cmp);

    ll len = vec.size();

    if(vec[len - 1].second > n/2){
        cout << "NO\n";
        return;
    }
  
    for(ll i = 0; i <len; i++ ){
        string tmp ="";
        ll times = vec[i].second;
        char ch = vec[i].first;
        while(times--)
            tmp += ch;
        ans += tmp;
    }
    len = ans.length();

    for (ll start = 0, end = len/2 -1; start < end; start++, end--) 
        swap(ans[start], ans[end]);
    


    cout << "YES\n" <<  ans << endl;
    
}

int main()
{
    ios_base::sync_with_stdio(false);   
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        solve();
}

March

Lunchtime

A. Parallel Processing

There are N tasks waiting in line to be executed. The execution time for the ith task is Ai seconds.

Chef has two processors to execute these N tasks. Both these processors work simultaneously. Each processor executes the assigned tasks one by one.

Chef assigns a prefix of these tasks to the first processor and the remaining tasks to the second processor.

For example, if there are 3 tasks, Chef can do one of the following:

  • Assign no task to the first processor. This means, the second processor will execute tasks 1,2 and 3.
  • Assign task 1 to the first processor. This means, the second processor will execute tasks 2 and 3.
  • Assign tasks 1 and 2 to the first processor. This means, the second processor will execute task 3.
  • Assign tasks 1,2 and 3 to the first processor. Thus, second processor would execute no tasks.

Find the minimum time in which all the tasks can be executed.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll solve()
{
    ll n, e, ans(0);
    cin >> n;
    vector<ll> vec;

    for(ll i=0; i<n; i++)
        {
            cin >> e;
            vec.push_back(e);
        }
    if(n == 1) return vec[0];

    if(n == 2) return max(vec[0], vec[1]);

    ll start = 1, end = n - 1;

    ll p1 = vec[0], p2 = vec[end];
    end--;

    while(start <= end){

    if(p1 < p2){
        p1 += vec[start];
        start++;
    }else{
        p2 += vec[end];
        end--;
    }

    }
    
    return max(p1, p2);

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        cout << solve() << endl;
}

B. Four Equidistant Points on a Grid

The manhattan distance between two points P1(x1,y1) and P2(x2,y2) is given by d(P1,P2)=x2−x1+y2−y1.

In other words, manhattan distance is the minimum number of moves required to reach P2 from P1 if, in each move, you are allowed to travel one unit along the X-axis or one unit along the Y-axis.

You are given an integer D. Find four points (P1,P2,P3,P4) with integer coordinates, such that:

  • The absolute value of both X and Y coordinates of all points is at most 109.
  • The manhattan distance between any pair of points is D . More formally, d(Pi,Pj)=D for all 1 ≤ i < j ≤ 4. If such set of points do not exist, print -1. If there are multiple solutions, you may print any.

  • DISTCON
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

void solve()
{
    ll d;
    cin >> d;

    if(d%2){
        cout << -1 << endl; 
        return;
    }

    cout << 0 << " " <<  d/2 << endl;
    cout << d/2 << " " <<  0 << endl;
    cout << d << " " <<  d/2 << endl;
    cout << d/2  <<  " " << d << endl;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
        solve();
}

April

Cookoff

A. Digit Sum Parities

For a positive integer M, MoEngage defines digitSum(M) as the sum of digits of the number M (when written in decimal).

For example, digitSum(1023)=1+0+2+3=6.

Given a positive integer N, find the smallest integer X strictly greater than N such that:

  • digitSum(N) and digitSum(X) have different parity, i.e. one of them is odd and the other is even.

  • DIGSMPAR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll getSum(ll n)
{
    ll sum = 0;
    while (n != 0)
    {
        sum = sum + n % 10;
        n = n / 10;
    }
    return sum;
};

ll solve()
{
    ll n, x, old_sum, new_sum;
    cin >> n;

    old_sum = getSum(n);
    n++;
    new_sum = getSum(n);

    if(old_sum%2 and new_sum%2)
    n++;

    if(old_sum%2 == 0 and new_sum%2 == 0)
    n++;

    return n;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        cout << solve() << endl;
}

B. Sticks and Rectangles

MoEngage has a bundle of N sticks. The ith stick has a length Li meters.

Find the minimum number of sticks (of any length) you need to add to the bundle such that you can construct some rectangles where each stick of the bundle belongs to exactly one rectangle and each side of a rectangle should be formed with exactly one stick.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll solve()
{
    ll n, e, ans = 0;
    unordered_map<ll, ll> ump;
    cin >> n;

    for (ll i = 0; i < n; i++)
    {
        cin >> e;
        ump[e]++;
    }

    for (auto e : ump)
        if (e.second % 2)
        {
            ans++;
            n++;
        }
    return n % 4 ? ans + 2 : ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll test;
    for (cin >> test; test--;)
        cout << solve() << endl;
}

June

Starters 41

A. Break the Stick

Chef has a stick of length N.

He can break the stick into 2 or more parts such that the parity of length of each part is same. For example, a stick of length 11 can be broken into three sticks of lengths {3,3,5} since each part is odd, but it cannot be broken into two sticks of lengths {5,6} since one is even and the other is odd.

Chef can then continue applying this operation on the smaller sticks he obtains, as many times as he likes.

Can Chef obtain a stick of length exactly X by doing this?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
    ll n, x;
    cin >> n >> x;

    if (n % 2 and x%2 == 0){
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
        
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        solve();

    return 0;
}

B. Sticks and Rectangles

You are given two integers L and R(L+3≤R). Output any four distinct integers between L and R (inclusive) such that their bitwise XOR is zero.

More formally, output any four integers a1,a2,a3,a4 such that:

  • a1⊕a2⊕a3⊕a4=0
  • L≤a1,a2,a3,a4≤R
  • ai=aj if and only if i=j

If more than one such quadruple exists, you may output any of them. If no such quadruple exists, print −1 instead.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
    ll l, r;
    cin >> l >> r;

    if (l % 2)
        l++;

    if (l+3 <= r)
        cout << l << " " << l + 1 << " " << l + 2 << " " << l + 3 << endl;
    else
        cout << -1 << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        solve();

    return 0;
}

Starters 42

A. Minimum number of Flips

Chef has an array A of length N consisting of 1 and −1 only.

In one operation, Chef can choose any index i (1≤i≤N) and multiply the element Ai by −1.

Find the minimum number of operations required to make the sum of the array equal to 0. Output -1 if the sum of the array cannot be made 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll solve()
{
    ll n,i,e, sum(0);
    cin >> n;

    for (i = 0; i < n; i++)
    {
        cin >> e;
        sum += e;
    }

    sum = abs(sum);

    if(sum%2) return -1;
    return sum/2;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
    cout << solve() << endl;

    return 0;
}

B. Divisible by 3

Stack likes the number 3 a lot.

He has two non-negative integers A and B. In one operation, Stack can do either of the following:

  • A:=A−B(change A toA−B)
  • B:=A−B(change B toA−B)
**Note: ** thatXdenotes absolute value of X. For example−7=7 and4=4.

Find the minimum number of operations after which at least one integer out of A and B becomes divisible by 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll solve()
{
    ll a, b, mini, maxi;
    cin >> a >> b;
    mini = min(a%3, b%3);
    maxi = max(a%3, b%3);

    if(mini == 0) return 0;
    if(mini == 1 and maxi == 1) return 1;
    if( abs(a-b)%3 == 0) return 1;
    return 2;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        cout << solve() << endl;

    return 0;
}

C. How Many Maximums

From an array A containing N integers, you construct a binary string S of length (N−1) as follows. For all 1≤i<N:

  • If Ai<Ai+1, then Si=0.
  • If Ai>Ai+1, then Si=1.

Given the string S, determine the count of indices i (1≤i≤N) such that it is possible for Ai to be the maximum element of the array A.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll solve()
{
    ll n,i,e, ans(0);
    bool upwards = true;
    string s;
    cin >> n >> s;

    for(i=0; i<=n-2; i++){
        if(s[i] == '1') {
            if(upwards) ans++;
            upwards = false;
        } else upwards = true;

    }

    if(s[n-2] == '0' and upwards) ans++;

    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
    cout << solve() << endl;

    return 0;
}

D. Minimum or Maximum

From a hidden array A of length N, Stack constructs an array B of length N such that:

For all i (1≤i≤N), Bi=max(A1,A2,…,Ai) or Bi=min(A1,A2,…,Ai). For the given array B of length N, Stack wants you to check whether a possible array A exists or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
    ll n,i,e, maxi = INT_MIN, mini = INT_MAX;
    bool possible = true;

    cin >> n;

    for(i = 0; i<n; i++){
        cin >> e;
        mini = min(mini, e);
        maxi = max(maxi, e);
        if(e > mini and e < maxi) possible = false;
    }

    if(possible) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        solve();

    return 0;
}

Starters 44

The Attack of Knight

While playing chess, Chef noticed that it is generally advantageous for him if his knight attacks two or more of his opponent’s pieces simultaneously. To practice this skill, Chef decided to perform the following exercise:

  • Take an empty 8 \times 88×8 chessboard, and any two white pieces.

  • Choose two distinct cells $ (X_1, Y_1), (X_2, Y_2) $ and place the pieces on those cells (the cell at the intersection of the ii-th row and jj-th column is denoted (i, j)(i,j)).

  • Check if there exists an empty cell where he can place a black knight in such a way that the knight attacks both the white pieces simultaneously.

Given the position of the two white pieces $ (X_1, Y_1), (X_2, Y_2) $, print ‘YES’ if there exists an empty cell where he can place a black knight in such a way that the knight attacks both the white pieces simultaneously, otherwise print NO.

For reference, a knight attacks a piece placed in a cell that is:

  • One square horizontally and two squares vertically away from it, or
  • One square vertically and two squares horizontally away from it

  • Practice
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
unordered_map<ll, ll> mp;

void insertXY(ll x, ll y)
{

    if (x < 9 and x > 0 and y < 9 and y > 0){
        ll key = x*10 + y;
        mp[key]++;
    }
}

void allMoves(ll x, ll y)
{
    insertXY(x + 2, y + 1);
    insertXY(x + 2, y - 1);
    insertXY(x - 2, y + 1);
    insertXY(x - 2, y - 1);
    insertXY(x + 1, y + 2);
    insertXY(x - 1, y + 2);
    insertXY(x + 1, y - 2);
    insertXY(x - 1, y - 2);
}

bool solve()
{
    ll x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    allMoves(x1, y1);
    allMoves(x2, y2);

    for (auto e : mp)
        if (e.second > 1)
            return true;

    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
    {
        if (solve())
            cout << "YES\n";
        else
            cout << "NO\n";
        mp.clear();
    }
    return 0;
}

Jogging

Alice jogs everyday to keep herself fit and active. She noticed that she burns $X$ calories when jogging the first kilometer, and for $ K>1 $, jogging the $K^{th}$ kilometer burns calories equivalent to the total number of calories burned while jogging the first $K-1$ kilometers.

What is the total number of calories that Alice burns after jogging for $N$ kilometers? The answer can be very large, so report it modulo $10^9 + 7$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007

typedef long long ll;

ll myPow(ll x, ll y)
{
    if (y == 0)
        return 1;

    if (y % 2 == 0)
        return (myPow(x, y / 2) * myPow(x, y / 2)) % MOD;
    
    return (x * myPow(x, y / 2) * myPow(x, y / 2) % MOD);
}

void solve()
{
    ll n, x, rn = 0, ans = 0;

    cin >> n >> x;

    n--;

    ll y = myPow(2, n);

    cout << (x * y) % MOD << endl;
    
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        solve();
    return 0;
}

Dense Bracket Sequence

A bracket sequence SS is called dense if one of the following is true:

  • SS is empty.
  • S = (X)S=(X) where XX is dense.

You are given a bracket sequence SS. What is the minimum number of brackets you must remove to make it dense?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
        ll n;
        string s;

        cin >> n >> s;

        ll ans=0,i=0,j=n-1;

        while(i<=j)
        {
            if(s[i]=='(' && s[j]==')')
            {
                i++;
                j--;
            }
            else if(s[i]==')')
            {
                i++;
                ans++;
            }

            else if(s[j]=='(')
            {
                j--;
                ans++;
            }
        }

        cout << ans << endl;
    
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll test, sol;
    cin >> test;

    for (ll t = 0; t < test; ++t)
        solve();
    return 0;
}
This post is licensed under CC BY 4.0 by the author.

Introductory Problems | CSES

C++ | Ladder 5 | a2oj