DYNAMO - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Amit Dwivedi
Tester- Encho Mishinev
Editorialist- Abhishek Pandey

DIFFICULTY:

Simple

PRE-REQUISITES:

Maths and Basic Logic

PROBLEM:

You and computer alternate giving five N- perfect numbers (i.e. numbers <10^N ) alternatively, A , B, C, D, E. You need to make sure that A+B+C+D+E=S while computer will try to stop you. If you are allowed to always chose S, devise an algorithm to always win.

QUICK-EXPLANATION:

Key to AC- Realize that 0 < A,B,C,D,E < 10^N while S \leq 5*10^N. Hence, S=A+2*10^N is an ideal choice for a win.

Since A,B,C,D,E < 10^N but S is allowed to be upto 5*10^N, realize that you need an ideal value of S to win. Hence, set UL=10^N. Let S=A+2*UL. Now you always have a winning strategy as follows-

  • Computer gave you A.
  • You returned S=A+2*10^N
  • Computer gave B
  • You returned 10^N-B. Sum so far = A+B+(10^N-B)=A+10^N.
  • Computer returned C.
  • You returned 10^N-C. Sum = A+B+(10^N-B)+C+(10^N-C)=A+2*10^N=S

EXPLANATION:

For this problem also, there is actually not very much to discuss after the quick explanation. It was more or less like grabbing the observation and coming up with the trick to solve the problem.

So, lets discuss the following-

  • Why doesn’t any random solution passes.
  • Seeing the problem from another easier perspective.
  • Wrapping up the solution.

Lets get started then!

Why doesn't any random solution passes

This is because of the value of S.

Say if you give S \leq 2*10^N. Now, you are guaranteed to lose because of following-

  • Computer gives some value of A , which is at least 1. \implies A \geq 1
  • Computer gives B=10^N-1.
  • You give C which has to be at least 1. \implies C \geq 1
  • Computer gives D=10^N-1.
  • You need to give E which has to at least be 1. \implies E \geq 1

\implies Given \ Sum \geq 1+(10^N-1)+1+(10^N-1)+1=2*10^N+1 \neq S.

Similarly there are methods to fail some weaker algorithms or tricks. Of course, if you set S reasonably large, it is possible to get your algorithm actually pass a few cases by fine-tuning the value of E, but the judge will try throw the algorithm down the hill by using extreme values of A to make the difference too high to cover up with just 1 variable.

Seeing the problem from another perspective

Lets look at the problem as follows-

Computer gives you a variable D, and you have to give a variable E such that D+E=S. Pretty easy right? We just print E=S-D and we are done with.

Lets copy this concept and repeat again. You are given a variable B, then have to give a variable C in addition to above things with D and E as well. We need B+C+D+E=S and B,C,D,E < 10^N and we chose S.

If we are given S>10^N, we can give C=10^N-B to prevent opponent’s control over B from impacting the game. We are back to only D and E and repeating the trick we did with B,C, we know that we are guaranteed to win for some value of S, namely S=2*10^N.

Now lets look at current variant, where computer gives you A and then you decide S. If we set S=A+2*10^N, we see that the problem is no different than above! This reverse engineering helps grasping what goes through during setting and solving such problems.

Wrapping up the Solution

Set S=A+2*10^N. Now follow the following-

  • Computer gave you A.
  • You returned S=A+2*10^N
  • Computer gave B
  • You returned 10^N-B. Sum so far = A+B+(10^N-B)=A+10^N.
  • Computer returned C.
  • You returned 10^N-C.

Sum = A+B+(10^N-B)+C+(10^N-C)=A+2*10^N=S

Our values of C and E cancel the computer’s impact over game from B and D by summing up to 2*10^N. Adding A to S lets us cancel its impact over game via A as well!

Beyond this I believe most of the stuff is self-explanatory. Ping me here if it isn’t :slight_smile:

SOLUTION

Setter
#include "bits/stdc++.h"
using namespace std;
using ll = unsigned long long int;
ll power(ll a,int x){
    ll res = 1ll;
    for (int i = 0; i < x; ++i)
    {
        res = a*res;
    }
    return res;
}
 
int main(){
    int t = 1,i;
    cin>>t;
    for (i = 0; i < t; ++i){
        int n;
        cin>>n;
        assert(n>=1 and n<=18);
        ll tpn = power(10ll,n);
        ll a ;
        cin>>a;
        assert(a>=1 and a<tpn);
        cout<<a + 2*tpn<<endl;
        ll b ;
 
        cin>>b;
        assert(b>=1 and b<tpn);
        cout<<tpn-b<<endl;
        ll c;
        cin>>c;
        assert(c>=1 and c<tpn);
        cout<<tpn-c<<endl;
        int ok;
        cin>>ok;
        assert(ok==1);
    }
    return 0;
}  
Tester
#include <iostream>
#include <stdio.h>
#include <assert.h>
using namespace std;
typedef long long llong;
 
int t, n;
 
int main()
{
    int test;
    int i,j;
 
    scanf("%d",&t);
 
    for (test=1;test<=t;test++)
    {
        scanf("%d",&n);
 
        llong pairGoal = 1;
        for (i=1;i<=n;i++)
        {
            pairGoal *= 10LL;
        }
        pairGoal = pairGoal;
 
        llong A;
 
        scanf("%lld",&A);
        printf("%lld\n",A + 2LL*pairGoal);
        fflush(stdout);
 
        scanf("%lld",&A);
        printf("%lld\n",pairGoal - A);
        fflush(stdout);
 
        scanf("%lld",&A);
        printf("%lld\n",pairGoal - A);
        fflush(stdout);
 
        scanf("%lld",&A); /// AC - 1
    }
 
    return 0;
}
 

Time Complexity=O(1)
Space Complexity=O(1)

CHEF VIJJU’S CORNER :smiley:

  • Prove or Disprove the following -
    • The discussed algorithm works independent of constraints.
    • The discussed algorithm works if A,B,C,D,E are allowed to be 0 or 10^N as well.
    • There is a set of constraints where the discussed algorithm fails.

Solutions to above shall not be provided immediately as to encourage you all to work on them.

Setter's Notes

The idea is, For every N-perfect number X there exist another N-perfect number Y such that X+Y = 10^N

All we need to do is to give the sum first number + 2*10^N .

After that for every cheffa given number X, chef can give 10^N-X (Another N-perfect number) to cheffa and the sum for pair B,C and D,E will be maintained 10^N.

Note that, This is the only possible value of S that no matter how optimally cheffa plays, chef always a valid set of N-perfect numbers to make the desired sum of A,B,C,D,E equal to S. Any other value of S will fail on Minimal or Maximal test.

  • With reference to last paragraph in setter’s notes above, answer the following-
    • Prove that S=4500 is unoptimal for N=3 and A=999. Note that since a proof is asked, you need to device a strategy such that computer always wins no matter what choice of C and E you give.
    • Let A=x and S=y+2*10^N. Prove or disprove that answer exists only at x=y. You cannot use setter’s claim to prove that.
    • Explore the uniqueness of solution value of S. In other words, prove or disprove setter’s claim that only for S=A+2*10^N we will always win and for other values of S we are guaranteed a loss. Note that proof via counter case is not acceptable here because you will then have to prove a winning strategy for Computer exists for every value of S except S \neq A+2*10^N.
Hint for last part

We already proved computer wins if S \leq 2*10^N.

Lets take another example. Lets say you give a large S such that S=2*10^N+K such that K \neq A. Now following happens:

  • Computer gives A.
  • You give S=K+2*10^N.
  • Computer gives B=1.
  • You give C=10^N-1 which is max possible value.
  • Computer gives D=1.
  • You again give E=10^N-1.

Sum obtained is A+2*10^N but as A and K are unequal, we lose.

Hence, all values of S get covered and we prove that for S not equal to A+2*10^N we lose.

Related Problems
11 Likes

Brilliant Editorial @vijju123. Greatful for ending problems.

1 Like

https://www.codechef.com/viewsolution/28792831
Can anyone say where my solution is wrong. I used strings as no of significant digits are supposed to be more than 16.

Hi @vijju123, you mentioned the following in Chef Vijju’s Corner -

The discussed algorithm works if A,B,C,D,EA,B,C,D,E are allowed to be 00 or 10^N10
N as well.

But I decided to go by the constraints. The numbers A, B, and D would have been N-perfect integers ideally. So,
0 < A < pow(10,n)

I decided to choose
C = pow(10,n) - 1 - B; return c = greatest_N_perfect_number - b
E = pow(10,n) - 1 - D; return e = greatest_N_perfect_number - d
So, this way, S = A + 2*pow(10,n) - 2;

I did not understand why this approach was wrong?
Or why/how is the following statement correct?

We already proved computer wins if S <= 2*pow(10,n)

The discussed thing is under a “Prove or Disprove”. You cannot assume that its correct. And I will not reveal the answer either :stuck_out_tongue:

For your approach, you should first read “Why a random solution doesn’t pass” section. It specifically deals with your question.

2 Likes