1262 - Password

All about problems in Volume 12. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

1262 password-why i got wrong answer

Post by nai_kew »

I think my code is right and I even test it on ideone.com .
someone help me please here is my code

Code: Select all

import java.util.*;
import java.io.*;
import java.util.Arrays;
class Main
{
	public static void main(String[]args)
	{
		int caseNum;
		int[] passNum;
		int[] passCount;
		int rowTxt = 6;
		int colTxt = 5;
		
		String str1,str2;
		String[][][] plate1;
		String[][][] plate2;
		
		String[][][] colSame;
		String[][][] colSameTmp;
	
		boolean same = false;

		int[][] colSameCount;
		int[] possCol = new int[colTxt];	

     			
		Scanner keyBoard = new Scanner(System.in);

		caseNum =  keyBoard.nextInt();
		passNum = new int[caseNum];
			
		passCount = new int[caseNum];
		int count = 0;
			
		plate1 = new String[caseNum][colTxt][rowTxt];
		plate2 = new String[caseNum][colTxt][rowTxt];
		colSame = new String[caseNum][colTxt][];
		colSameTmp = new String[caseNum][colTxt][rowTxt];
		colSameCount = new int[caseNum][colTxt];

		for (int i = 0; i< caseNum;i++)
		{
			passNum[i] =  keyBoard.nextInt();
			keyBoard.nextLine();
			for (int j = 0; j<rowTxt; j++)
			{		
				str1 =  keyBoard.nextLine();
				for (int k =0; k<str1.length(); k++)
				{
					plate1[i][k][j] = str1.substring(k,k+1);

				}
			}
			for (int j = 0; j<rowTxt; j++)
			{	
				str1 = keyBoard.nextLine();
				for (int k =0; k<str1.length(); k++)
				{
					plate2[i][k][j] = str1.substring(k,k+1);

				}
			}
			
			for (int j = 0; j<colTxt; j++)
			{
				for (int k = 0; k<rowTxt; k++)
				{
					str1 = plate1[i][j][k];
					same = false;
					int x = 0;
					while ((same == false) && (x<rowTxt))
					{
						str2 = plate2[i][j][x];
						if (str1.equalsIgnoreCase(str2))
						{
								
							colSameTmp[i][j][colSameCount[i][j]] = str1;
							colSameCount[i][j] = colSameCount[i][j]+1;
							same = true;	
						}
						x = x+1;
					}
				}
			}
			
			for (int j= 0; j<colTxt; j++)
			{
				colSame[i][j] = new String[colSameCount[i][j]];
				for (int k =0; k<colSameCount[i][j] ; k++)
				{
					colSame[i][j][k] = colSameTmp[i][j][k];
				}
				Arrays.sort(colSame[i][j]);
			}				
			
			possCol[0] = colSame[i][colTxt-1].length;
			for (int j = 1; j<colTxt; j++)
			{
					
				possCol[j]=colSame[i][colTxt-1-j].length*possCol[j-1];
			}
			if ((possCol[colTxt-1] < passNum[i] ) || (passNum[i]==0))
			{
				System.out.print("NO");
			}
			else
			{
				passNum[i]= passNum[i]-1;
				System.out.print(colSame[i][0][passNum[i] / possCol[colTxt-2]]
				+colSame[i][1][(passNum[i]%possCol[colTxt-2]) /possCol[colTxt-3]]
				+colSame[i][2][((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])/possCol[colTxt-4]]
				+colSame[i][3][(((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])%possCol[colTxt-4]) /possCol[colTxt-5]]
				+colSame[i][4][((((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])%possCol[colTxt-4]) %possCol[colTxt-5])]);		
			}
			System.out.println();	
		}					
	}
}


nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

uva 1262 - got wrong answer

Post by nai_kew »

I dont know why I got worng answer.
I already test my code at ideone.com and I think my answer is right
here is my code

Code: Select all

import java.util.*;
import java.io.*;
import java.util.Arrays;
class Main
{
	public static void main(String[]args)
	{
		int caseNum;
		int[] passNum;
		int[] passCount;
		int rowTxt = 6;
		int colTxt = 5;
		
		String str1,str2;
		String[][][] plate1;
		String[][][] plate2;
		
		String[][][] colSame;
		String[][][] colSameTmp;
	
		boolean same = false;

		int[][] colSameCount;
		int[] possCol = new int[colTxt];	

     			
		Scanner keyBoard = new Scanner(System.in);

		caseNum =  keyBoard.nextInt();
		passNum = new int[caseNum];
			
		passCount = new int[caseNum];
		int count = 0;
			
		plate1 = new String[caseNum][colTxt][rowTxt];
		plate2 = new String[caseNum][colTxt][rowTxt];
		colSame = new String[caseNum][colTxt][];
		colSameTmp = new String[caseNum][colTxt][rowTxt];
		colSameCount = new int[caseNum][colTxt];

		for (int i = 0; i< caseNum;i++)
		{
			passNum[i] =  keyBoard.nextInt();
			keyBoard.nextLine();
			for (int j = 0; j<rowTxt; j++)
			{		
				str1 =  keyBoard.nextLine();
				for (int k =0; k<str1.length(); k++)
				{
					plate1[i][k][j] = str1.substring(k,k+1);

				}
			}
			for (int j = 0; j<rowTxt; j++)
			{	
				str1 = keyBoard.nextLine();
				for (int k =0; k<str1.length(); k++)
				{
					plate2[i][k][j] = str1.substring(k,k+1);

				}
			}
			
			for (int j = 0; j<colTxt; j++)
			{
				for (int k = 0; k<rowTxt; k++)
				{
					str1 = plate1[i][j][k];
					same = false;
					int x = 0;
					while ((same == false) && (x<rowTxt))
					{
						str2 = plate2[i][j][x];
						if (str1.equalsIgnoreCase(str2))
						{
								
							colSameTmp[i][j][colSameCount[i][j]] = str1;
							colSameCount[i][j] = colSameCount[i][j]+1;
							same = true;	
						}
						x = x+1;
					}
				}
			}
			
			for (int j= 0; j<colTxt; j++)
			{
				colSame[i][j] = new String[colSameCount[i][j]];
				for (int k =0; k<colSameCount[i][j] ; k++)
				{
					colSame[i][j][k] = colSameTmp[i][j][k];
				}
				Arrays.sort(colSame[i][j]);
			}				
			
			possCol[0] = colSame[i][colTxt-1].length;
			for (int j = 1; j<colTxt; j++)
			{
					
				possCol[j]=colSame[i][colTxt-1-j].length*possCol[j-1];
			}
			if ((possCol[colTxt-1] < passNum[i] ) || (passNum[i]==0))
			{
				System.out.print("NO");
			}
			else
			{
				passNum[i]= passNum[i]-1;
				System.out.print(colSame[i][0][passNum[i] / possCol[colTxt-2]]
				+colSame[i][1][(passNum[i]%possCol[colTxt-2]) /possCol[colTxt-3]]
				+colSame[i][2][((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])/possCol[colTxt-4]]
				+colSame[i][3][(((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])%possCol[colTxt-4]) /possCol[colTxt-5]]
				+colSame[i][4][((((passNum[i]%possCol[colTxt-2]) % possCol[colTxt-3])%possCol[colTxt-4]) %possCol[colTxt-5])]);		
			}
			System.out.println();	
		}					
	}
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

Don't double post.
Last edited by brianfry713 on Wed Oct 03, 2012 8:17 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

Re: 1262 password-why i got wrong answer

Post by nai_kew »

can someone help me please
I just want to know what is the correct output for this input

Code: Select all

21
0
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
1
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
2
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
3
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
5
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
12
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
13
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
14
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
33
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
34
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
35
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
36
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
37
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
0
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
1
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
3888
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
7776
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
7777
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
1
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
5
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
64
FGHIJ
EFGHI
DEFGH
CDEFG
BCDEF
ABCDE
WBXDY
UWYXZ
XXZFG
YYFYH
EZWZI
ZGHIJ
here is my output

Code: Select all

NO
AAMSO
AAMST
AANSO
AIMSO
AJNST
BAMSO
BAMST
DJMSO
DJMST
DJNSO
DJNST
NO
NO
AAAAA
CFFFF
FFFFF
NO
ABGAG
ABGPS
NO

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

Your input isn't valid, K can't be 0.
Edited to remove incorrect I/O.
Last edited by brianfry713 on Tue Oct 02, 2012 9:27 pm, edited 3 times in total.
Check input and AC output for thousands of problems on uDebug!

nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

Re: 1262 password-why i got wrong answer

Post by nai_kew »

arrgh your output make me really confuse now.
first
I dont understand how k change from 1 to 5 with same input and your output is all the same AAMSO
or k change from 33 to 36 and your output is AIMST
second
when k = 7777 output should be "NO"? because all maximum possible password is 7776
third
the last 3case I copy sample input from the problem page and the output is
ABGAG
ABGPS
NO

but you output is
ABGAG
ABGAG
EBFII

sorry for ask too many questions. I am new to this programming thing, maybe I misunderstand something. thank you for your help

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

I deleted the incorrect output I posted. For this input:

Code: Select all

21
1
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
1
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
2
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
3
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
5
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
12
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
13
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
14
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
33
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
34
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
35
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
36
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
37
DHOSC
BIMKA
CBNMT
AAPPB
EDABO
FJKCY
HAMTD
AJDSK
OINOO
YCCAG
BOBDT
DSTJX
1
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
1
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
3888
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
7776
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
7777
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
ABCDE
BCDEA
CDEAB
DEABC
EABCD
FFFFF
1
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
5
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
64
FGHIJ
EFGHI
DEFGH
CDEFG
BCDEF
ABCDE
WBXDY
UWYXZ
XXZFG
YYFYH
EZWZI
ZGHIJ
The correct output is:

Code: Select all

AAMSO
AAMSO
AAMST
AANSO
AIMSO
AJNST
BAMSO
BAMST
DJMSO
DJMST
DJNSO
DJNST
NO
AAAAA
AAAAA
CFFFF
FFFFF
NO
ABGAG
ABGPS
NO
Check input and AC output for thousands of problems on uDebug!

nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

Re: 1262 password-why i got wrong answer

Post by nai_kew »

lol so your output and my output is exactly the same (if i change input k from 0 to 1)
and i still got wrong answer

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

Input:

Code: Select all

1
9
MZRHL
AJOET
BKWLT
ZTVIE
MHPFY
BPSWA
EBJZT
YLNIE
EXKSZ
GASXF
VPXFF
BUPCR
AC output:NO
I used backtracking to generate all possible password strings without duplicates, sorted them, then print the K'th string from the sorted array if it exists. I didn't need to do any division or modulus. My code is simple and short. Don't store all the previous cases when you don't need to. On some problems you'll have a lot of test cases.
Last edited by brianfry713 on Mon Feb 04, 2013 11:18 pm, edited 1 time in total.
Check input and AC output for thousands of problems on uDebug!

nai_kew
New poster
Posts: 6
Joined: Wed Sep 26, 2012 9:28 pm

Re: 1262 password-why i got wrong answer

Post by nai_kew »

Finally got accept. Thank you so much brianfry713 for you help. i didnt know that input can be same character in same column

Code: Select all

ABCDE
ABCDE
ABCDE
ABCDE
ABCDE
ABCDE
as I told you I'm new to this programing thing.
first time i didnt know how to read input or present output (do i need to read it all every case 1 time and
then print the output all case at 1 time or read 1 case and print 1 case)
that why i using array like that make it look complicate. now i know how to the thing here thank you so much

tiendaotd
New poster
Posts: 12
Joined: Mon Jan 14, 2013 12:21 pm

Re: 1262 password-why i got wrong answer

Post by tiendaotd »

brianfry713 wrote:Input:

Code: Select all

1
9
MZRHL
AJOET
BKWLT
ZTVIE
MHPFY
BPSWA
EBJZT
YLNIE
EXKSZ
GASXF
VPXFF
BUPCR
AC output:BPPFT
I used backtracking to generate all possible password strings without duplicates, sorted them, then print the K'th string from the sorted array if it exists. I didn't need to do any division or modulus. My code is simple and short. Don't store all the previous cases when you don't need to. On some problems you'll have a lot of test cases.
I don't think your output is correct . My AC code output "NO" . I think it's obvious that there're only 8 < 9 possible password here, so the ouput should be "NO".
Last edited by tiendaotd on Tue Feb 19, 2013 12:27 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

You're right, the output should be NO. I edited my previous post.

The common letters are:
column 1: B, column 2: P, column 3: PS, column 4: FI, solumn 5: ET
The 8 valid passwords are: BPPFE, BPPFT, BPPIE, BPPIT, BPSFE, BPSFT, BPSIE, BPSIT
Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 1262 password-why i got wrong answer

Post by tamim1382csedu19 »

I see the pictures with the problem are broken.. I cant understand them problem without the pics.. Can anyone upload the pics please?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 1262 password-why i got wrong answer

Post by brianfry713 »

Check input and AC output for thousands of problems on uDebug!

tamim1382csedu19
New poster
Posts: 18
Joined: Mon Jun 03, 2013 5:09 pm

Re: 1262 password-why i got wrong answer

Post by tamim1382csedu19 »

Getting WA.. can anyone give some critical I/O ?
Here's my code http://ideone.com/ctHs0p

Post Reply

Return to “Volume 12 (1200-1299)”