CONFLIP - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

CAKEWALK

PREREQUISITES

Ad Hoc, Simple Math

PROBLEM

In the game of Coin Flip there are initially N coins on the table. All these coins are either showing Heads or Tails. Let us say that the coins are arranged in a line, numbered from 1 to N.

You have to perform N operations in which you flip all the coins from position 1 to i in the ith round. You are to report the number of Heads / Tails after all the operations are complete.

QUICK EXPLANATION

It is easy to see that at the end of the game the coins would be in alternating positions, starting with either Heads or Tails. Therefore, either

HTHTHTHT...

Or,

THTHTHTH...

Therefore, you can easily deduce the number of Heads or Tails at the end of the game.

EXPLANATION

First, let us prove that the situation at the end of the game is indeed, alternating Heads and Tails.

Each coin is flipped a fixed number of times.

  • The first coin has been flipped N times. Once in each round.
  • The second coin has been flipped N-1 times. Once in each round except the first.
  • And so on…
  • The last coin has been flipped once.

We use the following insights,

  • A coin flipped even number of times, will show the same side, as it did initially.
  • A coin flipped odd number of times, will show the opposite side, of the one it did initially.

Now Let us consider two cases.

N is even

We can use the following insights,

  • All the coins at odd positions will be in their initial configuration.
  • All the coins at even positions will be opposite to their initial configuration.
  • There are as many even positions as there are odd positions.

Hence, no matter what the initial position is

  • The number of coins facing Head and Tail are equal.

Thus, the answer will always be N/2, for the query of Heads as well as Tails.

N is odd

We can use the following insights,

  • All the coins at even positions will be in their initial configuration.
  • All the coins at odd positions will be opposite to their initial configuration.
  • There are floor(N/2) coins in even positions, and ceil(N/2) coins in odd positions.

Hence, no matter what the initial position is

  • The number of coins that match the initial configuration are equal to floor(N/2).
  • The number of coins that do not match the initial configuration are equal to ceil(N/2).

Thus, assuming integer division, the answer will be N/2, for the query that matches the initial configuration. Otherwise the answer will be N/2 + 1.

This can be summerized as in the code below.

if (N % 2 == 0 || I == Q)
    print(N/2)
else
    print(N/2 + 1)

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

2 Likes
2

include <stdio.h>

int res[100];
int p=0;
void display(int m)
{
	res[p++]=m;

}

int main()
{
	int i, j, g, k, count[10][10], a[10][3], t, m;
	char s[10][10];
	clrscr();
	scanf("%d", &t);
	for(m=0;m<t;m++)
	{
	scanf("%d",&g);
	for(i=0; i<g; i++)
	{
		scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
		for(j=0; j<a[i][1]; j++)
		{
		if (a[i][0] == 1)
		s[i][j] = 'H';
		else
		if (a[i][0] == 2)
		s[i][j] = 'T';
		}
		s[i][j] = '\0';
	for(j=1; j<=a[i][1]; j++)
	{
		for(k=0; k<j; k++)
		{
		if(s[i][k] == 'H')
		s[i][k]='T';
		else
		s[i][k]='H';
		}

	}
	}
	for(i=0; i<g; i++)
	{
	count[m][i]=j=0;
	if(a[i][2] ==1)
	while(s[i][j]!='/0')
	{
	if(s[i][j] == 'H')
	count[m][i]++;
	j++;
	}
	else
	if(a[i][2] ==2)
	while(s[i][j]!='/0')
	{
	if(s[i][j] == 'T')
	count[m][i]++;
	j++;
	}
	display(count[m][i]);
	}
	}
	for(i=0;i<p;i++)
	printf("%d\n",res[i]);
	return 0;

}

I have compiled my code even with linux, but it it showing runtime error. I am facing such problems for a long time. Please help.

3

@jatin_b it seems you have removed conio.h but have forgotten to remove clrscr(); from your code…
I wonder how can your code posted can compile sucessfully in linux then…
Resubmit it now…
Hope it doesn’t show RTE then…

4

#include<stdio.h>
#include<stdlib.h>
main()
{
int t,g,i,q;
long int n,j,ctr,k;
int a;
scanf("%d",&t);
while(t–)
{
ctr=0;
scanf("%d",&g);
while(g–)
{
scanf("%d%ld%d",&i,&n,&q);
a=(int)malloc(n*sizeof(int));
for(j=1;j<=n;j++)
{
a[j]=i;
}
for(j=1;j<=n;j++)
{
for(k=1;k<=j;k++)
{
if(a[k]==1)
{
a[k]=2;
}
else if(a[k]==2)
{
a[k]=1;
}
}
}
for(j=1;j<=n;j++)
{
if(a[j]==1)
ctr++;
}
}
if(q==1)
{
printf("%ld\n",ctr);
}
else
{
printf("%ld\n",n-ctr);
}
}
return 0;
}

i have compiled and run my code in my turbo c++ dosbox and it ran correctly but it shows runtime error ie. sigsegv on the online judge… ie segmentation error… how to over come this ?

please help/

5

You are declaring too much memory for a . The limit for n is 1 ≤ N ≤ 10^9 .you cant have so much memory . In turbo C++ also if you also try to run for such big value I am sure it wont run . try to do this without having so much memory .

6

I have more or less used the same logic but my submission gives wrong answer.
http://www.codechef.com/viewsolution/5963715

Could someone tell me the corner cases?

7

@arpan…you’re not checking if i==q…in case n is odd…no of coins=n/2+1 when i is not equal to q…but n/2 if i==q

8

#include<stdio.h>
char replace(char);
int main()
{
int n,i,I,k,q,h=0,t=0,T,G;
char arr[1000];
scanf("%d",&T);
while(T–)
{
while(G–)
{
scanf("%d",&G);
scanf("%d%d%d",&I,&n,&q);
for(i=0;i<n;i++)
{
if(I==1)
{
arr[i]= ‘h’;
}
else
{
arr[i]= ‘t’;
}
}
for(i=0;i<n;i++)
{
if(I==1)
{
arr[i]=‘t’; }
else
{
arr[i]=‘h’;}
for(k=i-1;k>=0;k–)
{
arr[k]= replace(arr[k]);
}
}
for(i=0;i<n;i++)
{
if(arr[i]==‘h’)
{
h++;
}
else
{
t++;
}
}
if(q==1)
{
printf("%d",h);
}
else{
printf("%d",t);
}
}
}

return 0;

}
char replace(char ch)
{
if(ch==‘h’)
{
ch=‘t’;
}
else
{
ch=‘h’;
}
return(ch);
}

its showing runtime error. please someone tell me why??

9

#include
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
void coin1()
{
long int t,j,k,i,n,g,c=0,d=0,m,q;
cin>>t;
while(t>=1)
{
cin>>g;
char a[g];
while(g>=1)
{

			cin>>i>>n>>q;
			for(j=1;j<=n;j++)
			{
				if(i==1)
				{
					a[j]='H';
				}
				else if(i==2)
				{
					a[j]='T';
			}
			}
				for(k=1;k<=n;k++)
		{
			for(j=1;j<=n;j++)
			{
				if(j<=k)
				{
					if(a[j]=='H')
					{
						a[j]='T';
					}
					else if(a[j]=='T')
					{
						a[j]='H';
					}
				}
				
			}
		}
		j=1;
		while(j<=n)
	{
		if(a[j]=='H')
		{
			c++;
			//cout<<c<<endl;
		}
		else if(a[j]=='T')
		{
			d++;
		}
		j++;
	}
	if(q==1)
	{
		cout<<c<<endl;
	}
	else if(q==2)
	{
		cout<<d<<endl;
	}
		c=0;
	d=0;
	g--;
	}
c=0;
d=0;

	t--;

}
}

int main()

{
coin1();
}

10

i have also runtime error problem please help

11

I executed your code @arus_47

Firstly, I removed that “include<bits stdc++.h=”">" as it led to fatal error.

After that, I put in custom input of Sample case and your code passed. I think that line was the problem.

I suggest removing “include<bits stdc++.h=”">" from your code

(EDIT-The correct code is #include < bits/stdc++.h > Also, the ‘#’ were missing in first three lines. Please see to it dear!)

:slight_smile:

(Upvote if you like my answer, so that I can also ask questions :slight_smile: )

12

#include
using namespace std;
int main()
{
int t,n,i,g,q;
cin>>t>>n;
while(t–)
{
while(n–)
{
int h=0;
cin>>i>>g>>q;
h=g/2;
if(g%2==0)
{
if(q==1||q==2)
cout<<h<<endl;
}
else
{
if(i==q)
cout<<h<<endl;
else
cout<<h+1<<endl;
}

  }

}
return 0;
}

13

can anyone tell me what’s wrong in this…?

https://www.codechef.com/viewsolution/14978375

14

I am using the same logic but getting time limit exceeded error.
Here is my code:
Click Here

15

My Code Exceeds Time Limit
Can anyone help me with this code
https://ide.geeksforgeeks.org/UWvwhmGwH0