Blog entries - Codeforces

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Tutorial

Code (C++)

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

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t, n;
    cin >> t;
    while(t--) {
        cin >> n;
        cout << (n <= 3? n-1 : 2 + (n&1)) << '\n';
    }
    return 0;
}

Code (Java)

import java.util.*;
import java.util.ArrayList;
public class Main {
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i < t; i++)
        {
            int n = sc.nextInt();
            System.out.println(Math.min(2 + (n & 1), n - 1));
        }
    }
}

Idea by ridbit10

1451B - Non-Substring Subsequence

Tutorial

Code (C++)

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

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int i, n, Q; string s;
        cin >> n >> Q >> s;
        while(Q--) {
            int l, r; cin >> l >> r; --l; --r;
            bool bad = true;
            for(i = 0; i < l and bad; i++)
                if(s[i] == s[l]) bad = false;
            for(i = r+1; i < n and bad; i++)
                if(s[i] == s[r]) bad = false;
            cout << (bad? "NO" : "YES") << '\n';
        }
    }
    return 0;
}

Code (Java)

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        int t = Integer.parseInt(br.readLine());
        for(int cases = 0; cases < t; cases++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            String s = br.readLine();
            int fi[] = new int[2];
            int la[] = new int[2];
            for(int j = 0; j < 2; j++)
            {
                fi[j] = 2000000000;
                la[j] = -1;
            }
            for(int i = 0; i < s.length(); i++)
            {
                int cur = (s.charAt(i) - '0');
                fi[cur] = Math.min(fi[cur], i);
                la[cur] = i;
            }
            for(int i = 0; i < q; i++)
            {
                st = new StringTokenizer(br.readLine());
                int l = Integer.parseInt(st.nextToken()) - 1;
                int r = Integer.parseInt(st.nextToken()) - 1;
                int curl = (s.charAt(l) - '0');
                int curr = (s.charAt(r) - '0');
                if(fi[curl] < l || la[curr] > r)
                    System.out.println("YES\n");
                else
                    System.out.println("NO\n");
            }
        }
    }
}

Idea by the_hyp0cr1t3

1451C - String Equality

Tutorial

Code (C++)

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

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int i, n, k; string a, b;
        cin >> n >> k >> a >> b;
        array<int, 27> have{}, need{};
        for(auto& c: a)
            have[c-'a']++;
        for(auto& c: b)
            need[c-'a']++;
     
        bool bad = false;
        for(i = 0; i < 26; i++) {
            if(have[i] < need[i] || (have[i] -= need[i]) % k)
                bad = true;
            have[i+1] += have[i];
        }
        cout << (bad? "No" : "Yes") << '\n';
    }
    return 0;
}

Code (Java)

import java.util.*;
import java.util.ArrayList;
public class Main {
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int cases = 0; cases < t; cases++)
        {
            int n = sc.nextInt();
            int k = sc.nextInt();
            sc.nextLine();
            String a = sc.nextLine();
            String b = sc.nextLine();
            int have[] = new int[27];
            int need[] = new int[27];
            for(int i = 0; i < n; i++)
            {
                have[a.charAt(i) - 'a']++;
                need[b.charAt(i) - 'a']++;
            }
            boolean bad = false;
            for(int j = 25; j >= 0; j--)
            {
                have[j] += have[j + 1];
                need[j] += need[j + 1];
                if(have[j] > need[j] || (need[j] - have[j]) % k != 0)
                    bad = true;
            }
            if(bad)
                System.out.println("No");
            else
                System.out.println("Yes");
        }
    }
}

Idea by Ashishgup

1451D - Circle Game

Tutorial

Code (C++)

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

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int64_t d, k;
        cin >> d >> k;
        int64_t x = 0, y = 0;
        while(true) {
            if(x <= y && (x + k) * (x + k) + y * y <= d * d)
                x += k;
            else if(x > y && (y + k) * (y + k) + x * x <= d * d)
                y += k;
            else
                break;
        }
        if(x == y)
            cout << "Utkarsh" << endl;
        else
            cout << "Ashish" << endl;
    }
    return 0;
}

Code (Java)

import java.util.*;
import java.util.ArrayList;
public class Main {
    public static boolean is_within(long x, long y, long dsq, long k)
    {
        return dsq - k * k * x * x - k * k * y * y >= 0;
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int cases = 0; cases < t; cases++)
        {
            int d = sc.nextInt();
            long dsq = ((long) d) * d;
            int k = sc.nextInt();
            int cur = 0;
            while(is_within(cur + 1, cur + 1, dsq, k))
                cur++;
            if(is_within(cur + 1, cur, dsq, k))
                System.out.println("Ashish");
            else
                System.out.println("Utkarsh");
        }
    }
}

Idea by Utkarsh.25dec

1451E1 - Bitwise Queries (Easy Version)

Tutorial

Code (C++)

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
 
const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16);
 
int n, xorvals[maxn], ans[maxn];
 
void andqueries(string s, int& dest)
{
    cout << s << endl;
    cout.flush();
    cin >> dest;
    if(dest == -1)
        exit(0);
    return;
}
 
int32_t main()
{
    cin >> n;
    assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1);
    for(int i = 2; i <= n; i++)
    {
        cout << "XOR 1 " << i << endl;
        cout.flush();
        cin >> xorvals[i];
        if(xorvals[i] == -1)
            return 0;
    }
    int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3];
    int and12, and13, and23;
    andqueries("AND 1 2", and12);
    andqueries("AND 1 3", and13);
    andqueries("AND 2 3", and23);
    int x = xor12 + 2 * and12;
    int y = xor13 + 2 * and13;
    int z = xor23 + 2 * and23;
    assert((x + y - z) % 2 == 0);
    ans[1] = (x + y - z) / 2;
    for(int i = 2; i <= n; i++)
        ans[i] = (xorvals[i] ^ ans[1]);
    cout << "! ";
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
    cout.flush();
    return 0;
}

Code (Java)

import java.util.Scanner;
 
public class Main {
    public static int queries(String s, Scanner sc)
    {
        System.out.println(s);
        System.out.flush();
        int x = sc.nextInt();
        if(x == -1)
            System.exit(0);
        return x;
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int xorvals[] = new int[n + 1];
        int ans[] = new int[n + 1];
        for(int i = 2; i <= n; i++)
            xorvals[i] = queries("XOR 1 " + i, sc);
        int xor12 = xorvals[2], xor13 = xorvals[3], xor23 = xorvals[2] ^ xorvals[3];
        int and12, and13, and23;
        and12 = queries("AND 1 2", sc);
        and13 = queries("AND 1 3", sc);
        and23 = queries("AND 2 3", sc);
        int x = xor12 + 2 * and12;
        int y = xor13 + 2 * and13;
        int z = xor23 + 2 * and23;
        assert((x + y - z) % 2 == 0);
        ans[1] = (x + y - z) / 2;
        for(int i = 2; i <= n; i++)
            ans[i] = (xorvals[i] ^ ans[1]);
        System.out.print("! ");
        for(int i = 1; i <= n; i++)
            System.out.print(ans[i] + " ");
        System.out.println();
        System.out.flush();
    }
}

Idea by Ashishgup and ridbit10

1451E2 - Bitwise Queries (Hard Version)

Tutorial

Code (C++)

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;
 
const int maxn = (1ll << 16) + 5, minn = 4, maxncheck = (1ll << 16);
 
int n, xorvals[maxn], ans[maxn];
vector<int> pos[maxn];
 
int queries(string s, int i, int j)
{
    cout << s << " " << i << " " << j << endl;
    cout.flush();
    int dest;
    cin >> dest;
    if(dest == -1)
        exit(0);
    return dest;
}
 
int32_t main()
{
    cin >> n;
    assert(n >= minn && n <= maxncheck && __builtin_popcount(n) == 1);
    xorvals[1] = 0;
    pos[0].push_back(1);
    for(int i = 2; i <= n; i++)
    {
        xorvals[i] = queries("XOR", 1, i);
        pos[xorvals[i]].push_back(i);
    }
    int a = 1, b = -1, c = -1;
    int same = -1;
    for(int i = 0; i < n; i++)
        if(pos[i].size() > 1)
        {
            b = pos[i][0];
            c = pos[i][1];
            same = i;
        }
    if(same == -1)
    {
        // If a_b ^ a_c == n - 1, then a_b & a_c = 0 
        for(int i = 2; i <= 3; i++)
            for(int j = i + 1; j <= n; j++)
                if((xorvals[i] ^ xorvals[j]) == n - 1)
                {
                    b = i;
                    c = j;
                }
        int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c];
        int andab = queries("AND", a, b);
        int andac = queries("AND", a, c);
        int andbc = 0;
        int x = xorab + 2 * andab;
        int y = xorac + 2 * andac;
        int z = xorbc + 2 * andbc;
        assert((x + y - z) % 2 == 0);
        ans[a] = (x + y - z) / 2;
    }
    else
    {
        // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c)
        ans[b] = queries("AND", b, c);
        ans[1] = xorvals[b] ^ ans[b];
    }
    for(int i = 2; i <= n; i++)
        ans[i] = (xorvals[i] ^ ans[1]);
    cout << "! ";
    for(int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
    cout.flush();
    return 0;
}

Code (Java)

import java.util.*;
import java.util.ArrayList;
public class Main {
    public static int queries(String s, int i, int j, Scanner sc)
    {
        System.out.println(s + " " + i + " " + j);
        System.out.flush();
        int x = sc.nextInt();
        if(x == -1)
            System.exit(0);
        return x;
    }
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> pos[] = new ArrayList[n + 1];
        for(int i = 0; i <= n; i++)
            pos[i] = new ArrayList<Integer>();
        int xorvals[] = new int[n + 1];
        int ans[] = new int[n + 1];
        xorvals[1] = 0;
        pos[0].add(1);
        for(int i = 2; i <= n; i++)
        {
            xorvals[i] = queries("XOR", 1, i, sc);
            pos[xorvals[i]].add(i);
        }
        int a = 1, b = -1, c = -1;
        int same = -1;
        for(int i = 0; i < n; i++)
        if(pos[i].size() > 1)
            {
                b = pos[i].get(0);
                c = pos[i].get(1);
                same = i;
            }
        if(same == -1)
        {
            // If a_b ^ a_c == n - 1, then a_b & a_c = 0 
            for(int i = 2; i <= 3; i++)
                for(int j = i + 1; j <= n; j++)
                    if((xorvals[i] ^ xorvals[j]) == n - 1)
                    {
                        b = i;
                        c = j;
                    }
            assert(b != -1 && c != -1);
            int xorab = xorvals[a] ^ xorvals[b], xorac = xorvals[a] ^ xorvals[c], xorbc = xorvals[b] ^ xorvals[c];
            int andab = queries("AND", a, b, sc);
            int andac = queries("AND", a, c, sc);
            int andbc = 0;
            int x = xorab + 2 * andab;
            int y = xorac + 2 * andac;
            int z = xorbc + 2 * andbc;
            assert((x + y - z) % 2 == 0);
            ans[a] = (x + y - z) / 2;
        }
        else
        {
            // if a_1 ^ a_b == a_1 ^ a_c, then a_b = a_c = (a_b & a_c)
            ans[b] = queries("AND", b, c, sc);
            ans[1] = xorvals[b] ^ ans[b];
        }
        for(int i = 2; i <= n; i++)
            ans[i] = (xorvals[i] ^ ans[1]);
        System.out.print("! ");
        for(int i = 1; i <= n; i++)
            System.out.print(ans[i] + " ");
        System.out.println();
        System.out.flush();
    }
}

Idea by FastestFinger, Ashishgup and ridbit10

1451F - Nullify The Matrix

Tutorial

Code (C++)

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 105;
 
int n, m;
int a[N][N], xorsum[2 * N];
 
int32_t main()
{
    IOS;
    int t;
    cin >> t;
    while(t--)
    {
        memset(xorsum, 0, sizeof(xorsum));
        cin >> n >> m;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cin >> a[i][j];
                xorsum[i + j] ^= a[i][j];
            }
        }
        int flag = 1;
        for(int i = 1; i <= n + m; i++)
            flag &= (xorsum[i] == 0);
        if(!flag)
            cout << "Ashish" << endl;
        else
            cout << "Jeel" << endl;
    }
    return 0;
}

Code (Java)

import java.util.*;
 
public class NullifyTheMatrix {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
 
        for(int x = 0; x < t; ++x) {
            int n = sc.nextInt();
            int m = sc.nextInt();
 
            int mat[][] = new int[n][m];
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j)
                    mat[i][j] = sc.nextInt();
            }
 
            int xors[] = new int[n + m - 1];
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < m; ++j)
                    xors[i + j] ^= mat[i][j];
            }
 
            int flag = 0;
            for(int xor : xors) {
                flag |= xor != 0 ? 1 : 0;
            }
 
            if(flag == 1)
                System.out.println("Ashish");
            else
                System.out.println("Jeel");
        }
    }
}

Idea by Jeel_Vaishnav

Full text and comments »

the_hyp0cr1t3's blog