ESCAPE1 - Evaluate Escape Character

no tags 

Strings represented in computers often include special characters which are not printed, instead they have some other function, such as the newline character '\n'.

For ease of manipulation, these characters are usually represented by a regular character, preceded by a so called 'escape' - in the above example, the character '\'.

Buj recently bought a string S of length n on the local market, for (according to him completely legal and within the law) home manipulation.

He forgot to read the online store ratings and customer reviews.

Upong arriving at home and taking the string out of the unbelievably eco-unfriendly packaging, he realized with horror that the characters of the string do not follow any known encoding. The only thing he managed to do was number the characters from 0 to n-1 in perceived lexicographical order.

Oh well, thought Buj, I'll still manipulate this string to my heart's content... but what if I got scammed, and sold a low-quality string? One which, if it was printed out, would be lexicographically large?

But what would be printed out depends on which character in the string is the escape.

Buj sent us the string by post for analysis, and we uploaded it to this website hoping someone would do the work for us.


The first line contains an integer 1 ≤ T ≤ 10 - the number of test cases. T cases follow.

For each case, the first line contains the number n - the length of the string - and the second line contains a space-separated permutation of the numbers 0, ... , n-1 - the characters of the string.

The sum of n within an input file will not exceed 106.


In this problem, escape characters work as follows: if it is the last character in the string, it has no effect and is simply printed out as usual. Otherwise, that character and the character immediately following it is not printed (and instead together they have some other, printing-unrelated function). Take a look at the sample for clarification.

Let si be the string which would be printed if we choose character number i as the escape character.

Let pi be the 0-based position of si if we sort all such strings lexicographically.

Output in a single line the numbers p0, p1, ..., pn-1.

In other words, output in order the answer to the questions

"How many strings out of s0, ..., sn-1 are lexicographically smaller than s0?"

"How many are smaller than s1?"


"How many are smaller than sn-1?"


0 1 2
0 2 1
Output: 2 0 1
2 1 0

In the first case:

If character 0 was the escape, the printed string would be 2.

If 1 was the escape, the printed string would be 0.

If 2 was the escape, the printed string would be 0 1 2.

Ordering these strings, we get [0, 0 1 2, 2].

So s0 is at index 2, s1 at index 0, and s2 at index 1, so the output is 2 0 1.

Note that the i-th number in the output is for the string where character number i is the escape, not the i-th character in the input.

hide comments
boemogensen: 2019-01-17 10:24:41

@Hodobox can you please check my submission 23075839, i dont know why this solution gives WA? Thank you.

1 6 11 5 12 9 7 0 10 3 8 4 2
your output starts with '9 0...' indicating that the printed string is lex. larger when character 0 is chosen compared to character 1.
But when 0 is escape, the printed string starts
1 6 11 5 ....
when 1 is escape, the string starts
11 5 12 9 ....
the first position where they differ is, well, right at the start, and 11 > 1 so S_1 > S_0.

The correct output would be
8 12 6 7 5 10 0 9 4 2 3 11 1

Wait , is that the correct output?
Because when 12 is escape, the string is
1 6 11 5 ...
But when 6 is escape, the string is
1 5 12 9 ...
which is s[12]>s[6].Can you explain about this clearly?
By the way, i know my mistake now. Thank you

You are right, S_12 > S_6. That is why the 12th number in the ouput > 6th number in the output (0-indexed)

Oh I see, my mistake is about index on output. Love this problem.the most humble problemsetter i've ever met. Thank you very much

Last edit: 2019-01-18 03:07:51
boemogensen: 2019-01-17 07:55:15

Last edit: 2019-01-18 04:18:17
Vipul Srivastava: 2019-01-17 07:28:03

Last edit: 2019-01-17 07:31:27
Vipul Srivastava: 2019-01-16 08:55:15

@Hodobox can you please give me a hint if I am failing most of the test cases or only some?

RE: you have WA almost everywhere, because for some reason you are treating the input as some sort of strings? But the numbers just represent the lexicographical order of each character.

Last edit: 2019-01-17 08:41:33
julkas: 2019-01-12 11:51:56

Good ESCAPE plan.

vaibhav2303: 2019-01-11 08:45:06

@Hobodox can you please check my submissions, all of them are essentially the same and yet one gives WA and the other gives AC, I believe there might be something weird going on with the test cases.

RE: you have an out-of-bounds indexing problem for a corner case, small enough for the code not to crash, which (not sure if by luck or otherwise) sometimes ends up printing the right number.

RE: I see my mistake now, thanks for helping and a great question!

Last edit: 2019-01-11 11:54:46

Added by:Hodobox
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem