harsh__h's blog

By harsh__h, 2 months ago,

1934A — Too Min Too Max

Solution
Code (C++)
Code (Python)

1934B — Yet Another Coin Problem

Solution 1
Solution 2

1934C — Find a Mine

Hint 1
Solution 1
Solution 2

1934D1 — XOR Break — Solo Version

Hint
Solution
Code

1934D2 — XOR Break — Game Version

Hint 1
Hint 2
Solution
Code

1934E — Weird LCM Operations

Solution
Code
• +105

 » 7 weeks ago, # |   -40 first so ez
 » 7 weeks ago, # |   -63 Fast editorial!
•  » » 7 weeks ago, # ^ |   -56 WHY DOWNWOTE???
 » 7 weeks ago, # |   -26 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.
•  » » 7 weeks ago, # ^ |   +11 wtf! NO. It's cringe.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +4 So you like a mathforces round?
•  » » » » 7 weeks ago, # ^ |   0 Ironic enough I classify C as a math problem...
•  » » 7 weeks ago, # ^ |   0 How often will interactive tasks appear now? (I just didn’t notice them during the rounds before)
•  » » » 7 weeks ago, # ^ |   +7 Interactive problems are not much but in last two contests problem C was interactive.
 » 7 weeks ago, # |   +37 English editorial pls ?
 » 7 weeks ago, # | ← Rev. 2 →   0 I just refreshed the page and the text changed from English to Russian. Please fix it,thanks.UPD:It was fixed,thanks!
 » 7 weeks ago, # |   +33 E: First time a problem need to hardcode from n=3 to n=13
 » 7 weeks ago, # |   +24 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.
•  » » 7 weeks ago, # ^ |   -107 It must be unrated
•  » » » 7 weeks ago, # ^ |   +7 Nah honestly if you can recall a 1.5 year old problem from memory then you deserve the points.
•  » » » » 7 weeks ago, # ^ |   +3 You would be laughing right before the round I was solving https://codeforces.com/problemset/problem/1797/C with all logic done, just fixing final bugs. Still I didn't solve C during the round. Although I think I would if hadn't switched to D.
•  » » » » 7 weeks ago, # ^ |   0 I mean, there's a Div2 Edu E a while ago thzt's literally the hard copy of APIO22 P3, lol
•  » » » » 7 weeks ago, # ^ |   0
 » 7 weeks ago, # |   0 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.
•  » » 7 weeks ago, # ^ |   +2 Added the proof. Is it written clearly?
•  » » » 7 weeks ago, # ^ |   0 Nice Explanation, Thanks!
•  » » » » 7 weeks ago, # ^ |   0 This part is trying to prove the greedy method works properly, and I still getting it.
 » 7 weeks ago, # |   0 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.
•  » » 7 weeks ago, # ^ |   0 Can you please explain why this works ?
•  » » » 7 weeks ago, # ^ |   0 because a_max(highest value) is fixed such the remainders which are 1->14 and there cases
•  » » » 7 weeks ago, # ^ |   0 Noticed that when we try to acheive a big n, using as many 15s seems to be right. However, the initial greedy solution may be wrong because in some situations we can take a step back and get a smaller answer.There are only two such situations: when n%15==5(5=1+1+3,20=15+5=10+10) or n%15==8(8=1+1+6,23=15+8=10+10+3).
 » 7 weeks ago, # |   -22 https://codeforces.com/contest/1934/submission/249187805 I am not getting why is it giving idleness limit exceeded verdict
•  » » 7 weeks ago, # ^ |   +38 because it's wrong
•  » » » 7 weeks ago, # ^ |   0 Then why the verdict is not "Wrong Answer"?PS: downvotes for a doubt. Crazy!
•  » » » » 7 weeks ago, # ^ |   0 cout.flush() ?
 » 7 weeks ago, # | ← Rev. 2 →   +3 good contest..I loved C but I solved after Contest from now...I wonot skip any interactive Problem when I practice general 
 » 7 weeks ago, # |   0 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?
 » 7 weeks ago, # |   +8 For $D-2$, you can also bruteforce/precalculate the states by checking every $n$ : $a$, $b$ transition since $n$ is atmost $60$
 » 7 weeks ago, # |   +14 Problems from this contest made me realize how low my IQ is...
•  » » 7 weeks ago, # ^ |   0 True, I found these thinking problems hard for me as well.
•  » » » 7 weeks ago, # ^ |   0 Y'alls IQ higher than mine!
 » 7 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 7 weeks ago, # ^ |   +18 This isn't exactly an answer to your question, but I came up with a solution that does not require brute force (but it did require a leap of faith for smaller cases):The basic idea is exactly as in the editorial, we only care about $x > \frac{n}{2}$.We will try to make tuples with these numbers starting from $\frac{n+2}{2}$, we will only consider consecutive numbers.Let $(x_1, x_1 + 1, x_1 +2)$ be the tuple that we are considering in this moment: If $x_1$ is odd, then we can apply the operation as in the editorial and continue with the next numbers.If not, then one of $x_1$ and $x_1+2$ is not divisible by $4$. Let's assume that $x_1$ satisfies this property. Then we will apply the operation to the tuple $(\frac{x_1}{2}, x_1+1, x_1+2)$. Notice that $\frac{x_1}{2}$ was not modified by other operations until now. Now, we can prove that we can generate the values of $x_1$, $x_1+1$, $x_1+2$ and $\frac{x_1}{2}$ with the new values generated, and $x_1$, that was not used.Finally, we have to consider the cases where we didn't handle the last numbers. If only two numbers were left, then the solution is equal to the editorial. But if one number is left, then we will use $(n, 1, \text{a number that is coprime with n and was not used})$ You have to prove that there will always exist such number, for a big $n$ is reasonable, but for a small $n$ I just had faith.
 » 7 weeks ago, # |   +1 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.
 » 7 weeks ago, # |   0 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 :(
•  » » 7 weeks ago, # ^ |   0 When the value in the mod is negative, we negate its contents while removing the mod.So as stated $a \leq b \leq c \leq d$, when we open the mods it becomes $(-(a-b))+(-(b-c))+(-(c-d))+(d-a)$ which on simplifying gives $b-a-b+c-c+d+d-a$ which equals $2*d-2*a$
•  » » » 7 weeks ago, # ^ |   0 Oh ok I get it. Thanks a lot!
 » 7 weeks ago, # |   0 include 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<> 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.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 15 * 5 + 10 * 2 + 3
 » 7 weeks ago, # |   +7 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
•  » » 7 weeks ago, # ^ |   0 I was having the same doubt, that why they gave 4 sixes in the eidtorial
 » 7 weeks ago, # |   0 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.
 » 7 weeks ago, # |   0 can someone please tell what was the rating of Problem B???
•  » » 7 weeks ago, # ^ |   0 just wait for a few days, als why do you need the rating of a problem anyways?
•  » » » 7 weeks ago, # ^ |   0 just curious nothing else
 » 7 weeks ago, # |   0 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).
•  » » 7 weeks ago, # ^ |   0 I also use this solution as I'm desperate. If anyone know how this solution works and prove it please tell me!!!
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +2 We need to prove this: for every $n>=30$ , the optimal choose must have a 15s coin.prove: Consider an optimal choose that don't have 15s coin. it have no more than 2*10s coin (3*10s coin->2*15s coin) 10s coin will not appear with 6s coin (10+6 = 15+1 , the optimal choose can have 15) it have no more than 2*6s coin (3*6s coin -> 1*3s coin + 1*15s coin) it have no more than 1*3s coin (2*3s coin -> 1*6s coin) it have no more than 2*1s coin (3*1s coin -> 1*3s coin) So , this optimal choose have sum of 2*1s + 1*3s + 2*10s = 25 < 30 (don't have 6s coin)OR 2*1s + 1*3s + 2*6s = 17 < 30 (don't have 10s coin)So exactly if n>25 we can greedy choose 15s coin.In fact , 25=10+15 , 24=15+6+3 , 23 = 10+10+3 (if have 15s coin,it will be 15+6+1+1) , so the maximum n that we can't do greedy is 23.
•  » » » 7 weeks ago, # ^ |   +1 Thanks, got what's going on. So you do greedy till your remaining number is <= 23, then you add the pre-calculation of the remainder. Or I can say, it can be shown that [can it?] the lcm is always >= (the number till which greedy can't be applied) [remains to be proven], and thus following what is done in the code, the remainder will always be , rem >= lcm >= lowest non greedy number, and thus works. Do you have anything to add?
 » 7 weeks ago, # |   -6 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 CautionI know that this test case can be solved with case 1 but for the sake of explanation I'm using it. It's short and can help in understanding this case a lot.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. Codell 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.
 » 7 weeks ago, # |   0 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).
 » 7 weeks ago, # |   +1 Cool problems! Thanks! I loved them.
 » 7 weeks ago, # | ← Rev. 2 →   0 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<<"! "<>n>>m;//m columns and n rows cout<<"? "<<1<<" "<<1<>r1;//r1=x1+y1; cout<<"? "<<1<<" "<>r2; cout<<"? "<>r3; //either r2=n-x1+y1 or n-x2+y2 if n-x1+y1>n-x2+y2=> x1-y1r4=n-x2+m-y2 cout<<"? "<>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<<"! "<n||y12>m||x12-(ll)x12!=0||y11-(ll)y12!=0){ cout<<"! "<
•  » » 7 weeks ago, # ^ |   0 perhaps your x11 y11 x21 y21 y12 x12 are floats...I don't understand why you're using float.The mines coordirates are all integers.
•  » » » 7 weeks ago, # ^ |   0 I'm using float so that i can identify when is r1+r2-m and similarly others are divisible by 2 or not. If you see carefully I have put a check in the if condition that x11-(ll)x11!=0 which checks if x11 is integer or not. So if x11 or y11 is a decimal then the answer is (x12, y12)
•  » » » » 7 weeks ago, # ^ |   0 you don't need to check if the point is divisible by 2 or not. just query this point and you will know. and if you really want to get the answer in 3 queries just check if r1+r2-m is divisible by two and continue using integers. float won't fit anyways, try long double.
•  » » » » » 7 weeks ago, # ^ |   0 For a moment lets leave the discussion on floats or long doubles. I know i could query this point and if I get 0 ,then its the correct point otherwise the other is the correct point. But still I want to know what is wrong in my method or logic.It seems correct that I query (n,m) and then get a r4 to find the other point (x2,y2) and then apply the conditions for assuming that r2 is distance from (x1,y1) and r3 is distance from (x2,y2).
•  » » 6 weeks ago, # ^ |   0 Bro sent the code as a spoiler or as a link
•  » » » 6 weeks ago, # ^ |   0 I'll take care the next time.
•  » » » » 6 weeks ago, # ^ |   0 You can edit the comment
 » 7 weeks ago, # |   +3 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. SpoilerThe problem can be viewed as choosing any 4 elements from the initial array, and placing them along a circle in any order. Except that, we also want this ordering to give us the maximum possible sum of the absolute differences of the adjacent elements in the circle.If we assume that we have chosen some 4 elements (we'll see how to choose them optimally a bit later), we just have to find a permutation along this circle that maximizes our goal. Now, intuitively we can see that, placing the top 2 maximal elements (or equivalently the top 2 minimal elements) diametrically opposite to each other is the most optimal way, that gives 2*((max1+max2)-(min1+min2)) as the answer.To prove this Intuitive claim of ours, let's consider elements a<=b<=c<=d. We can see that there are only 3 possible permutations with unique pairs of adjacents. This is because : There are only (4-1)! = 6 circular permutations (Rotations are considered the same, cuz the adjacents are the same). Among them as well, we must consider the mirror images (left-right inversion) to be the same (cuz the adjacents are the same). Therefore, we divide by 2, giving us 6/2 = 3 permutations. To view these 3 permutations, consider the elements a,b,c,d to be permuted along the circle. Fix the position of a, now once we fix it's opposite element, the adjacents get fixed automatically. Therefore, we only have 3 perms. ( a-b opposite, a-c opposite, a-d opposite ). We can evaluate the answer for these 3 perms, as it has been done in the Editorial, and pick the maximum, which will turn out to be 2*((d+c)-(a+b)), thereby proving our intuitive claims. ( max1=d , max2=c , min1=a, min2=b )Thus, for the overall problem, we can just pick the maximum two and the minimum two elements from the entire array, as this choice maximizes 2*((max1+max2)-(min1+min2)). I'm sorry if this turned out to be lengthy. Also, feel free to correct me if there's something wrong in this.Thanks for Reading :)
 » 7 weeks ago, # |   +3 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<
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 .
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 For your first question: For example take the number 1111000 in your turn. With your logic, you get 1110000 and 0001000 and you print it. Obviously the system will choose 1110000.But here since only the XOR of two split numbers needs to be equal to 1110000; the system could print 1011111 and 0101111 (both are less than 1110000, constraints of the problem are met) so the lsb we removed can come back in cases like these. therefore, the interaction is not guaranteed to end in 63 operations.but when we remove msb, it's impossible to get that same bit back again and we can finish the interaction in less than or equal to 63 operations.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Well, I forgot the constraint that up to 63 operations can be executed. I guess that is why I got TLE when I use lsb strategy. Thank you very much for pointing it out! :)
•  » » » » 6 weeks ago, # ^ |   0 np :)
 » 7 weeks ago, # | ← Rev. 2 →   0 Could somebody please explain why is this solution giving TLE for problem D2??The given below is the link to my submission :- https://codeforces.com/contest/1934/submission/249353586
•  » » 7 weeks ago, # ^ |   0 Use long long in your print function
•  » » 6 weeks ago, # ^ |   0 Use lsb will exceed operations limitation. See this
 » 7 weeks ago, # | ← Rev. 2 →   0 Why my submission doesn't work (Problem C)? 249380440
 » 7 weeks ago, # | ← Rev. 4 →   +6 My solution for B is a little interesting. https://codeforces.com/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. Here's the code#include 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 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; } 
•  » » 6 weeks ago, # ^ |   0 Bro sent the code as a spoiler or as a link
 » 7 weeks ago, # |   -10 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 ?
 » 7 weeks ago, # |   +16 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?
 » 7 weeks ago, # |   0 problem C sucks
 » 6 weeks ago, # | ← Rev. 2 →   0 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
•  » » 6 weeks ago, # ^ |   0 Bro sent the code as a spoiler or as a link
 » 6 weeks ago, # |   0 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?
•  » » 6 weeks ago, # ^ |   0 for ex n=20: greedy chooses the greatest that's why the output is 4(15*1+3*1+1*2) but it must be 2(10*2)
»
4 weeks ago, # |
0

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

}

}

»
3 weeks ago, # |
0

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

 » 8 days ago, # |   0 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.