harsh__h's blog

By harsh__h, 2 months ago, In English

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
  • Vote: I like it
  • +105
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

first so ez

»
7 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

Fast editorial!

»
7 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

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, # ^ |
      Vote: I like it +11 Vote: I do not like it

    wtf! NO. It's cringe.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How often will interactive tasks appear now? (I just didn’t notice them during the rounds before)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Interactive problems are not much but in last two contests problem C was interactive.

»
7 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

English editorial pls ?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +33 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Added the proof. Is it written clearly?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice Explanation, Thanks!

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This part is trying to prove the greedy method works properly, and I still getting it.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain why this works ?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      because a_max(highest value) is fixed such the remainders which are 1->14 and there cases

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it -22 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +8 Vote: I do not like it

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, # |
  Vote: I like it +14 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

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.com/contest/1934/submission/249116555

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was having the same doubt, that why they gave 4 sixes in the eidtorial

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +2 Vote: I do not like it

    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.

    1. it have no more than 2*10s coin (3*10s coin->2*15s coin)

    2. 10s coin will not appear with 6s coin (10+6 = 15+1 , the optimal choose can have 15)

    3. it have no more than 2*6s coin (3*6s coin -> 1*3s coin + 1*15s coin)

    4. it have no more than 1*3s coin (2*3s coin -> 1*6s coin)

    5. 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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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, # |
  Vote: I like it -6 Vote: I do not like it

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

Caution

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.

Code

And thanks to Shayan for coming up with this approach.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +1 Vote: I do not like it

Cool problems! Thanks! I loved them.

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

Code
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro sent the code as a spoiler or as a link

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

Spoiler
»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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?
  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    .

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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! :)

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

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
»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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, # |
  Vote: I like it +16 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

problem C sucks

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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.