Codeforces Round #931 (Div. 2)

Hello, Codeforces!

I invite you to participate in Codeforces Round 931 (Div. 2), which will be held on Friday, March 1, 2024 at 14:35UTC.

The round will be rated for participants with rating lower than 2100. Participants with higher rating can participate in round unofficially.

You will have 2 hours to solve 5 problems, with one of the problems having 2 versions. One or more interactive problems may occur in the round, so please read guide for interactive problems before the contest.

All problems are authored by me.

I would like to thank:

Good luck to all participants!

UPD: Score distribution: 500 — 1000 — 1500 — (1500 — 1250) — 3250

UPD2: Editorial

UPD3: Congratulations to the winners!

Div1 + Div2

Div2

• 10 days ago, # ^ | your first comment in a leap year :3

• 10 days ago, # ^ | You mean tough?

• 10 days ago, # ^ | well, I believe you my master

• 10 days ago, # ^ | ← Rev. 3 →   +2 harsh__h Thanks to all the authors for arranging the back-to-back contest.

• 9 days ago, # ^ | ruler姐姐！

• 10 days ago, # ^ | ← Rev. 5 →   0 [deleted]

  • 9 days ago, # ^ | Why downwote?

• 9 days ago, # ^ | Updated:)

• 10 days ago, # ^ | Thanks

• 9 days ago, # ^ | About to turn into aryanc404 with the missing stream links.

  • 9 days ago, # ^ | he took a break till Tuesday

• 9 days ago, # ^ | u guessed exactly btw

• 9 days ago, # ^ | don't hope again

• 9 days ago, # ^ | never hope again!

• 10 days ago, # ^ | Seems we both suffered last div2. Atb for this one!

  • 9 days ago, # ^ | That's true I guess

  • 9 days ago, # ^ | Bro i suffered this one also :(

    • 9 days ago, # ^ | :( last 2 rounds have been tough...

• 9 days ago, # ^ | Can anyone explain me why downwote?

  • 9 days ago, # ^ | Welcome to Codeforces bro

• 9 days ago, # ^ | It's easy you just have to write that that were the best problems you've ever saw in your life in comments.

  • 9 days ago, # ^ | This problems were indeed the best problems I solved in my entire life. Especially the interactive problem, I just loved it

• 9 days ago, # ^ | In many of them, the author of the question was clarifying this. I hope it will be the case this time.

• 9 days ago, # ^ | Oh, post a selfie

• 9 days ago, # ^ | There is only one author.

• 9 days ago, # ^ | Probably it's a part of Goodbye Codeforces series

• 9 days ago, # ^ | ← Rev. 2 →   0 i'm apologizing on my knees

• 9 days ago, # ^ | ← Rev. 2 →   +33 i really like it personally, even though i couldn't solve it. You may never do interactive problems if you don't encounter it in a contest

• 9 days ago, # ^ | Though I guess it would change the meaning — I suppose that by 'solo' the authors meant that unlike in D2, D1 IS NOT a two player game [as of game theory classification] (:

• 9 days ago, # ^ | ← Rev. 2 →   +3 May be to make question more easy. :)

• • 9 days ago, # ^ | Damn, seems very easy to reinvent then.

• 9 days ago, # ^ | What's wrong with this contest?

• 9 days ago, # ^ | First, observe pair . What can you say about it?

• 9 days ago, # ^ | i use 15 coins (n/15) then switch case 14 cases...(remain of divided by 15)

  • 9 days ago, # ^ | Let's call the answer of this problem . I did some experiments and found that for almost all , , but there seemed (only!) two exceptions: , and . So my solution was as follows: generate a table of up to using DP, and for calculate using the above formula. I didn't prove, but the results of experiments seemed very promising.

• 9 days ago, # ^ | I solved it in a partial DP sort of way. Calculate the least number of coins required for creating sum up until 30, beyond which the optimal way would be to first reduce the amount to below 30 by taking as many coins of 15 as possible and calculate the minimum for what's left. The main problem arises when you have 23/20 coins left, because if you blindly apply greedy you will get 15 + 6 + 1 + 1 and 15 + 3 + 1 + 1, when the optimal way is actually 10 + 10 + 3 and 10 + 10, respectively

• 9 days ago, # ^ | ← Rev. 3 →   +5 What is the maximum times you can use any number? [1, 3, 6, 10, 15] Is there any point in using 3, 3, 3, 3? Or 1, 1, 1, 1, 1, 1? Or 10, 10, 10?

  • 9 days ago, # ^ | ← Rev. 2 →   0 In some cases yes, just google unbounded knapsack it's a standard problem

    • 9 days ago, # ^ | Yes I've solved unbounded knapsack problem but in this problem we had to minimize the number of coins so I thought its best to replace 3, 3 with 6 and so on.

      • 9 days ago, # ^ | For small numbers all coins necessary. For huge only 15. For a math contest my solution is wrong, but that's how programmers do it, just precompute and forget

• 9 days ago, # ^ | Only in div. 3 and edu div. 2. You can still hack but you'd have to do it during the contest.

  • 9 days ago, # ^ | How do you do it during the contest?

    • 9 days ago, # ^ | I don't know sorry

    • 9 days ago, # ^ | First, lock a problem using lock icon visible on dashboard. Then, click on the Room tab, where you can see coders who are in your room, you can only hack among these. The locked problems here should be visible in bold format. Click on the solution of any other coder for the same problem and hack it.

• 9 days ago, # ^ | no, its rated for you

• 9 days ago, # ^ | C was really cool problem

  • 9 days ago, # ^ | yeah but, I'm terrible at geometry

    • 9 days ago, # ^ | I guess its about pattern. SO if there is only ONE mine — you can request 1,1 and if dis is less then n, we will request (n-(n-dis), 1) cause it will be on diagonal of n, else (n-(dis-n),m) then we within 2 request we can find mine. But there are two mines, so we will spend two more request, cause one mine will be on diagonal and the second mine is tricky. Maybe I complicated the solution, but anyway you can check my code.

• 9 days ago, # ^ | ← Rev. 6 →   +21 imo D2 < D1 < B < C lol though I must add that i think problem D2 was quite nice

• • 9 days ago, # ^ | You just need to change x such that MSB of Y is set in X.

    • 9 days ago, # ^ | For D2, the consider the parity of the numbers of '1's in the binary representation of . (Hint: when played optimally, the current player wins if and only if there are an even number of '1's in the binary representation of )

• 9 days ago, # ^ | there should be space between "?" and x and y.

• 9 days ago, # ^ | also you are using endl multiple times.

• 9 days ago, # ^ | You can use jdoodle for testing them, there's a separate switch to enable interactive input

• 9 days ago, # ^ | For simpler problems like C, I somehow manage to make a judge function in my local environment, but yeah for complex problems like D2 where the interactor needs to be smart, such thing would really save a lot of time.

• 9 days ago, # ^ | You are printing both (x1,y1) and (x2,y2) as answers

  • 9 days ago, # ^ | Oh, yeah, I was in a such rush that I didn't read the statement properly

• 9 days ago, # ^ | Yeah good round, thanks harsh__h

• 9 days ago, # ^ | You have to flush before taking input and after giving output, you're flushing after taking input.

  • 9 days ago, # ^ | ← Rev. 3 →   0 It wasn't accepted lmao

• 9 days ago, # ^ | XORForces

• 9 days ago, # ^ | Which problem used maths ?

  • 9 days ago, # ^ | InteractiveForces

    • 9 days ago, # ^ | Fair. I like them in general, although I always have a bad time debugging my programs. Especially this time.

• 9 days ago, # ^ | You only need to ask any three out of c1,c2,c3,c4 queries. (c1,c4) and (c2,c3) are complementary equations, so each mine satisfies exactly one of these equations. On solving the three equations, you get two solutions, exactly one of which is a mine. For the final query, you can ask the distance from either of these solutions. If the distance is zero, then it is a mine. Otherwise, the other solution is a mine.

• 9 days ago, # ^ | First find possible points from query(1,1) , query(1,n) , query(1,m). Atmost two points are possible from this. now find distance from one of the possible points . if you get response as zero then this pair is answer or other pair will be answer.

9 days ago, # | Worst day ever

• 9 days ago, # ^ | us moment... not as worse as yours yet a bad one

• 9 days ago, # ^ | At least you are not alone

• 9 days ago, # ^ | are you sure?

• 8 days ago, # ^ | it hurts

• 9 days ago, # ^ | For B, is n0 = 30 the right minimum value for it?

• 9 days ago, # ^ | For B I think that n0 = lcm(1,3,6,10,15) = 30 is the "optimal" choice

• 9 days ago, # ^ | B could be solved greedily. Grab 10 or 1 (based on the current n) until it is divided by 3, then grab 3, 6, 15 greedily for the rest. Submission

  • 9 days ago, # ^ | Explain you approach. Also why you are keeping n>= 10 ?

    • 9 days ago, # ^ | I'm not keeping n >= 10. If n < 10 then obviously I couldn't grab 10 coins.

• 9 days ago, # ^ | 249172491 I think I did what you said, but it tle on test 1, could you help me with it please?

  • 9 days ago, # ^ | ll cosas = 1; ll p1 = 0; bool usar = true; for (ll i = 0; i < 63 and cosas > 0; i ++){ if ((1LL << i) & n){ p1 ^= (1LL << i); cosas --; } } In this section p1 will be the lowest bit of n. Try to let p1 be the highest bit of n.

    • 9 days ago, # ^ | Oh I see what can happen. Now it works, thanks!

• 9 days ago, # ^ | May be I am wrong, but in problem D1 are you not using operation of type 2 ()?

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define double long double
#define endl '\n'
#define PI 3.1415926535897932384626433832795l
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const double EPS = 1e-9;
void solve()
{
    int n, m;
    cin >> n >> m;
    cout << "? 1 1" << endl;
    cout.flush();
    int d1;
    cin >> d1;
    if (d1 == 0)
    {
        cout << "! 1 1" << endl;
        cout.flush();
        return;
    }
    cout << "? 1 " << m << endl;
    cout.flush();
    int d2;
    cin >> d2;
    if (d2 == 0)
    {
        cout << "! 1 " << m << endl;
        cout.flush();
        return;
    }
    cout << "? " << n << " " << 1 << endl;
    cout.flush();
    int d3;
    cin >> d3;
    if (d3 == 0)
    {
        cout << "! " << n << " 1" << endl;
        cout.flush();
        return;
    }

    int x1 = ((d1 + d2 - n) + 1) / 2;
    int y1 = d1 - x1;
    int x2 = ((d1 + d3 - m) + 1) / 2;
    int y2 = d1 - x2;
    if (x1 + 1 > 0 && y1 + 1 > 0)
    {
        cout << "? " << y1 + 1 << " " << x1 + 1 << endl;
        cout.flush();
        int d4;
        cin >> d4;
        if (d4 == 0)
        {
            cout << "! " << y1 + 1 << " " << x1 + 1 << endl;
        }
        else
        {
            cout << "! " << y2 + 1 << " " << x2 + 1 << endl;
        }
        cout.flush();
    }
    else
    {
        cout << "? " << y2 + 1 << " " << x2 + 1 << endl;
        cout.flush();
        int d4;
        cin >> d4;
        if (d4 == 0)
        {
            cout << "! " << y2 + 1 << " " << x2 + 1 << endl;
        }
        else
        {
            cout << "! " << y1 + 1 << " " << x1 + 1 << endl;
        }
        cout.flush();
    }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

• 9 days ago, # ^ | You should either provide a link or use a spoiler, and you're not even telling us which problem. :(

• 9 days ago, # ^ | int x1 = ((d1 + d2 - n) + 1) / 2; int y1 = d1 - x1; int x2 = ((d1 + d3 - m) + 1) / 2; int y2 = d1 - x2; This might be where it is going wrong. You will need to check whether the two lines actually intersect or not by performing modulo 2, I made the same mistake in my first submission.

  • 9 days ago, # ^ | I got your point. Thanks

• 9 days ago, # ^ | Bro sent the code as a spoiler or as a link

• 9 days ago, # ^ | Maybe you don't even output an answer

1000100010101010101
|   |   |
0   0   1
 000 000 [anything]

• 9 days ago, # ^ | Yup, same (I actually got the solution with 2 operations for one case, but since there were 63 operations, I thought that there would probably be some "change bits one by one" sort of solution).

• 9 days ago, # ^ | ← Rev. 2 →   +3 It can be proven that after n = 23 there is no combination where you shouldn't use 15 coins. So we always use 15 coins before we get to the 23 (or less) left, where we can brute force the correct combination.

  • 9 days ago, # ^ | do you have a formal proof for that?

• 9 days ago, # ^ | You can. But u'll get TLE.

• 9 days ago, # ^ | Nope, the simple DP won't work, because the limit of is too large -- you can't create a table with elements. You need to find a way to calculate the answer for a large , which is the core of this problem.

  • 9 days ago, # ^ | I'm learning basics of dp now like knapsack problems but still in the basic ones so do you recommend trying this problem to learn something helpful ?

• 9 days ago, # ^ | Compiling with -fsanitize=undefined can catch these types of overflow errors, just so you know

• 9 days ago, # ^ | ← Rev. 3 →   0 Never mind, I got it, few of my queries were going out of bound.

• 9 days ago, # ^ | C is harder than D1 imo

  • 9 days ago, # ^ | B is harder than c imo

    • 9 days ago, # ^ | How come 9k users solved it?

      • 9 days ago, # ^ | cheating exist

• 9 days ago, # ^ | sorry to say, but your code is not that clean. Writing clean code is important, as it can save time and make it easier for others to find and fix errors. In general, if your code is messy, people may not even bother to look at it.

  • 9 days ago, # ^ | Thanks for letting me know, I will try improving on this, any tips?

    • 9 days ago, # ^ | remove unusual functions and store them to somewhere else. use functions only when it's necessary. In addition, try to learn C++ properly. java isn't suitable for problem solving.

• 9 days ago, # ^ | First is not correct for cases like 15005 where you use 1000 15s, 3, 1, 1. Instead of 15,3,1,1 use 10,10.

• 9 days ago, # ^ | What is your solution for c?

  • 9 days ago, # ^ | ← Rev. 2 →   +3 If we set the the point (1,1) as fixed and ask(1,1) then we will get the nearest point to (1,1) now one of the following (1,m) or (n,1) must have the same near point no we have d1 = ask(1,1) d2 = ask(1,m) d3 = ask(n,1) let (x,y) is the our point that can be obtained from d1,d2 now ask(x,y) if the result is zero then this is the point else we have to take (x,y) with respect to ask(1,1) , ask(n,1) How to obtain a possible (x,y) from two queries you can solve equation of two variables form any two of the following : d1 = (x-1) + (y-1) d2 = (x-1) + (m-y) d3 = (n-x) + (y-1) You can have a look on my submission that also have some comments that may help you 249181821 upvote if that helps you <3

    • 9 days ago, # ^ | Thanks Note that the third equation is not correct It should be d3 = (n-x) + (y-1)

def solve():
    n = inp()
 
    coins = [1, 3, 6, 10, 15]
    ans = float('inf')
 
    def dfs(num, index, curr):
        nonlocal ans
        if num == 0:
            ans = min(ans, curr)
            return
        if index == 0:
            ans = min(ans, curr + num)
            return
 
        c = coins[index]
        for i in range(index):
            k = num // c
            dfs(num - (c * k), i, curr + k)
            if k > 1:
                dfs(num - (c * (k - 1)), i, curr + (k - 1))
 
    for j in range(len(coins)):
        dfs(n, j, 0)
    return ans

• 9 days ago, # ^ | I don't exactly know how your solution works, but I think it's really cool because it works in the time limit and it doesn't involve hard-coding some magic values...

• 9 days ago, # ^ | Nice solution. Can you please explain how you did this?

  • 9 days ago, # ^ | ← Rev. 2 →   0 it pretty much generates 'all the possibilities' and takes the minimum of those possiblities, it even calculates the possibility when the number of coins is max lol, for the base cases : if num == 0 that means the the sum of coins we have is equal to original n and the number of those coins is (curr) so with we take that curr if it's inferior to our current minimum (ans) if index = 1 that means we are at coin = 1 so we take what left of original n and add it to the current number of coins than update the ans if it's inferior the loop inside the dfs function will call dfs recursively with what's left of n after taking the max possible number of coins with current coin (c) k = num //c add that number to the current number of coins we have (curr+k) and pass that number and what's left of n to coins with value inferior than the current coin, so for example at 3: we will pass the same (what's left of n and curr+k) to coin 1, at 6 we will pass them to 3 and 1 at 10 we will pass them to 6,3,1 and we will calculate until we reach the base case , and update the minimum for the second dfs call inside the loop dfs(num — (c * (k — 1)), i, curr + (k — 1)) it takes care of the possibility where i can replace 1 coin of 15 with x coins , of any coins with value inferior to it and if such possibility provides an inferior curr it will be updated in the ans, like the case for number 98 **it better to take 98 = 15 * 5 + 10 * 2 + 3 * 1 = 8 coins , than 98 = 15 * 6 + 6 * 1 + 1 * 2* = 9 coins The outside loop that calls the dfs for j in range(len(coins)): dfs(n, j, 0) is for the possibility when the original n is directly divisible by any coin , like the case of 20 , if i don't call dfs in a loop and call it only on 15 or index= 4 in my case it will return 20 = 15*1 + 3 * 1 + 1* 2 = 4 coins, because if i call it only on 15 the 20 will never reach coin = 10 untouched , it will reach coin = 10 with the value 5 = 20 — 15, so i need to also call dfs with 10 as the starting coin,and the original n as the starting value in this case it will return 20 = 10 * 2 = 2 coins and as i said in the start the algorithm will take the minimum of all those possibilities and return it Sorry if my explanation is unclear , if you have any other questions regarding the solution i will try to answer it

• 9 days ago, # ^ | Through empirical observation, because otherwise we can change the surplus 's into .

• 9 days ago, # ^ | Welcome to the land of undefined behavior In problem B when i = 30, you are accessing sieve[30] but your vector size is exactly 30 (should be > 30) In problem C you didn't delete the code from problem B and the same thing happens

  • 9 days ago, # ^ | shittt. I got it,but why there is no runtime error in test 1, it should come at the earliest testcase only. & Please tell why the same code is successfully submitted after the contest.

    • 9 days ago, # ^ | ← Rev. 2 →   +1 The thing about undefined behavior is your code will become completely unpredictable You can try submitting that same code for some more times and see that it might get different verdicts for different submissions of the same code

    • 9 days ago, # ^ | ← Rev. 4 →   +1 You can read more about undefined behavior here: https://en.cppreference.com/w/cpp/language/ub (I know that it's kinda weird that C++ doesn't immediately throw a rte on invalid array accessing, but I guess it's just a quirk of C++ that you have to deal with...) Also as a side note, vector has a .at() method and it is guaranteed to perform bound checking (It will throw an exception in case of invalid accesing), so you might want to use it instead of the normal [] operator

• 9 days ago, # ^ | Tag mike

• 9 days ago, # ^ | That's not cheating, 249197369 was submitted after contest

• 9 days ago, # ^ | Get used to it :(

• 9 days ago, # ^ | Yeah, after sorting, you can choose i = 0, j = n-1, k = 1, l = n-2, so you can get maximum value.The answer is 2·(a[j]+a[l]-a[i]-a[k])

• 8 days ago, # ^ | The round was unrated for me even though my rating was < 2100.

• 8 days ago, # ^ | Well, it is strictly forbidden to use __asm__. In this case, we cannot tell whether the code is copied.

• 8 days ago, # ^ | maybe your code coped anyone

• 6 days ago, # ^ | ← Rev. 2 →   +5 Code obfuscation isn't allowed, you aren't allowed to intentionally make your code harder tl understand to avoid hacks

• 8 days ago, # ^ | I hope I can be Expert in the next contest