×

# CHEFLR - Editorial

 1 Problem link : contest practice Difficulty : Simple Pre-requisites : basic math Solution : The problem is one of the easiest in the set. The solution is as follows. When we have an odd-length string S, we can make one turn and set some flag the the answer is even. Otherwise, we should keep in mind than the answer is odd. The remaining part always has even length, and we can threat the tree as the octary one and numerate the nodes by consecutive natural numbers. When we have found the node number in this tree, we will only need to multiply it by two and possibly to subtract one. The tree is octary, so the consecutive symbols can be grouped in pairs and each pair will denote a single edge of the tree. Namely, in the order from left to right the order of pairs is "ll", "lr", "rl", "rr". So we just maintain the variable index and each time we traverse one edge of our tree, we multiply it by 4, and then add -2, -1, 0 or 1, depending on the type of the edge: -2 for "ll", -1 for "lr" and so on. At the end we just need to find the index-th even (or odd) number. The parity depends on the parity of the length of the string that denotes the path. Setter's solution: link Tester's solution: link This question is marked "community wiki". asked 15 Sep '14, 15:32 719●43●63●77 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 8 Or we could do something like the following - For each level, keep a counter whether the level number is odd or even. We have ans = root = 1 Now traverse through the string. If the next character is 'l' and we are on an even numbered level - ans = ans x 2 else if the next character is 'l' and we are on an odd numbered level - ans = ans x 2 - 1 else if the next character is 'r' and we are on an even numbered level - ans = ans x 2 + 2 else if the next character is 'r' and we are on an add numbered level - ans = ans x 2 + 1  Finally, print ans  answered 15 Sep '14, 17:36 264●5●11 accept rate: 0% This wasn't working. TLE error. (15 Sep '14, 21:57) This worked for me. Are you sure nothing else was wrong with your code? (16 Sep '14, 22:40) It will work. It worked for me too. And most probably 90% of people have tackled this problem this way. @chefkaushik94 : Optimize your code. (16 Sep '14, 22:46) ketanhwr6★ I did the same. But it shows WA. Can someone please tell my mistake? http://www.codechef.com/viewsolution/4807475 (17 Sep '14, 17:17) Please someone let me know what's wrong with my code http://www.codechef.com/viewsolution/4811858 I followed the same method, and it worked for provided test cases, but on submission, it keeps showing wrong answer. (20 Sep '14, 13:40) rok07072★ @rok0707 modulo 10^9+7. (02 Oct '14, 14:03) amitt0012★ @rok0707 hi.. here is your corrected solution https://www.codechef.com/viewsolution/7887676 here I want to mention something which you may havn't taken care first one when you are taking mod some even level value may be convert into odd value because there are so many times mode happen that's why you should a separate variable for keeping track of level or you can use index also second one may be your root[i] is exact multiple or equal to mod than root[i]%mod=0 later (may be )2*root[i]-1 become negative hope it help you.. happy coding (22 Aug '15, 17:23) showing 5 of 7 show all
 0 char a size should be 100000+1. This extra one byte is to hold '\0' value. answered 16 Sep '14, 13:33 6●4 accept rate: 0%

Can anyone tell me for which input my code is not working

# include<string.h>

char s[1000000];

unsigned long long int flag=1,ans,x,a;

using namespace std;

int main()

{

unsigned long long int t,i,p=1,n=0,k=0,z=0;

unsigned long long int flag,ans=1000000007,x;

cin>>t;

for(i=0;i<t;i++)

{ flag=1; p=1,n=0,k=0,z=0;

cin>>s;

a = strlen(s);

while(a)

{

n = (p % 2) - 1;

k = 2 + n;
if(s[z] == 'l')
{
flag = flag*2 + n;

}
else if(s[z] == 'r')

flag = flag*2 + k;

p++;
z++;
a--;
}


flag = flag % ans;

printf("%lld\n",flag);

}

}

1★denial27
1
accept rate: 0%

 0 Can someone help me understand why my code, here, has failed? I think it's OK unless it's a fence post ever that I'm not able to figure out. answered 18 Sep '14, 05:44 1 accept rate: 0%
 0 Can someone please tell me what is wrong with my code found here http://www.codechef.com/viewsolution/4728506 answered 19 Sep '14, 17:34 1 accept rate: 0%
 0 Can anyone please figure it out why the enormous input method is unable to fetch the string from buffer ? Please!! //Chef Left-Right #include #include #define BUFFER 1000000 int main() { int test, i ,value=1, length,n,j=0; int limit=1000000007; char array[BUFFER+1]; scanf("%d",&test); while((n = fread(array, 1, BUFFER, stdin))) { if(test == 0) break; for(i=0; i
 0 I dont understand the editorial explanation, can someone elaborate in simple terms ? answered 18 Dec '14, 09:46 2★bicepjai 11 accept rate: 0%
 0 @rok0707 hi.. here is your corrected solution your corrected solution (AC) here I want to mention some points which you may havn't taken care POINT 1 first one when you are taking mod some even level value may be convert into odd value because there are so many times mode happen that's why it is possible Solution 1 you should a separate variable for keeping track of level or you can use index also POINT 2 second one may be your root[i] is exact multiple or equal to mod than root[i]%mod=0 later (may be )2*root[i]-1 become negative Solution 2 always check if(root[i]>=mod) root[i]%=mod root[i]=(root[i]+mod)%mod; hope it help you.. happy coding answered 22 Aug '15, 17:29 1.1k●12●29 accept rate: 6%
 0 Can anyone let me know whats wrong with my solution. I have done the same but getting WA. https://www.codechef.com/viewsolution/18744849 Thanks in advance answered 03 Jun '18, 03:39 5●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,680
×1,173
×947
×167
×61

question asked: 15 Sep '14, 15:32

question was seen: 4,803 times

last updated: 03 Jun '18, 03:41