ANKPAREN - Editorial

Can any one help me understand why this code (gist link) is giving NZEC?

Edit: A slightly modified solution (gist link) to consider bad input gave me AC.

I’m getting NZEC but I can’t understand why. I’ve verified my answers for all possible input strings up to length 12, and thousands of random input strings up to max length. Here is my code, it uses the same method as the official solution. public static String ANKPAREN(char[] s, int k, String str) on line 87 is the method that does the actual work.

EDIT: to be clear I don’t care if my solution is correct or not, I’m just looking for a way that it can break (NZEC).

EDIT 2: I found the problem: when I read the input I have to say:

String s = scan.next();

instead of

String s = scan.nextLine();

I always use nextLine() in CodeChef competitions, and both cases work on the sample input. This means my answer was correct but failed due to bad input. This is very disappointing. :frowning:

1 Like

what will be the answer for an empty sequence as in the question it is mentioned to be regular ?

Blockquote
“So, to produce L2n we need to de…”

what is L2n ? more specifically what is n ?
If n is the length of the string then how can you delete the 2n th character ?

Please help me to understand the following sentence of yours. How did you come up with this lexicographic order?

“So for string S=′′(())()((()))(())”, the lexicographic order will be L1<L3<L5<L7<L6<L4<L2<L0. To produce lexicographically 3rd string we need to produce L5 by deleting any of the bold characters : “(())()((()))(())”."

Seems like there is some problem with input. My submission using BufferedReader gave NZEC while one using Scanner passed.

4 Likes

@code_master01 & @code_note & @amitpandeykgp.: The editorial is great. Thanks for that. But let me ask you one small thing…as you have said there are 2 key ideas -1. one of chunk 2.other of
L2i+1<L2j+1,L2i>L2jfor(i<j) L2i+1<L2jfor all(i,j). How did you arrive at this? Can you please tell me the intuitive idea? What ideas did you have before setting this beautiful question/writing the editorial…hope that will be helpful to beginners like me.

@ar56
Given sequence is S="(())()((()))(())", You know that ‘(’ < ‘)’ . So let ‘(’ = 1 ans ‘)’ = 2.

Now S = 11 22 1 2 111 222 11 22

L0 = By deleting any character from 0th pair i.e 11 .

L1 = By deleting any character from 1st pair i.e 22 . and so on.

Therefore L1 will be : 11 2 1 2 111 222 11 22

L3 = 11 22 1 111 222 11 22

L5 = 11 22 1 2 111 22 11 22

L7 = 11 22 1 2 111 222 11 2 and so on .

As it become clear that L1<L3<L5<L7 . . .

lexicographically largest will be L0 = 1 22 1 2 111 222 11 22 .

Yet I want to know @amitpandeykgp how did you come with the scenario . Amazing question .

2 Likes

What causes NZEC in python I submitted a code in python , i tested in Codechef IDE which gave appropriate output when i submitted the same for the problem it gave me an NZEC

When i just wrote the same algo code in C++ 4.92 it gave me AC

Here is the link

Python : CodeChef: Practical coding for everyone

C++ : CodeChef: Practical coding for everyone

Can someone help me understand why this solution 4PRXeG - Online C++0x Compiler & Debugging Tool - Ideone.com gave me WA. It works perfectly for the example given above and for any other test cases i could think off using the same logic as described above.

Can anybody please help me with my code that why it’s giving TLE .
Here’s a brief about what i have done.

CHECK 1 : if the input string is odd sized then if k>1 print -1 , else print string.

CHECK 2 : if the input string is irregular then if k>1 print -1 else print string.

CHECK 3 : i have converted the whole string from ‘(’ and ‘)’ to characters ‘a’ and ‘b’.
Then using the string concatenation operation and with the help of two temporary strings
generated all n-1 strings and hashed them into an map.
then finally checked if k>map.size() print -1
else find kth position in map and print that string after converting it back.

since i have used map . complexity would hardly go nlogn . and for 10^5 and at most 10 test cases . it would go 2 * (10^7) which goes strictly in 1 second. so why tle .?

here’s my


[1] . 
    


  [1]: http://ideone.com/l4J6rF

Can anyone tell me for which test case this solution CodeChef: Practical coding for everyone is not working .?

can anyone pls tell why this solution is wrong…pls
http://www.codechef.com/viewsolution/7264909

Could you tell me your approach(in short)?

First, I am checking if string is regular or not.
If it is regular, Kth subsequence can be obtained by removing ‘)’ from Kth group of ‘)’ (I mean continuous sequence of ‘)’) from left to right.
If there are not enough groups of ‘)’ (i.e K is greater) then Kth subsequence can be obtained by removing ‘(’ from (K - no.of ‘)’ groups)th group of ‘(’ from right to left.

Length of the given string is greater than or equal to 1. It is given in the constraints.

Sorry for confusion. Length of the string is N not n. L_2n is the subsequence which gets generated by deleting a character from (2n)th chunk.

You have problem in the statement or in the proof?

nice editorial! :slight_smile:

The links to the solutions do not work [ Access Denied ]. :frowning:

1 Like