Ambiguous Problem Help

c
practice

#1

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 <stdio.h>

# 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] !='

')
{
if(byteRead==BUFFER)
{
ret = fread(input, sizeof(char), BUFFER, stdin);
byteRead=-1;
}

		else if(input[byteRead]!=' ' && input[byteRead]!='

‘)
{
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

");
}
else
printf("not ambiguous
");

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

#2

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. :slight_smile:


#3

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 !


#4

I can, but I assume to produce output within time-limit, fread() cam help. Is it where I am wrong ?


#5

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. :slight_smile:


#6

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.


#7

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.


#8

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.