Editorial — Codeforces Round #685

#	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	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
7	SecondThread	150
9	orz	146
10	pajenegod	145

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 - Неподстрочные подпоследовательности

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 - Равенство строк

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 - Игра в круге

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 - Битовые запросы (упрощенная версия)

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 - Битовые запросы (усложенная версия)

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 - Обнулить матрицу

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

using u32 = uint32_t; u32 n RU; // we can't use u16 because 1u << 16 will be an overflow. // First we query the xors. vector<u32> xo(n + 2, 0); // of course xo[1] = 0. for (u32 i = 2; i <= n; ++i) { cout << "XOR 1 " << i << endl; // endl to flush. xo[i] RU; } // Then we find if there are any two elements that are equal. u32 eq[2] {}; { vector<u32> used(n + 2, 0); // 0 means unused. for (u32 i = 1; i <= n; ++i) { if (used[xo[i]]) { eq[0] = used[xo[i]]; eq[1] = i; break; } used[xo[i]] = i; } } // Now we decipher a_0. u32 a0; { if (eq[0]) { cout << "OR " << eq[0] << ' ' << eq[1] << endl; a0 = ru() ^ xo[eq[0]]; } else { u32 q = find(&xo[2], &xo[n], n - 1) - &xo[0]; // Position of the complementary of a_0. u32 p = (q == 2 ? 3 : 2); cout << "AND 1 " << p << endl; u32 t1 RU; cout << "AND " << q << ' ' << p << endl; u32 t2 RU; a0 = (t1 | t2) ^ xo[p]; } } // Aha, we've found the answer. cout << "! " << a0; for (u32 i = 2; i <= n; ++i) { cout << ' ' << (a0 ^ xo[i]); } cout << endl;

Comments (126)

Show archived | Write comment?

galen_colin

3 years ago, # |

+75

If you prefer solutions in video format, here's some for A-E2 (along with the regular screencast of bricking all of the problems)

→ Reply

exalted

3 years ago, # ^ |

← Rev. 3 →

In C, is the TLE due to using python?

Edit-1: using sys.* in place of input does the job. So yeah, I guess.

Edit-2: please upvote the very useful comment below before leaving

sagarpandey7742

+14

You can use the following lambda functions to save time.

Lambda functions

iinp = lambda: int(sys.stdin.readline())

inp  = lambda: sys.stdin.readline().strip()

strl = lambda: list(inp().strip().split(" "))

intl = lambda: list(map(int, inp().split(" ")))

mint = lambda: map(int, inp().split())

flol = lambda: list(map(float, inp().split(" ")))

flush = lambda: stdout.flush()

arham_doshi

Here is hindi video editorial for A to E2, with solutions and thought process. here

KnightKnight

I wonder why you got downvotes , Nice work Bro :) Your video really helped me

+16

Nice to hear it helped you.

mogamboCodes

I almost implemented replica of E2 solution but getting WA on TC 4. 3 cases I considered. ALL unique (I got N-1 as a XOR of first and ith element), first and ith elements are same, any 2 random element are same. https://codeforces.com/contest/1451/submission/99655336

PR_0202

+62

Hope I will become CM today after 10 months of continuous contests :) .. that proves hardwork can do anything.. nice round btw ;)

ahmedash95

+12

Congrats PR_0202 you just got what you hoped :D

Thank you soo much buddy :)

ZeLon

wow you solved all the Q ...congrats buddy...a well deserved CM![user:PR_0202]

shubham7999

if in c problem z can also be converted to a then how can we do that ??

← Rev. 2 →

If we can increment 'z' to 'a' then, For every alphabet we calculate the required value of increment of frequency f[i]=(freqB-freqA).

Then if every f[i] is divisible by k and sum of all f[i] is 0. It is possible to convert the string, because the extra string (f[i]) can be converted into any charecter we want.

so in one iteration we calculate all f[i] and then check sum of all character f[i] should be 0?? so it means f[i] can also be negative??

Yes, it will be negative when you need more charecters... also check it all f[i] are divisible by k.

ohk thanks for explaining

XORring-Samurai

Hi, In today's D, I found the maximum number of moves possible, and checked its parity in order to decide the answer. But this gave me WA on pretest-5. I am unable to figure out the error. Can some one please elaborate if I have made a logical error, or some implementation error.

Link to my submission. https://codeforces.com/contest/1451/submission/99180269

Thanks a lot!!

Levi_Ackermann

+11

You probably had made a mistake in you code , because you logic is wrong but answer is right. Optimal path is not necessary the path with maximum moves but in this case it is, suppose two players are playing a game where each player turn by turn have to pick any number of stone from a pile of n stones and last person to pick the stone lose the game. Now u can clearly see that optimal strategy is not the one with maximum moves.

potato_machine

i*i could possibly lead to integer overflowing for d = 1e5 and k = 1, you should change i to long long instead of int

jughead__73

Thanks for the really fast editorial !

AyanoGod

+15

E1 E2 is really well written kudos for the awesome round :)

raj_mehta_

I miss Ashishgup's solutions in friends standings, ofcourse he can't participate in his contest XD. But yeah I learn a lot from his solutions.

ebaalhuis

+23

For E2, after (n-1) XOR queries and finding two numbers $$$a, b$$$ whose XOR is all ones (so case 2, all numbers are distinct). Can we pick a third number $$$c$$$, AND it with $$$a$$$ and $$$b$$$, the sum of those 2 outputs gives $$$c$$$ and we are done (find rest of the array with XOR that we did already)?

Dixtosa

In C I was solving for the case when the segment did not necessarily only contain the same letters. Do you guys think it is much more difficult or solvable at all?

nraghu_1547

+10

Good editorial;)

floch

+19

I wasn't able to implement in time my idea of E1, but did someone think like this too? My key idea was that given

$$$a \oplus b, b \oplus c, c \oplus a, a \& b, b \& c, \text{ and } c \& a$$$

$you$ could calculate $$$a, b$$$ and $$$c$$$. I will use this idea to calculate $$$a_1, a_2, a_3$$$. Then I will apply the XOR between $$$a_1$$$ and every other $$$a_i$$$ for $$$4 \leqslant i \leqslant n$$$, and from that I can calculate $$$a_i$$$ ($$$a \oplus b = c \Leftrightarrow b = a \oplus c$$$). This will use $$$n + 3$$$ operations, but I can fix it by using that $$$c \oplus a = (a \oplus b) \oplus (b \oplus c)$$$.

Great contest and thanks for the fast editorial btw.

GuptaJi

Can u just confirm one thing that in E1(easy version ) whether giving that n is power of 2 and nos are in range [0,n-1] is of any importance or not ?my sense is that — the solution would be same if these two constraints are not there ?Am i right or not ?

I think they are given for E2 mainly.

It doesn't depend on the numbers being in the range $$$[0: n-1]$$$ nor $$$n$$$ being a power of two. It only depends on $$$n \geqslant 3$$$.

KabirKanha

It's been a while since I enjoyed a problem set so much. Hats off.

katsurap_

[Deleted]

_aadiupadhyay_

hey, I used the same approach for E1 but got WA on pretest 4. Can anyone please have a look at my solution and tell me where I went wrong. Thanks

spunkyyogi

+22

This is how the editorials should be. Properly explaining the solution with proper reasoning.

ay21

Amazing Problemset !

dhritishman22

+24

![ ](

from Imgflip Meme Generator

)

CoderAnshu

If I am not wrong in problem D we can solve for all initial points instead of (0,0) only, i think there are only some parallel lines parallel to y = x which are losing positions and rest all are winning positions and these parallel lines can be found in O(d) time .

lemongrab

I think you are correct, we first need to set all points outside the circle to be winning position, and just evaluate point near perimeter, which gives information about the whole line.

notAnAltAccount

Looking at the graph, can't we say that a position is a losing position if there is a winning position directly above or directly right of it, and a position is winning if both the positions adjacent to it are losing?

By that logic, we can just count the number of steps played if the players go from (0,0) to the rightmost point (24,0) in this case), and then straight upwards till they can stay inside ((24,4) in this case)?

For example; d=5,k=2: (0,0)->(2,0)->(4,0)->(4,2) so we can tell if (0,0) is a winning position or not, based on the number of steps.

Yess , exactly this one . I didn't knew to attach images but this image is self explanatory . Thanks a lot for making my point clearer. We just need to set those points as losing positions which have no move available and then all other points can be retrieved by just drawing a line with slope = 1 at that point

GoatTamer

This can be proven like so: If a point (x,y) is losing, then (x-1,y) and (x,y-1) are winning. Now the point (x-1,y-1) can only go to these two points, so it is losing as well. This proves that if a point is losing all points on that diagonal are losing as well.

If a point(x,y) is winning, then it means at least one of the points (x+1,y) and (x,y+1) is losing. Let us assume it is (x+1,y) (the lower diagonal). As we have proved, that entire diagonal is losing, so all points on the diagonal of (x,y) have at least one losing state they can go to, so they are all winning.

nnv-nick

+18

Why going to the point $$$(kz, kz)$$$ in D is an optimal strategy?

It is not optimal strategy! it is what player 2 can force. If $$$(kz, k(z+1))$$$ is inside circle then also $$$(k(z+1), kz)$$$ is inside circle. If these two are winning positions then $$$(kz, kz)$$$ will be losing position.

Thank you, got it now!

blackBird

I really appreciate that solutions in Java are also provided and taken into consideration for time limits, especially for interactive problems. Thanks for the amazing round!

sharath101

-7

Imagine spending 1 and half hour for solving, coding and trying to debug a misunderstood problem.

Thats my story for E1 E2 this contest :(( Thought "XOR i j" was xor of all elements from i to j lol. Anyways the questions were really great, Thanks for the round!

codesniper99

-9

who asked?

-8

Your mom last night

-20

keep my mom out of this and I'll keep my dick out of yours

I dont care what you do with your meat. But if u are rude to me, I'll be rude in my own way

toph3110

me too

gabrielwu

+39

Here's my solution E2, which only differs from the official solution in the second case.

Find the values $$$a_1 \oplus a_2, a_1 \oplus a_3, \dots, a_1 \oplus a_n$$$ by using $$$n-1$$$ queries.

Case 1: At least one value of $$$a_1 \oplus a_2, a_1 \oplus a_3, \dots, a_1 \oplus a_n$$$ is repeated (or $$$0$$$). Treat the same as the official solution.

Case 2: The values $$$a_1 \oplus a_2, a_1 \oplus a_3, \dots, a_1 \oplus a_n$$$ contain all numbers from $$$[1, n-1]$$$. Let $$$j$$$ and $$$k$$$ satisfy $$$a_1 \oplus a_j = 1$$$ and $$$a_1 \oplus a_k = 2$$$. These must exist by pigeonhole. Now you know that $$$a_1$$$ and $$$a_j$$$ differ only on the smallest bit, so querying $$$a_1 \land a_j$$$ will get you all of the bits of $$$a_1$$$ except the last one. Similarly, the smallest bit of $$$a_1$$$ and $$$a_k$$$ must be the same, so querying $$$a_1 \land a_k$$$ will give you the last bit of $$$a_1$$$. Now you can put these two results together to reconstruct all $$$\log_2 n$$$ bits of $$$a_1$$$ and you are done in $$$n+1$$$ queries.

rguy23

I think you need to do a lot of case work since numbers can be same. Also why will $$$a_1 \oplus a_2, a1 \oplus a3,...., a_1 \oplus a_n$$$ contain all numbers from $$$[1, n-1]$$$? You can easily take some numbers same, also it is not necessary that $$$j, k$$$ such that $$$a_1 \oplus a_j = 1$$$ and $$$a_1 \oplus a_k = 2$$$ exists.

No, you don't need any casework. If some of the numbers are the same, treat it as case 1 in the official editorial solution (I didn't bother writing it because its the exact same as the editorial). Otherwise, the $$$n-1$$$ values $$$a_1 \oplus a_2, a_1 \oplus a_3, \dots, a_1 \oplus a_n$$$ are guaranteed to have all values within $$$[1, n-1]$$$ because they are all distinct.

Sir, can you please tell me on which case my solution failed. I used a similar approach. Please have a look. Thanks

ikovrigin

Is editorial for C correct? test case: 1 3 2 aaa bcb

aaa -> bba -> bcb (so answer should be possible) but code from editorial say No.

ss_loves_AC

aaa -> bba -> cca

thx i see they should be equal to increase.

the_hyp0cr1t3

all characters that are being incremented must be the same

Deuchie

I have another way to explain E2, and I want to list it here in case it may help someone else.

An important attribute of XOR operations is that it points out the differences between two binary sequences.

By XORing every $$$a_i$$$ where $$$i\in[2, n]$$$ with $$$a_1$$$, we can get an array of the differences of all other elements from $$$a_1$$$. Now, if we know what $$$a_1$$$ actually is, we will know what every element else is.

To obtain that array mentioned above, we have already used up $$$n - 1$$$ opportunities. We only have 2 left. So the problem now is how to obtain the actual value of $$$a_1$$$ in two queries.

Here we discuss two separate situations.

There are no pairs of elements in the array that have equal elements. Note that the problem tells us that all elements in the array are within the range $$$[0, n - 1]$$$. That means in this case the array is simple a permutation of $$$[0, n - 1]$$$.

Therefore, there must exist a number $$$a_i$$$ such that $$$a_1\oplus a_i=n-1$$$. That is, $$$a_i$$$ is complementary to $$$a_1$$$.

What are we talking about this for? Note that if we select any other number $$$a_j$$$ where $$$j\ne i \wedge j\ne 1$$$, we can get its actual value by two AND operations with $$$a_1$$$ and $$$a_i$$$ respectively and ORing the two parts. Also, we know that $$$a_1 \oplus a_j \oplus a_j=a_1$$$. We already have $$$a_i \oplus a_j$$$, so one XOR and we will get $$$a_1$$$. In this case we shall get the value in exactly two steps.

There exist a pair of elements in the array that has equal elements. Hey, by requesting an OR (or an AND, makes no difference) and we will get the value of the two elements. Then by XORing as described above we will get what we need. In this case we only need one step.

Okay. Now it is clear, and the only thing that's left is to show us the code:

pj423

Could somebody tell me what is wrong with my code for problem C? I am not using the frequency array approach. I think I have accounted for all the possible conditions and just cannot find what I am missing. It is giving output wrong output "Yes" for a test case in pretest 2 but since that particular test case is not visible, I don't have any clue as to what's wrong.

~~~~~ ~~~~~

Link to the code.

matheusdacach

Try removing all equal elements from both strings at the start.

BERNARD

Problem D is simply just:

Find a point $$$P(k×x,k×y)$$$ with the maximum Manhattan distance from $$$O(0,0)$$$ and an euclidean distance from it at most $$$d$$$, if its Manhattan distance is odd then the first player will win.

($$$x$$$ and $$$y$$$ are any positive integers).

manish_109

Can anyone tell me what is wrong with this approach in Question C .as i am sorting both string and checking every k substring ..it will. S1(i) will be either equal to s2(i) or if s1(i) <s2(i) then we will check for k blocks .if there is such consecutive k blocks then we will move further otherwise NO.. Link to my submission: https://codeforces.com/contest/1451/submission/99185412

SarthakBansal

Can anyone please tell me why I'm getting Idleness limit exceeded on Test 1 in E1 ? 99199797

EDIT: Got it.

Zhora_.004

Why in problem D player 2 should always go to some point such that x = y? Why is it always optimal for player 2?

hvk3

Could someone explain why the proposed solution for D does not consider points of the form (az, bz) where a and b are unequal, while considering potential terminal points for deciding the winner?

spookywooky

This is because if both play optimally, these fields will never be used.

Could you elaborate on this? I believe my question is directed towards the reason why these points are suboptimal (at least that's what I was hoping to convey).

Submit_Galactic_Algo

From what I understood, no matter who plays, they can always divert it to that maximal point

tadek

← Rev. 8 →

D can be solved with binary search and some precomputation. Basically we have the condition $$$p^2+q^2 \leqslant d^2$$$. We can introduce two integers $$$n$$$ and $$$m$$$ and write $$$p = kn$$$ and $$$q = km$$$ which gives $$$k^2(n^2+m^2)\leqslant d^2$$$. Now since the players can only increase either $$$x$$$ or $$$y$$$ then we take $$$n$$$ and $$$m$$$ for points $$$(0,1), (1,1), (1, 2), (2, 2), (2, 3), (3,3), (3,4) ...$$$. Now if we compute $$$(n^2+m^2)$$$ and sort it we get the following sequence $$$1,2,5,8,13,18,25...$$$ which is given by the general formula $$$a_l=\text{ceiling}(l^2/2)$$$. Now we can rewrite the initial condition as $$$(n^2+m^2) \leqslant d^2 / k^2$$$. Once we have all this we can precompute $$$a_l$$$ from $$$l=1$$$ to $$$l = 100000\sqrt{2}$$$, store the sequence in a sorted array and binary search this array for such an $$$l$$$ such that $$$a_l \leqslant d^2 / k^2$$$. If the found $$$l$$$ is divisible by 2 then "Utkarsh" will win otherwise "Ashish".

I tried to implement this like 11 times during the contest but had a lot of error. Only after the contest I got a passing solution. If someone is interested then here it is: 99201613

aryanc403

Initially, the problem gave $$$d^2$$$ instead of $$$d$$$. $$$1,2,5,8,13,18,25...$$$ was the reason it was changed to $$$d$$$. Funny enough there are 3 OEIS series if one tries to search for values of d at which winner changes. here. One is supposed to search using the first 24 terms to find correct OEIS series.

Also one advise don't use library ceil/floor functions. Just use integer based functions. math.floor can be replaced with // and math.ceil(a/b) can be written as (a+b-1)//b

Hmm... good point but the formula for the sequence is not necessary (although I agree that some luck is required :). I gave it since I used it in my solution but you can also precompute the sequence using the points $$$(0,1),(1,1),(1,2),...$$$. I guess it should also work.

If one notices $$$(0,1),(1,1),(1,2),..$$$ then there are 100 ways to get an AC :) . OEIS is required for those who want to get an AC without any crucial observation by just using formula written there as a BlackBox.

ankushkhanna

A simple binary search solution will work for $$$D$$$, without any precomputation. The solutions goes as follows:

Find the maximum $$$x \in \mathbb{N}$$$ such that $$$2 x^{2} k^{2} \leq d^{2}$$$. It is very simple to see that $$$x \in \Big [ 0, \frac{1}{\sqrt{2}} \frac{d}{k} \Big ] \cap \mathbb{N}$$$. For simplicity, we can drop the $$$\frac{1}{\sqrt{2}}$$$ part of our upper bound which will make everything integral.
Now, this point $$$(xk, \space xk)$$$ is the farthest point of this form which is still inside the circle. And it takes exactly $$$2x$$$ moves to reach such a point.
If any of the points $$$((x + 1)k, \space xk)$$$ or $$$(xk, \space (x + 1)k)$$$ lie inside the circle (odd moves), then Ashish wins, else (even moves) Utkarsh wins.

Time Complexity: $$$O \Big (\log_{2}{\big \lfloor \frac{d}{k} \big \rfloor} \Big )$$$
Space Complexity: $$$O(1)$$$

Here's the code: 99193957.

And it is very easy to convert this binary search solution to a constant time solution. It is easy to see that $$$x = \Big \lfloor \frac{1}{\sqrt{2}} \frac{d}{k} \Big \rfloor$$$.

Time Complexity: $$$O(1)$$$
Space Complexity: $$$O(1)$$$

Here's the code: 99270210.

sarv

A bit more explanation about Problem F please?

I understand that the logic of Nim Game works here, but why do we start out with the diagonals? What is the purpose of the diagonals?

ptd

It’s slightly more complicated than you may have expected. I suggest taking a look at problem 1149E (Election Promises) and read the explanation using game theory, and then try to prove that the nimber for each position (i, j) is (alephnull ^ (n — i + m — j)) * a[i][j] where alephnull is the smallest ordinal number.

Bojack_human

https://youtu.be/2CRJHN5-9Ks made a video on the solution of the problem D , take a look if you want to.

elvahs

I have a problem with interactive problem.

Can I use ios::sync_with_stdio(0); when I slove it?

TheeLooser

For E2, I tried all $$$\binom{\binom{4}{2} \times 3}{5}$$$ possible sets of queries, but none of them yielded a bijection ($$$f:[0,3]^4 \rightarrow [0, 3]^5$$$). What's up with this paradox?

traviscott

How can you have a bijection between 2 sets of unequal size?

Sorry, I meant injection.

Atsushi

[Solved] problem D why going to kz,kz is optimal

can't player2 move the same direction with player1? I've been thinking and trying to prove this is worse Can someone tell me? thx

Codeforcer

Say both of them move in the same direction. Now both of them already know where they will end up if they continue moving (both of them know (d/k) and hence the total moves). So the one which will be in a winning position will enjoy the walk while the one losing will try to counter by moving perpendicularly. So moving in the same direction is a contradiction and can never occur in an optimal game. This idea leads to a very easy implementation.

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 1e9;


int main(){
	fast;
	int t,n,i,j,k,d;
	cin >> t;
	while(t--){
		cin >> d >> k;
		int f=1,x=0,y=0,moves=0;
		while(x*x + y*y <= d*d){
			if(f){
				x+=k;
				f=0;
			}
			else{
				y+=k;
				f=1;
			}
			++moves;
		}
		cout<<(moves%2 ? "Utkarsh" : "Ashish")<<"\n";
		
	}	
}

Suppose Player 1 and Player 2 in their first moves move right. Now suppose that Player 1 will lose if they continue to go right so Player 1 moves up and Player 2 moves right. Now they are not in (kz, kz) position. Why this strategy is not optimal for Player 2?

ijxjdjd

For Problem F, how do we prove that the game is finite? It seems almost counterintuitive given the nature of adding to paths.

bhushanbaby

At the start of the game, the players already know the winner and loser.

The winner can make the game finite from the following strategy:

Pick any cell (i, j) to be the starting cell if the matrix with top left corner (0, 0) and bottom right corner (i, j) (excluding the cell (i, j)) contains only 0's.

Specifically, if the top left cell is not 0, a player can make it 0 by choosing it as the starting cell. In that case, that cell cannot be chosen again as the starting cell, as stated in the game rules.

Following the same pattern, a player can then recursively do the same with the rest of the matrix (starting with cells such as (0, 1) or (1, 0)).

TheScrasse

← Rev. 6 →

Let $$$s[k]$$$ be the sum of the $$$a[i][j]$$$ such that $$$i+j=k$$$.
You can prove by induction that, for every length $$$l$$$ of $$$s[]$$$, you end in a finite number of moves. It's obviously true for $$$l=1$$$.
For $$$l>1$$$, you can divide the sequence of moves in a finite number of finite segments, such that you decrease $$$s[1]$$$ only at the end of the segments. Those segments have finite length because, if you don't decrease $$$s[1]$$$, it's like having $$$l' = l-1$$$.

MyLeg

← Rev. 5 →

No matter what moves the players make, the game is going to end eventually. The reason is that whenever a cell is increased then there is a cell coming before it that is decreased. Here is a formal proof: Order the cells in a single row of length n*m such that the diagonal ordering is preserved. like this for instance

| 0 | 1 | 5 | 6 |

| 2 | 4 | 7 | 10 |

| 3 | 8 | 9 | 11 |

Let a[] be the array corresponding to this ordering (len(a) = n*m = N). Now, every single move will change a subsequence of this array so that the leftmost element that is changed is decreased by at least 1. We can do induction on both the length of a[] and the values of a[0] to prove that eventually we will have a[] = [0,0,...,0] (in other words do induction on the tuple (a[0], len(a[])) using the usual ordering of tuples). There are two cases

Eventually there is an operation involving a[0]. In this case a[0] is reduced and so we end up with a smaller tuple (a[0], len(a[])) and use induction hypothesis
No operation involves a[0]. But in this case we are effectively working on an array of length N-1. So by induction, eventually we will have a[1] = a[2] = ... a[N-1] = 0. But the only valid operation after this would involve reducing a[0]. So we again end up in case 1.

A proof that almost works, but is not correct, is to consider the array a[] as a number in base B for some large B (so a[] corresponds to the number a[N-1] + a[N-2]*B + a[N-3]*B^2 + ... a[0] * B^(N-1)) and argue that after each step the number is decreased because a leading index is decreased. However this doesn't work since we cant fix large enough B because the values of a[] can get arbitrarily large (but this does give the correct intuition). Instead we are working with the set of polynomials of degree N=n*m with non-negative integer coefficients with the natural ordering. Even though there are infinitely many polynomials less than the current one and bigger than 0, reducing the polynomial with each step still ensures we reach 0 eventually, which is interesting

alwyn

NVM

First learn C++, the command initializes with values 0 only. Also search atleast 10 times on web before commenting.

Okay I was wrong. Thanks for pointing out.

Hascii009

In D if player 2 knows that going diagonally is a losing situation, won't he just mirror player 1's move (so if 1 goes right 2 goes right and vice versa)?

If player 1 makes his first move right, then player 2 has 2 choices $$$~-$$$ move up, or move right. If he moves up, then player 1 can move right. If he moves right, then player 1 can move up. Either way, player 1 can force them to stay on the line $$$x-y=k$$$ after every turn of his. We also know that the point $$$(k(z+1), kz)$$$, which is on the line $$$x-y=k$$$ and lies inside the circle, is a losing point for player 2. So player 1 is guaranteed to win.

Is D is solvable in O(1) complexity? 99220580

tommyGunn

in order to ensure that we can make xor(r1+c1)=0 by decreasing, we select such a cell (r1,c1) whose largest set bit is equal to the largest set bit of xor(r1+c1). can someone please explain me this.

and how do we proof that game is finite.

The solution is to go through bits, and change the rest of bits after i, we subtract 2^i, and add at max 2^i-1, subtract 1 atleast. ith bit has gotta be set for property of xor.

efaraz27

Hi, In 'A' problem, I first checked if a proper divisor exists for 'n' if yes i divided 'n' with it's max proper divisor else I subtracted '1' from 'n' and repeated this process till 'n' reaches '1' while incrementing the moves counter. But this gave me WA on pretest-2 (more precisely 'n'=25). I am unable to figure out the error. Can some one please elaborate if I have made a logical error, or some implementation error.

Link to my submission. https://codeforces.com/contest/1451/submission/99135132

wsyhb

Note that even if you divide n by its max proper divisor, there may be other proper divisors after you subtract 1 from n some times. However, it is optimal to turn n into 2 first, then subtract 1 from n. If n is already an even number, there is no need to do anything. While if n is an odd number, you can subtract 1 from n first.

According the approach above, it is very easy to get the answer when n<=3, and when n>3, answer is just 2 if n is even, or 3 if n is odd.

+21

This contest is so good for its succinct statements, interestring and challenging problems without too long code, and quick but perfect editorial. Thanks for perfect preparation for this! I expect to have such contests again!

NapSaq

Guys, What is the solid proof in problem D that the second player would always have it better to return to the $$$y=x$$$ line?

codefforces

I think it's not 'always'. It's only when (kz, k(z+1)) is outside the circle, that he can and will keep returning the token to the y=x line.

If (kz, k(z+1)) is inside the circle, he would like to keep returning to the y=x+k (or x=y+k) line but he can't. On the other hand Player 1 can, regardless of Player 2's move.

You apparently misunderstood my question, Do you know why the answer is true? why isn't it that both players just go right? that's when both steps are available.

Why the $$$2nd$$$ player always wants to get back to the state where its $$$(kz,kz)$$$ ?

woon813

The 'return to the y=x line' is basically just a game strategy that can be used by both players.

If (kz,kz+k)/(kz+k,kz) is outside the circle, then the 2nd player can use this strategy to win. (if 1p move right, then 2p move up, vice versa)

If the points are inside the circle, then since 1st player's steps must always step to (0,k)/(k,0), the 1st player can use this strategy similarly (if 2p move right, then 1p move up, vice versa), which will reach (kz,kz+k)/(kz+k,kz) which is the final step of the game.

Thanks got it

jayantjha1109

Is that equation written on the first line of the solution of E1 well-known? If yes, where can I find it proof?

Muhammad98

Why this submission 99184173 in B didn't get TLE ?

silverxz

It seems not difficult after I saw the solution of F. but I just want to know how to come up with this solution...Is this a common method to solve game theory problems?

ashishdwi99

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

can someone explain me how is above code able to find two numbers with xor as n-1 without compairing all pair of numbers??

__invariant__

In problem D : I found out the maximum number of possible moves that are possible for the given 'd' value (call it mx ) .Then i output :

player 1 , if mx%2 == 1 ;
player 2 if mx%2 == 0

I think this is correct because the player who is winning according to the mx value will always be able to make the game last mx rounds(by increasing the min(x ,y) ) . I am not sure of this strategy , did someone else used this method ?

diamond786

Can someone please explain that why in problem c they add the frequency have[i] to have[i + 1] ? Thanks in advance!

We keep exactly $$$need[i]$$$ occurrences of the $$$i$$$-th character. The remainder must be converted into something else, otherwise the frequencies will not be equal. So we add $$$have[i] - need[i]$$$ to $$$have[i+1]$$$ by performing operations of the second type some number of times.

foundnt_Alice

I think the C++ code for problem D is wrong, isn't it? If you declare x,y,d to type int, it will cause "integer overflow" at some where like d*d or (x + k) * (x + k).

Thanks, it has been updated now

I am not clear with the claim in Problem E2 editorial that there will be serveral pairs (j,k) with xor N-1 ?? why is that true?

aberent

The claim is in the case where every value is different.

If every value is different, then, for each i

j ≠ k => a_i ⊕ a_j ≠ a_i ⊕ a_k

as such each i gives n different xor values (including 0, when it is xored with itself). Since n is a power of 2 we know that all the xor values with a_i must be less than n, so precisely one of the values must be n-1. We therefore have a total of n (i,j) pairs with an xor value of n-1.

Teva

P c WA 3 way ? :( https://ideone.com/65UkTo

ManInTheMiddle123

Okay, so Codeforces' anticheat system claim that my solution for problem 1451A in here is similar to user john21's solution to problem A (which you can have a look at here). And as such, they disqualify me from this contest. This is not true and I can guarantee that this is just coincidence, because, well, the solution of problem A is pretty much the same for everyone. However, my solution to problem B and john21's problem B is completely different. I think it is really unfair here because I did the entire contest on my own and still got disqualify. Can someone (admin, mod, MikeMirzayanov, etc) look into this please? Thank you very much.

janmansh

Can someone please provide an easy explanation for F? I didn't understand the editorial for F. Thank you.

rifatrraazz

Why this solution is getting WA? I couldn't find such case. Anyone can help? 99975575

Jingyuan_Li

when solveing problem E2 , I find out that it seems i must use cout rather than printf so that i can pass the test(you can check my submission 101768336 101767976). I just replace all printf with cout and i pass the test
Could anyone share with me what happened ??

crimsonred

You didn't flush the output after using printf(), whereas with cout you have used endl which automatically flushes the output.

KashishNegi

3 weeks ago, # |

In problem C, let's consider a test case: 1 5 5 abcde bcdef

// according to the given code it's answer is NO but i think it's answer is yes: because.... we can apply 2nd operation on the whole string then : a+1 = b, b+1 = c, c+1=d , d+1 = e, e+1 = f; then... bcdef.. the string can be converted.. so ans should be yes... ??

3 weeks ago, # ^ |

i got this... all elements should be equal.. i got this.. i don't read properly (or my eng. is weak)

the_hyp0cr1t3's blog