first so ez

Fast editorial!

Thanks for the fast System test and fast editorial. It was a great contest and I liked problem C. I think every contest needs an interactive problem at least.

English editorial pls ?

I just refreshed the page and the text changed from English to Russian. Please fix it,thanks.

UPD:It was fixed,thanks!

E: First time a problem need to hardcode from n=3 to n=13

Problem C seems to essentially be a duplicate of a problem which I wrote in a previous DMOJ round, but with one fewer step. This is probably just a coincidence though.

whats the reason behind this? If coins of value 1, 3, 6 and 15 were only present the greedy logic of selecting the higher valued first would work.

Another solution for B is to do greedy by picking the highest possible denomination each time, but finally decrease the above answer by 0,1 or 2 depending upon the value of n mod 15.

https://codeforces.net/contest/1934/submission/249187805 I am not getting why is it giving idleness limit exceeded verdict

good contest..I loved C but I solved after Contest
from now...I wonot skip any interactive Problem when I practice general

The third test case of $$$D2$$$ really confused me. Why are we moving first, and why is Bob not splitting $$$10$$$ into $$$8$$$ and $$$2$$$, which should be optimal according to Bob?

Also, what is classic classic in the input?

For $$$D-2$$$, you can also bruteforce/precalculate the states by checking every $$$n$$$ : $$$a$$$, $$$b$$$ transition since $$$n$$$ is atmost $$$60$$$

Problems from this contest made me realize how low my IQ is...

E: Are there any cute approach for $$$n$$$ is small?
I used randomized brute force(and easily found a solution, 249183723 (commentout code)), but I'm looking for simpler approach.

Another approach of B: 2 * max >= 3 * 2nd max i.e. 2 * 15 >= 3 * 10, which means if n >= 30, always better to take 15s until n < 30, then for residual count (max 29), dp can be used.

submission: https://codeforces.net/contest/1934/submission/249116555

Can someone please explain how the formula was derived in problem A? Like how is |a−b|+|b−c|+|c−d|+|d−a| equal to 2∗d−2∗a? I'll be able to understand the next two if I only knew how to do this :(

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

void minCoins() { int n; cin>>n; int coins[] = {15, 10, 6, 3, 1}; int min1=INT_MAX, numCoins = 0; for(int i=0;i<5;i++){ if((n%coins[i])==0) min1=min(min1,n/coins[i]); } for (int i = 0; i < 5; i++) { numCoins += n / coins[i]; n %= coins[i]; }

cout<<min(min1,numCoins)<<endl; }

int main() { int t; cin >> t; while (t--) { minCoins(); }

return 0; }

This code is giving result 9 for 98(15*6+6*1+1*2) which is indeed correct right! but in problem the answer for 98 is 8.

You would never need more than 2 6s, 18=15+3 better than 6+6+6 and 24=15+3+6 better than 6+6+6+6

If you write C like this:

query a dot(x1,y1)

analyze which dot to query next (using many if-else)

and query (x2,y2)

and analyze all possible conditions...(using many if-else)

and query (x3,y3) ....

your code will easily become over 100 lines and have a very complex logic and also hard to write & debug. That's what I did in the contest.....qwq.

Maybe I should learn more. How to solve this kind of problem efficiently? Thanks for any ideas.

can someone please tell what was the rating of Problem B???

For question B, there seems to be a better solution. 249111275 I like this solution by Sugar_fan, because it's linear time per test case after a tiny amount of precalculation. Could Sugar_fan himself or someone who gets it please explain a little bit on the solution? About why taking the remainder between m and 2m works and 0 and m does not?

As for the value of m in his/her solution (= 2700), I intuitively expanded on this idea and figured that in general m = lcm(numbers) will also work. As such here is an accepted solution (I simply changed m from 2700 to 30 in the code): 249254380, with 0ms, signifying O(1).

An easier solution to D1. We just want to work on first 2 setbits of number n. I claim that if the first set bit of n is also set in b then the solution is always possible in 1 operation. Consider the example:

n = 5, m = 1. their binaries will be

n = 101
m = 001

Here, we can always have a value of s lesser than n such that its XOR with n will be also be lesser than n. For instance we can use s = 100 and our value of n will be transformed into m. Case 2(m has a setbit between the first 2 setbits of n) Consider n = 5 and m = 3 The binaries will be ~~~~~ n = 101 m = 011 ~~~~~ Here we will always have to choose the second bit of s as 1 in order to reach m but it will be contra to the second condition of s < n. So the solution isn't possible in the test case. Case 3(We have first 2 setbits of n and m in same position): In this case we can always make n = m in just 2 operations. lets consider the example. n = 21, m = 5; The binaries will be: n = 10101; m = 00101

First, we can choose s = 100001. How and why? If we set the first bit of s and leave the position of second set bit of n in s then we will have the independence to choose the leftover bits as we like as anyways, s is always going to be smaller than n. Thus, we have cut the problem into a position where we only check the positions between first 2 set bits of n. Once we are done with that, we can choose any s such that leftover bit gets toggled. Here, for instance, we could choose s = 00100 in the second step and hence, n will be transformed into m. Hope this helps someone. I have this code which does this job in time complexity closer to constant.

ll m, n;
 
ll st(ll x, ll i){
	return ((x & (1ll << i)) > 0);
}
 
void solve(){
	cin >> n >> m;
	bool bad = 0, solved = 0;
	int last = -1, st_cnt = 0;
	for(int i = 61; i >= 0; --i){
		if(st(n, i)){
			if(st(m, i)){
				cout << "1\n";
				cout << n << " " << m << "\n";
				solved = 1;
				break;
			}
			st_cnt++;
			last = i;
			if(st_cnt == 2) break;
		}
		else if(st(m, i)){
			bad = 1;
			break;
		}
	}	
	if(bad){
		cout << "-1\n";
		return;
	}
	if(!solved){
		cout << "2\n";
		cout << n << " " << m + (1ll << last) << " " << m << endl;
	}
}

And thanks to Shayan for coming up with this approach.

I think I've got pretty interesting solution for B. It was knapsack problem, but with cunning trick.

Let's remove all 15 from number N. I mean like, lets cnt = n/15, then n -= cnt*15. Then just do DP with vector a = {1, 3, 6, 10}. And the answer will be cnt + dp[n] (because n is less than 15 it will pretty quick).

But there's a catch. Sometimes it is better to not take last 15 coin. For example, 98. With our method, answer will be 9 (15*6 + 6*1 + 1*2). But the correct answer is 8 (15*5 + 10*2 + 3*1).

So we should write two dps, one for n -= (n/15)*15, and the other is for (n/15-1)*15, and then output the minimal one min(dp1[n] + cnt1, dp2[N] + cnt2).

Cool problems! Thanks! I loved them.

For the problem C, I queried (1,1), (1,m),(n,1) and (n,m).

Let the manhattan distances be r1,r2,r3,r4.

So as in the solution I guessed 2 possible values of (x1,y1).Let them be (x11,y11){assuming r2 is distance from (x1,y1)} and x12,y12{assuming r3 is distance from (x2,y2) and r2 is distance from x1,y1}. Now using r4 ,we know for sure that r4=n-x2+m-y2 since we assumed x1+y1=r1.

We calculate the possible values of (x2,y2) using r4 and r3 (assuming (x1,y1) is calculated using r1 and r2 i.e (x1,y1)=(x11,y11)). Then to check out of (x11,y11) and (x12,y12) which one is the correct (x1,y1) we apply the condition that

if(x11+y11<=x21+y21 && -y11+x11<=-y21+x21){
            cout<<"! "<<x11<<" "<<y11;
}
else cout<<"! "<<x12<<" "<<y12;

I think my logic is correct ,but still my code is giving WA.What am i doing wrong here?

Here is my piece of code for reference.

        ll n,m;
        cin>>n>>m;//m columns and n rows
        cout<<"? "<<1<<" "<<1<<endl;
        ll r1;
        cin>>r1;//r1=x1+y1;
        cout<<"? "<<1<<" "<<m<<endl;
        ll r2;
        cin>>r2;
        cout<<"? "<<n<<" "<<1<<endl;
        ll r3;
        cin>>r3;
        //either r2=n-x1+y1 or n-x2+y2 if n-x1+y1>n-x2+y2=> x1-y1<x2-y2 then r2=n-x2+y2
        // r3=x1+m-y1 or x2+m-y2 (if r2=n-x2+y2 ,then r3=n-x1+y1 and vice versa)
        //r4=n-x1+m-y1 or n-x2+m-y2 ?? since we assumed r1=x1+y1<x2+y2 =>r4=n-x2+m-y2
        cout<<"? "<<n<<" "<<m<<endl;
        ll r4;
        cin>>r4;
        r1+=2;
        r2+=1;
        r3+=1;
        float x11=(r1+r2-m)*1.0/2;
        float y11=(r1-r2+m)*1.0/2;
        float x21=(m+2*n-r3-r4)*1.0/2;
        float y21=(m-r4+r3)*1.0/2;
        float y12=(r1+r3-n)*1.0/2;
        float x12=(r1-r3+n)*1.0/2;
        if(x11<=0||y11<=0||x11>n||y11>m||x11-(ll)x11!=0||y11-(ll)y11!=0){
            cout<<"! "<<x12<<" "<<y12;
        }
        else if(x12<=0||y12<=0||x12>n||y12>m||x12-(ll)x12!=0||y11-(ll)y12!=0){
            cout<<"! "<<x11<<" "<<y11;
        }
        else if(x11+y11<=x21+y21 && -y11+x11<=-y21+x21){
            cout<<"! "<<x11<<" "<<y11;
        }
        else cout<<"! "<<x12<<" "<<y12;
        cout<<endl;

Very interesting problems, many thanks to the setters!. Just wanted to share my thoughts on problem A, as I thought it might help someone cuz it took a while for me to understand it well enough (or) intuitively.

For the problem D2, if the number p has an even bit count, can I break it into p1=2^(lsb of p) and p2=p1⊕p , where lsb means the least significant bit?

In the Code Part of Solution to Problem D2, on Alice's turn, why does the code set curr into p1? Why cannot Bob choose p2 instead of p1?

long long p1=(1ll<<pos);
long long p2=curr^p1;
cout<<p1<<" "<<p2<<endl;
curr = p1; // p2?

Could somebody please explain why is this solution giving TLE for problem D2??

The given below is the link to my submission :- https://codeforces.net/contest/1934/submission/249353586

Why my submission doesn't work (Problem C)? 249380440

My solution for B is a little interesting. https://codeforces.net/contest/1934/submission/249410271

• Realise that when n grows, say n = 420, its 15 x 28 and 10 x 42, and 42-28 = 14
• This means using the 15-value coin is a no-brainer as its using atleast 14 less coins than other combinations, so even if the remainder is non-zero, it will be less than 14 and we can use 1-value coin to fill the remainder, and it will still be optimal.
• So I reduce large values of n, say 10^9 to a number between 420 and 435 by using only 15-value coins, then I rely on dp to tell me the minimal coins needed to consume the current number.

#include <bits/stdc++.h>
using namespace std;
int dp[435];
int go(int n) {
	if (n >= 435) return (n-420)/15 + go(420 + (n-420)%15);
	return dp[n];
}
void solve() {
	int n; cin >> n;
	cout << go(n) << endl;
}
void init() {
	vector<int> coins = {1, 3, 6, 10, 15};
	dp[0] = 0;
	for (int i = 1; i < 435; i++) {
		dp[i] = i;
		for (int c: coins) if (c <= i) dp[i] = min(dp[i], 1 + dp[i-c]);
	}
}
int main() {
	init();
	int t; cin >> t;
	while (t--) solve();
	return 0;
}

B was similar to this spoj problem TPC07. Seems like others are picked from somewhere with minor conditions change only or is this a coincidence ?

For problem E, how does jury check whether the answer output by the contestant is correct? That is, how to write the Special Judge for this problem?

problem C sucks

import math
def base_5(n):
    if n<0:
        return math.inf
    if n==5:
        return 3
    ans=0
    if n%10==5:
        n-=15
        ans+=1
    
    ans+=(2*(n//30))
    n=n%30
    ans+=(n//10)
    return ans
    
def func(n):
    
    if n%5==1:
        return min(base_5(n-1)+1,base_5(n-6)+1)
    if n%5==2:
        return min(base_5(n-2)+2,base_5(n-7)+2,base_5(n-12)+2)
    if n%5==3:
        return min(base_5(n-3)+1,base_5(n-8)+3)
    if n%5==4:
        return min(base_5(n-4)+2,base_5(n-9)+2)
    
    return base_5(n)
    
for i in range(int(input())):
    n=int(input())
    print(func(n))

another approach for B

Why exactly can't problem B be solve greedily. I came up with obvious cases: 20 = 10 + 10, 35 = 15 + 10, and so on. But why not?

This is My B number Code I think this is more easy than this code

include <bits/stdc++.h>

using namespace std; typedef long long int ll; int main() {

int t;
cin>>t;
while(t--)
{
    int  ans[]= {0,1,2,1,2,3,1,2,3,2,1,2,2,2,3,2,3,1};
    int n;
    cin>>n;
    int out=n/15;;
    int x=n%15;
    if( x==8 and n>15)
    {
        cout<<out+2<<endl;
    }
    else if(x==5 and n>15){
        cout<<out+1<<endl;
    }
    else
    {
        cout<<out+ans[n%15]<<endl;
    }


}

}

include<bits/stdc++.h>

using namespace std;

void rec(int in,vector &v,long long c,long long &ans,long long n) {
if(in>=v.size()) return;

if(n<0)
return ;
if(n==0)
{
    ans=min(ans,c);
    return ;
}

if(n-v[in]>=0)
rec(in,v,c+1,ans,n-v[in]);

rec(in+1,v,c,ans,n);

return;

} int main() { int t; cin>>t; while(t--) { long long n; cin >> n; long long ans =INT_MAX; vector v = {15, 10, 6, 3, 1}; int in = 0; for (in = 0; in < v.size(); in++) { if (v[in] <= n) break; } long long c=0; rec(in, v, c, ans, n);

cout << ans << endl;


  }

 }

why is this code not running for this test case 402931328

and giving the output

Exit code is -1073741571

Another solution for D1. Since we are allowed up to 63 operations, we can just do $$$\le1$$$ operation per bit. First let's assume there are at least 2 set bits in $$$n$$$.

For each bit $$$b$$$, if $$$b$$$ is the same in $$$m$$$ and $$$n$$$, then obviously we don't have to change it. Then we can break into two cases:

$$$1$$$: If $$$b$$$ is set in $$$n$$$ but not $$$m$$$, then we can add another operation flipping just that bit to $$$0$$$. Obviously, $$$b < n$$$ and $$$b\oplus n < n$$$, so this is valid.

$$$2$$$: If $$$b$$$ is set in $$$m$$$ but not $$$n$$$, then we can't have a separate operation, since then $$$b \oplus n > n$$$. Instead, let's combine this operation with an operation from case $$$1$$$, specifically the largest one. Note that since $$$m < n$$$, we will always encounter case $$$1$$$ before case $$$2$$$.

Now all we have to do is check if the largest operation is valid (because it may have been invalidated by case $$$2$$$ operations). There is an answer iff the largest operation is valid.

Problem: C

Can anyone tell me why my answer is giving the Idleness limit exceeded? What's wrong with my code?

my code: https://codeforces.net/contest/1934/submission/258188798

interactive problem for Problem C? That's not interesting.