560 - Magic

[Dejarik]

I'm trying to solve the problem 560-Magic, but I don't understand the meaning of some of the keys of the statement. Please has anybody solved this problem (only 16% accuracy?... hummm, and only 193 accepted answers in stats) in order to tell me the exact meaning of remove if possible leading zeros?

if a 3 occurs in the decimal representation: remove this 3 (remove if possible leading zeros)
if a 7 occurs in the decimal representation: remove this 7 (remove if possible leading zeros)

Does it means that, one number 123456 is converted to 12456 or 120456? And why is said if possible?? I'm very confused about this enunciation.

Thanks in advance! Joan

[Dominik Michniewski]

123456 must be converted to 12456.

I think, that main problem in this problem is TLE. Your algorithm must be very efficient ( I got Accepted with time ~2.4 sec, and it's best what I can do ... but I see that it's only 51 time in ranklist )

Removing all possible leading zeros means: if after applying any rule to number is starts with zeros - remove it all.

Best regards
DM

[Dejarik]

Hey! Thanks for your answer. You helped me very much in order to understand the requirements of the problem. I'm now working hard on it, but always receiving Wrong Answer. May you help me comparing several input/output cases for the problem?

Thanks in advance! Here is my I/O sample:

Input

Code: Select all

15
904390
38502352
43963409
5632950142
54960601673125
69436025369230
64309635065690245634
69832064398623063231
69054623692356023693
8759890412418924142
3333333333333333333
1112444444456668
1234567891011121314
122333444455555666
9

Output:

Code: Select all

90490
850252
496409
562950142
549606016125
69460256920
64096506569024564
698206498620621
6905462692560269
859890412418924142
11699
1852
2
2
0

Bye!

[Dominik Michniewski]

I got such results (easiest to say, why it's different is last case):

BTW. I got Accepted today, so it's very fresh solved problem to me

Code: Select all

90490
850252
628048
562950142
8515145185
99194219560
64096506569024564
862124185015151
6905462692560269
125141291605984606
529100529100529
1261852
5918004814864
582116404046
1

Comment to last case:
9 -> divide by 3 two times and you got 1, not 0. every rule can be applied to number as many times as you can use it I hope this helps you

Best regards
DM

[Dejarik]

I think it is the strongest and hardest problem I even tried in ACM Contest Site.

I cannot understand the execution for this example:

Code: Select all

1234567891011121314

Your suggested output is:

Code: Select all

5918004814864

But my estimated output is:

Code: Select all

4115226004048 

How is my output built? Please see:

1234567891011121314 divide it by 3
411522630337040438 remove the 3
41152260337040438 remove the 3
4115226037040438 remove the 3
411522607040438 remove the 7
41152260040438 remove the 3
4115226004048 : best solution estimated

And i cannot find a best value in any other way of my backtracking tree. Are you able to add to your code any 'printf("dividing by 3...")' or similar in order to see how did you build your answer?

Thank you very much,

Joan

[Dejarik]

The other example that fails between our both executions (all other are the same):

Input instance:
69832064398623063231

My output is:
59118266514059

And your suggested output is:
862124185015151

How is my output built?

69832064398623063231 : remove the 3
6983206439862063231 : divide by 3
2327735479954021077 : divide by 3
775911826651340359 : remove the 7
75911826651340359 : remove the 7
5911826651340359 : remove the 3
591182665140359 : remove the 3
59118266514059 : best output estimated

I'm making a mistake but i cannot find where. Thanks!!!!

Joan

[Dominik Michniewski]

I think, that I correct transform my program into one, which produces this list (with my little help in translation :

Code: Select all

Path for 69832064398623063231:
delete 3 -> 6983206439862306231
div by 3 -> 2327735479954102077
div by 3 -> 775911826651367359
delete 7 -> 77591182665136359
div by 3 -> 25863727555045453
delete 7 -> 2586372555045453
div by 3 -> 862124185015151

Code: Select all

Path for 1234567891011121314:
delete 3 -> 124567891011121314
div by 3 -> 41522630337040438
delete 3 -> 4152260337040438
div by 7 -> 593180048148634
delete 3 -> 59180048148634
delete 3 -> 5918004814864

I assume that you must have error in pruning algorithm or in part, which creates new numbers from old.

Best regards
DM

[Bodo]

I still have problems with 560. My program seems to be quite efficient (approx. 2s), but gets WA all the time. On input

15
904390
38502352
43963409
5632950142
54960601673125
69436025369230
64309635065690245634
69832064398623063231
69054623692356023693
8759890412418924142
3333333333333333333
1112444444456668
1234567891011121314
122333444455555666
9

I get

90490
850252
628048
562950142
8515145185
99194219560
64096506569024564
862124185015151
6905462692560269
125141291605984606
529100529100529
1261852
5918004814864
582116404046
1

Does anybody have some hint? Did I forget some subtle detail?

[Dominik Michniewski]

I got the same results as you

Best regards
DM

[Bodo]

Do you have any suggestions? Below is my code. I do not have any idea what is wrong with my code.

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>

const int Length=22, HashSize=19019, HashFactor=17;

char Max[Length], Key[HashSize][Length], Val[HashSize][Length];
bool Used[HashSize];

int hash(char *String)
{
   int i=0, HashVal=0;
   for(i=0;i<int(strlen(String));i++)
      HashVal=(((HashFactor*HashVal)+String[i]-'0')%HashSize);
   return HashVal;
}
void reverse(char *String)
{
   int i;
   char c;
   for(i=0;i<int(strlen(String))/2;i++)
   {
      c=String[i];
      String[i]=String[strlen(String)-1-i];
      String[strlen(String)-1-i]=c;
   }
}
void normalize(char *String)
{
   int i=strlen(String);
   while(String[i-1]=='0' && i>1)
      i--;
   String[i]='\0';
}
bool leq(char *S1, char *S2)
{
   int i;
   if(strlen(S1)!=strlen(S2))
      return (strlen(S1)<strlen(S2));
   for(i=strlen(S1)-1;i>=0;i--)
      if(S1[i]<S2[i])
	 return true;
      else if(S1[i]>S2[i])
	 return false;
   return true;
}

void test(char *S1, char *S2)
{
   if(!leq(S1, S2))
      strcpy(S2, S1);
}

bool div(char *Dividend, int Divisor, char *Quotient)
{
   int Carry=0, i;
   Quotient[strlen(Dividend)]='\0';
   for(i=strlen(Dividend)-1;i>=0;i--)
   {
      Carry=10*Carry+Dividend[i]-'0';
      Quotient[i]=(Carry/Divisor)+'0';
      Carry=Carry-(Divisor*(Quotient[i]-'0'));
   }
   return (Carry==0);
}

void cut(char *String, int Pos, int Length, char *New)
{
   int i;
   for(i=0;i<Pos;i++)
      New[i]=String[i];
   for(i=Pos;i<int(strlen(String))-1;i++)
      New[i]=String[i+Length];
   New[strlen(String)-Length]='\0';
}

void solve(char *String)
{
   char Local[Length], LocalMax[Length]="0";
   int i, HashVal=hash(String);
   bool Success=false;

   normalize(String);
   if(leq(String, Max))
      return;
   if(Used[HashVal])
      if(strcmp(String, Key[HashVal])==0)
      {
	 strcpy(String, Val[HashVal]);
	 test(String, Max);
	 return;
      }
   if(strcmp(String, "0")==0)
      return;
   if(div(String, 3, Local))
   {
      Success=true;
      solve(Local);
      test(Local, LocalMax);
   }
   if(div(String, 7, Local))
   {
      Success=true;
      solve(Local);
      test(Local, LocalMax);
   }
   for(i=0;i<int(strlen(String));i++)
      if((String[i]=='3' || String[i]=='7') && String[i]!=String[i+1])
      {
	 Success=true;
	 cut(String, i, 1, Local);
	 solve(Local);
	 test(Local, LocalMax);
      }
   for(i=0;i<int(strlen(String))-2;i++)
      if(String[i]==String[i+1] && String[i]==String[i+2] && 
	 String[i]!='7' && String[i]!='3' && String[i]!=String[i+3])
      {
	 Success=true;
	 cut(String, i, 3, Local);
	 solve(Local);
	 test(Local, LocalMax);
      }
   for(i=0;i<int(strlen(String))-6;i++)
      if(String[i]==String[i+1] && String[i]==String[i+2] && 
	 String[i]==String[i+3] && String[i]==String[i+4] && 
	 String[i]==String[i+5] && String[i]==String[i+6] && 
	 String[i]!=String[i+7] && String[i]!='7' && String[i]!='3')
      {
	 Success=true;
	 cut(String, i, 7, Local);
	 solve(Local);
	 test(Local, LocalMax);
      }
   Used[HashVal]=true;
   strcpy(Key[HashVal], String);
   if(Success)
      strcpy(String, LocalMax);
   test(String, Max);
   strcpy(Val[HashVal], String);
}

int main()
{
   int NumCases, i;
   char Line[Length];
   scanf("%d\n", &NumCases);
   for(i=0;i<HashSize;i++)
      Used[i]=false;
   while(NumCases-->0)
   {
      gets(Line);
      reverse(Line);
      strcpy(Max, "0");
      solve(Line);
      reverse(Line);
      printf("%s\n", Line);
   }
   return 0;
}

[Martin Macko]

Do you have any suggestions? Below is my code. I do not have any idea what is wrong with my code.

If still having WA... your code doesn't work on:

Code: Select all

6
4900006514979587103
9305660497031957126752544737246
13708976269278645181999140607
1427490008594779
107351103235212538538682
65244379091939972650698

My AC's output:

Code: Select all

5444516810650
14555260491408155596449826
569658564262150606668020
1424900085949
51119529691488501842
6524490919992650698

[Fali]

This is the output I got with your input:
INPUT

Code: Select all

6
4900006514979587103
9305660497031957126752544737246
13708976269278645181999140607
1427490008594779
107351103235212538538682
65244379091939972650698

OUTPUT

Code: Select all

4906514995810
11488469494221669969449966
186996609898064545105801
20921440849
11929005946806504298
1068519485428441198

I can't understand why I got diferent output than you. Please Can you explain me your output ?

[brianfry713]

Fali, my AC code's output matches yours.

Here's one of those outputs explained.

Code: Select all

1427490008594779 remove a 7
142749000859479 divide by 7
20392714408497 remove a 3
2092714408497 remove a 7
209271440849 remove a 7
20921440849