Google Code Jam- Deceitful War

Can any one explain me the 4th test case of the above question. How the answer is 8?

The link to the problem is as below:

Deceitful War

Thanks in advance.

This comment explains it.

1 Like
Naomi : 0.186   0.300   0.389   0.557   0.832   0.899   0.907   0.959   0.992

Ken   : 0.215   0.271   0.341   0.458   0.520   0.521   0.700   0.728   0.916

In deceitful war Naomi will fake as follows:

Original     Faked                                    Result

0.186        0.915                              Ken will choose 0.916 and Ken wins

0.300        0.729                              Ken will choose 0.215 and Naomi wins

0.389        0.730                              Ken will choose 0.271 and Naomi wins

0.557        0.731                              Ken will choose 0.341 and Naomi wins

0.832        0.832(no need to fake)     Ken will choose 0.458 and Naomi wins

0.899        0.899(no need to fake)     Ken will choose 0.520 and Naomi wins

0.907        0.907(no need to fake)     Ken will choose 0.521 and Naomi wins

0.959        0.959(no need to fake)     Ken will choose 0.700 and Naomi wins

0.992        0.992(no need to fake)     Ken will choose 0.728 and Naomi wins

The trick here is that Ken chooses weight by greedily looking at best for the current situation, so when Naomi fakes 0.915 Ken looks for a weight just greater than 0.915 and finds 0.916 but when Naomi fakes 0.729 Ken couldn’t find a weight greater than 0.729 so he chooses 0.215( Minimum available weight , as he knows that he’ll lose this round anyhow he selects the lightest weight to keep his future chances bright).

5 Likes

My solution yesterday(unmodified):small input correct.

enter code here

#include<stdio.h>

#include<conio.h>
#include<fstream.h>
#include<io.h>

void main()
{
clrscr();
FILE *fp1,*fp2;
fp1=fopen(“test.txt”,“r”);
fp2=fopen(“out1.txt”,“w”);
int tot,i;
fscanf(fp1,"%d",&tot);
for(i=1;i<=tot;i++){
printf(“Case #%d: “,i);
int n;
fscanf(fp1,”%d”,&n);
i=1;long float naomi[10],ken[10];
for(i=0;i<n;i++){
long float temp;
fscanf(fp1,"%lf",&temp);
naomi[i]=temp;}
i=0;
for(i=0;i<n;i++){
long float temp;
fscanf(fp1,"%lf",&temp);
ken[i]=temp;}
i=0;
int j=0;
int decwar=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(ken[i]<naomi[j])
{
decwar=decwar+1;goto step;
}

}
step:}
printf("%d ",decwar);
int war=0;

//for naomi
i=0;j=0;
int x=naomi[i],pos;i++;
while(i<n){
if(x<naomi[i]){x=naomi[i];pos=i;i++;}
else{i++;}
}
int maxnaomi=x;
//for ken
i=0;j=0;
int x1=ken[i],pos1=0;i++;
while(i<n){
if(x1<ken[i]){x1=ken[i];pos1=i;i++;}
else{i++;}
}
int maxken=x;

while(maxnaomi>maxken){
war=war+1;

i=0;
int x2=ken[i];int pos2=0;i++;
while(i<n){
if(x2>ken[i]){x2=ken[i];pos2=i;i++;}
else{i++;}
}
int minken=x2;

naomi[pos]=0;
ken[pos2]=0;

//for naomi
i=0;
int x=naomi[i],pos;i++;
while(i<n){
if(x<naomi[i]){x=naomi[i];pos=i;i++;}
else{i++;}
}
int maxnaomi=x;
//for ken
i=0;j=0;
int x1=ken[i],pos1=0;i++;
while(i<n){
if(x1>ken[i]){x1=ken[i];pos1=i;i++;}
else{i++;}
}
int maxken=x1;
}

printf("%d\n",war);
}
getch();
}}

}

Thanks a lot.

//