You are not logged in. Please login at www.codechef.com to post your questions!

×

CONFLIP - Editorial

3
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.

This question is marked "community wiki".

asked 12 Nov '12, 18:20

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 13 Nov '12, 14:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


# 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.

link

answered 13 Nov '12, 01:53

jatin_b's gravatar image

1★jatin_b
1
accept rate: 0%

edited 13 Nov '12, 02:06

betlista's gravatar image

3★betlista ♦♦
16.9k49115225

@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..

(13 Nov '12, 02:04) xpertcoder4★

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/

link

answered 25 Jun '14, 17:35

karankapoor's gravatar image

2★karankapoor
-112
accept rate: 0%

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 .

(25 Jun '14, 17:40) the65bit4★

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?

link

answered 22 Jan '15, 22:02

arpan_'s gravatar image

2★arpan_
1
accept rate: 0%

@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

link

answered 22 Jan '16, 19:37

shandilya's gravatar image

0★shandilya
1
accept rate: 0%

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&lt;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??

link

answered 14 Aug '16, 16:55

gaurav_096's gravatar image

0★gaurav_096
1
accept rate: 0%

edited 14 Aug '16, 17:02

include<iostream>

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(); }

link

answered 24 Jan '17, 02:15

arus_47's gravatar image

1★arus_47
1
accept rate: 0%

i have also runtime error problem please help

link

answered 24 Jan '17, 02:15

arus_47's gravatar image

1★arus_47
1
accept rate: 0%

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!)

^_^

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

link

answered 25 Jan '17, 11:32

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 25 Jan '17, 12:43

include<iostream>

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; }

link

answered 11 Jul '17, 21:16

sheteyash's gravatar image

1★sheteyash
1
accept rate: 0%

can anyone tell me what's wrong in this..?

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

link

answered 15 Aug '17, 16:20

strawhatdragon's gravatar image

2★strawhatdragon
435
accept rate: 0%

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

link

answered 14 Nov '17, 08:44

nmsjha's gravatar image

1★nmsjha
11
accept rate: 0%

edited 14 Nov '17, 08:46

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,719
×1,662
×952
×281
×17

question asked: 12 Nov '12, 18:20

question was seen: 10,241 times

last updated: 14 Nov '17, 08:46