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

×

Need help with this hourrank-2 question !!

0
1

https://www.hackerrank.com/contests/hourrank-2/challenges/gugas-function . I read the editorial but it was very terrible. How to solve this?

asked 04 Nov '15, 00:44

AnoopNarang's gravatar image

3★AnoopNarang
183
accept rate: 0%

edited 04 Nov '15, 00:45


Hello @ AnoopNarang

consider you are 5 digits(n=5)
now you can place 10001 only in one way.
1*1=1

you can place 1001 in two ways
_ 1001
1001 _
here each way will give two possible ans.
2*2=4
Similarly you can  place 101 in 3 ways
101 _ _
_ 101 _
_ _ 101
here each way will give 4 possible ans.
4*3=12

total ans= 12 + 4 + 1=17
If you notice for other higher didgits too .  you will get a general formula
total ans =summation of ( pow(2,i-1)*i ) , where i will vary from 1 to n-2.

here is my code for the same problem

#include<stdio.h>
# define M 1000000009
int main()
{
 int n,i;
 long long int sum=1;
 long long int temp=1;
 scanf("%d",&n);
 if(n==3)
    {
      printf("1\n");
    }
 else
 {
    for(i=2;i<=n-2;i++)
   { temp=temp*2;
    if(temp>=M)
    {
     temp=temp%M;
    }
   sum = sum + (temp*i) ;
   if(sum>M)
    sum=sum%M;
 }
 printf("%lld\n",sum);
 }
  return 0;
}

happy coding

link

answered 04 Nov '15, 15:16

va1ts7_100's gravatar image

3★va1ts7_100
4721732
accept rate: 11%

edited 04 Nov '15, 15:42

I checked your answer, its getting accepted. But i did not get

Similarly you can place 101 in 3 ways 101 _ _ _ 101 _ _ _ 101 here each way will give 4 possible ans. 4*3=12

Wont there be repetitions in these 12 combinations. Like 101 _ _ -------- 101[01]
_ _ 101 -------- [10]101

(04 Nov '15, 20:19) AnoopNarang3★

@Anoopnarang, you can draw this on paper for 5 digits. then you will understand better why there will not be repetition . Bcoz when i was solving this question , i was confused too like you , and i solved it by drawing cases on paper..!

Short exlanation-: in number 10101, there will be two contributions to the ans , starting (101) and ending (101) , and my approach counted it twice too so , no repititions !

(05 Nov '15, 01:50) va1ts7_1003★

Ok got it ... thanks for the efforts man !!

(05 Nov '15, 11:16) AnoopNarang3★

anytime bro :)

(05 Nov '15, 11:40) va1ts7_1003★

@AnoopNarang

Since the contest is of 1 hour, just try to do the problem in another way also(shortcut) as follows.

f(1) = 0

f(2) = 1

f(3) = 5

f(4) = 17

So, now that u have got some numbers check for the common formula/pattern in OEIS(CLICK HERE FOR SOLUTION)

So, the formula is (n-1)*2^n + 1.

so, in this way, u can get AC in 5-8 minutes max. but the most important thing is that u must definitely read and understand the editorial after the contest.

PS:- Even i also did not get this question accepted becoz i took n^2 instead of 2^n and messed up everything. Also,even i did not understand editorial properly.

link

answered 04 Nov '15, 20:38

shiva_google's gravatar image

2★shiva_google
974
accept rate: 0%

edited 04 Nov '15, 21:00

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:

×310

question asked: 04 Nov '15, 00:44

question was seen: 2,048 times

last updated: 05 Nov '15, 11:40