×

# Ambiguous Problem Help

 0 I am trying my hands on Ambiguous Permutation problem listed under Easy problems in Practice Section. I have employed logic that if I make a number out of provided combination and again create a number based on its inverse permutation, if both numbers are same, it would be an ambiguous permutation. Consider the first test input 1 4 3 2 According to logic, I take an integer initial that would take hold number made out of given permutation and final would hold up number made out of its inverse permutation. So, here is calculation of initial, initially initial and final are 0. powr() is a function here, It gives out 10^n. And till holds number of numbers in test case, so, till=4 and limit holds copy of till. initial = initial10 + numberpowr(till-1); till--; so, For First, initial = 0 + 1*10^(4-1); initial = 1000; initial = 1000 + 4*10^(3-1); initial = 1000 + 400; initial = 1400; initial = 1400 + 3*10(2-1) initial = 1400 + 30 initial = 1430 initial = 1430 + 2*10(1-1) initial = 1432; And for final computation final= final + currIndex*10^(limit-num); final = 0 + 1*10^(4-1) final = 0 + 1000 final = 1000 final = 1000 + 2*10^(4-4) final = 1000 + 2 final = 1002 final = 1002 + 3*10^(4-3) final = 1002 + 30 final = 1032 final = 1032 + 4*10^(4-2) final = 1032 + 400 final = 1432 Both numbers are same. But I am getting wrong answer for my solution. I don't wish to copy other's solution. I want to know error of my way. By the way, logic works for numbers >10. I have checked. Here is code. # include # define BUFFER 32678 # define true 1 # define false 0 static char input[BUFFER]; static char store[100001]; int powr(int); int main() { int ret, byteRead=0, cont, till=0, initial=0, final=0, firstIndex=0, currIndex=0, passedFirst=0, limit, num=0; cont = 4; ret = fread(input, sizeof(char), BUFFER, stdin); while(cont) { while(byteRead < ret && input[byteRead] >= '0') { till = till*10 + (input[byteRead]-'0'); limit= till; byteRead++; } if(till==0) { cont=false; continue; } while(byteRead < ret && input[byteRead] <'0') { byteRead++; } while(byteRead < ret && input[byteRead] !='\n') { if(byteRead==BUFFER) { ret = fread(input, sizeof(char), BUFFER, stdin); byteRead=-1; } else if(input[byteRead]!=' ' && input[byteRead]!='\n') { num = num*10 + (input[byteRead]-'0'); } else if(input[byteRead]==' ') { initial = initial + (num * powr(till-1)); if(passedFirst == false) { currIndex=1; passedFirst = true; } final = final + currIndex*powr(limit-num); currIndex++; num =0; till--; } byteRead++; } passedFirst=false; initial = initial + (num * powr(till-1)); final = final + currIndex*powr(limit-num); if(final == initial) { printf("ambiguous\n"); } else printf("not ambiguous\n"); till= final = initial =0; byteRead++; num=0; currIndex=1; } return 0; } int powr(int n) int mul=1,i; for(i=1;i<=n;i++) { mul = mul*10; } return mul; }  asked 29 Oct '13, 04:04 66●2●2●6 accept rate: 100% why don't you use standard C library to read the standard input ? i mean scanf() ? it would probably be easier, and less error-prone. By the way, logic works for numbers >10. I have checked.  really ? what would be initial and final values for N = 10 ? let's say the permutation is 1 2 3 4 5 6 7 8 10 9 : initial = 1234567909 final = 1234567900 this permutation should be considered ambigous. moreover, storing them in simple C integers won't fit. it cannot hold a number with 10^5 digits. i think you'll need another approach. good luck ! (29 Oct '13, 04:21) I can, but I assume to produce output within time-limit, fread() cam help. Is it where I am wrong ? (29 Oct '13, 04:26) no, but you shouldn't worry about the time limit in the first attempt. the main step is at first to get a correct algorithm. then, if you obtain TLE (time limit exceeded) with a fast algorithm, it'll be time to solve performance issues the hard way. :) (29 Oct '13, 04:34) I have made fallowing test case for myself. 4|1 4 3 2|5|2 3 4 5 1|1|1|11|1 4 3 2 11 8 10 6 9 7 5|10|5 8 7 6 1 4 3 2 10 9|10|5 8 7 6 1 4 3 10 2 9|0| | = newLine And I am receiving output as ambiguous|not ambiguous|ambiguous|ambiguous|ambiguous|not ambiguous It's right. It works for n=11 and 10. (29 Oct '13, 04:38)

 1 please run you code with this test case : 10 1 2 3 4 5 6 7 8 10 9  and even if your algorithm was correct, simple C integers cannot hold such large values. just try with N = 15, choose any permutation you want, and look at the initial and final values. :) answered 29 Oct '13, 04:43 3.4k●2●19●55 accept rate: 20% Damn. I need a new algo. I was thinking that I can create 12354 from 1 2 3 5 4 but I wasn't thinking that for very large list, it would overflow. Thanks anyway. (29 Oct '13, 04:53) you're welcome. good luck ! you can be proud for finding a solution by your own. in my opinion, it's the better way to make progress in programming. (29 Oct '13, 04:55)
 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:

×1,490
×558

question asked: 29 Oct '13, 04:04

question was seen: 1,453 times

last updated: 29 Oct '13, 04:55