Codeforces Round #41, Problem-C (Safe Cracking)

Problem Link: Safe Cracking

I could not solve this problem in the contest. My greedy solution was wrong. I submitted it without proof (didn't have time for that) and it failed the system test.

I have solved it later with the correct greedy idea described bellow:

Solution:
initially we have a cyclic 4-tuple {A,B,C,D}. (i.e. D and A are consecutive)

The solution works iteratively. At each step, we decide to perform one of the following operations based on the parities of {A,B,C,D}.

(1) if there are 2 consecutive even numbers, we divide both of them by 2, and repeat this step.
(2) if there are 2 consecutive odd numbers and at least one of them is greater than 1, we increase them by 1 and go back to step 1.
(3) we find two consecutive numbers such that, their parities are different. Increase them by 1 and go back to step 1.

Proof:
We have to prove 2 things: (i) the algorithm terminates with {1,1,1,1} (ii) it doesn't take more than 1000 steps.

The key observation is that, the algorithm never performs the increment operation for more than 1 consecutive steps. It is performed in case of one of the following combination of parities:

a. {odd,odd,odd,odd}
b. {odd,even,odd,even}
c. {even,odd,even,odd}

an increment operation on any of these combinations produces two consecutive even numbers which gets divided by 2 in the next step.

So, in every two consecutive steps, there is at least one division operation. This can not go forever.

So, we can conclude that, the algorithm terminates after a finite step with {1,1,1,1}.

The number of steps required is O(log₂M) where M is the maximum number among {A,B,C,D}. This ensures that, it never takes more than 1000 steps.

Here is the Accepted c++ code implementing this idea:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<ctype.h>

#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))

int main()
{
int a[4];
FOR(i,4) scanf("%d",a+i);

while(1)
{
  if(a[0]==1&&a[1]==1&&a[2]==1&&a[3]==1) break;

  bool done = false;

  FOR(i,4)
  {
      if( a[i]%2==0 && a[(i+1)%4]%2==0 )
      {
          printf("/%d\n",i+1);
          a[i]>>=1;
          a[(i+1)%4]>>=1;
          done = true;
          break;
      }
  }

  if(done) continue;

  FOR(i,4)
  {
      if( a[i]%2==1 && a[(i+1)%4]%2==1 && max(a[i],a[(i+1)%4])>1)
      {
          printf("+%d\n",i+1);
          a[i]++;
          a[(i+1)%4]++;
          done = true;
          break;
      }
  }

  if(done) continue;

  int pos = 0;

  FOR(i,4)
  {
      if(a[i]%2 != a[(i+1)%4]%2) pos = i;
  }

  a[pos]++;
  a[(pos+1)%4]++;

  printf("+%d\n",pos+1);
}

return 0;
}

This blog is inspired by: http://one-problem-a-day.blogspot.com