Nice!

As a participant, I will downvote.

i wish i could be expert!

Hope to be pupil again

Guy's name tho

Whenever someone starts a line with, "i am not simp", there is a high chance that they are not simp. Seems legit.

I know...

no but her insta is @zachscud

No it is not. Like C took me 7 minutes at most, D took 15-20.

you can just ask 25 pairs (a, b) and (b, a), and you are able to print the answer once you've got different paths for an arbitrary pair. The probability of getting same path for each pair is 2^(-25).

u can just try every pair {1, i} and {i, 1} for i from 2 to 27. In each two query ({1, i} and {i, 1}) u have a 50% chance that u get distance in different directions. If u do, then the answer is ans1 + ans2, where ans1 and ans2 is results for queries. Also, if u get -1 at some point, it means, that the previous i was the greatest vertex in graph, so it should be the answer. So print i — 1 and return

I think no. Try basic ternary give me WA TC 1x

I thought so for a while but no, it's much simpler.

Roughly 1-2^-25 when n is big enough.

No, the idea, especially with No hacks, 50 test cases, really says it uses random. Also, as there is no binary search, you can only rely on distances, but they could all be simply distances on a part of a graph, so you cannot guarantee the answer is correct. The only way is to minimise the chance of fail

We rarely have "easy" problems with randomized solutions. This is a good way to introduce randomized solutions to beginners

I guess you've never heard of mr Green Grape

log(1e18) > 50

The chance of failure is 2^(-25), which is very small

i guess it is (i did the same btw), because hacks are disabled and there are 50 tests only. Moreover, the problemsetters did even tell us that amount of tests is 50, which is kinda strange.

Find all the characters in string that lie between letters s[0] and s[n — 1] and use all of them for jumps.

I try every pair {1, i} and {i, 1} for i from 2 to 27 ^^

IT'S IS THE INTENDED SOLUTION

It's probability theory. We have a chance of success 1/2, same for failure. As we ask 25 times, we have a chance of failure equal to 2^(-25), which is a VERY small number

Since we have at most 50 queries, we can check 25 pairs in both ways. Assume we got a pair (a, b). Checking it both ways means that you chack a pair (a, b) and (b, a) since it can give different results. Since the output path length is randomized between the 2 paths(the short and the long versions, since it's a cycle), it's 50% chance for each to output.

Asking 25 queries in this format and checking for -1 or different results for the (a, b) & (b, a) query. If you get -1, it means the last vertice(call it v; 2<=v<=26) is the correct answer, since the current one is out of bounds and the last one wasn't. So we output the last valid run. If the results differ, you can output sum of the results, since you got both paths for (1, v) pair and their sum is a complete cycle.

This one failing has quite a low chance, since it's 1/2 for each path to be given for a query, it's 2^-25% chance of this idea failing, if I am not mistaken.

I hope this makes sense.

You're allowed 50 queries. You make a pair of queries "? a b" and "? b a", and hope that you get different results for these two. If the results are different, then you can add the two results to get the number of vertices.

I'm not sure if the guess counts as a query, but if it doesn't, then you have 25 pairs of queries to get this. If it does count, then you only get 24 pairs of queries, plus an extra query, and one for the answer.

It's annoying that this is a randomized solution, but the probability of this failing is less than 1%, and there are many hints in the problem statement itself to suggest that this is the intended approach (equal probability in bold letters, mentioning that "? a b" and "? b a" are rolled independently, specifying the number of jury tests, etc).

Also if you ask why the numbers of allowed querry is not greater it's because with 60 querry (which is log2(1e18)) you can just get the result with a binary search

As the solution uses sorting I might suggest it's that the last index is not the last in your sequence. Or you could possibly go in the wrong order if p >= q or less than q. IDK, but that's most likely the mistake

Try "baba".

I fell into the same trap and got WA. Thankfully, I figured it out before the contest was over.

I didn't read your code (but I checked "baba" via custom invocation), but it's most likely due to your use of sorting. The assumption that your range covers all instances of first character and all instances of last character only applies if first character < last character. In the scenario where last character < first character, your range likely does not capture all instances of first and/or last character.

Here is the counter case for your solution: 1 yydia

correct ans: 24 5 1 2 4 3 5

Your ans: 24 4 1 4 3 5

Now it's Accepted!

Accepted

Thanks Noobish_Monk Andalus Nikhil19259

one counter test case: 1 puvh correct ans: 8 2 1 4 your output: 8 3 1 2 4

Check 1 zzzzza

Yeh same doubt regarding the E part of the contest, in all the test cases, input is in this form-

3 9195979e279504391c49d2f080c1d8c755d044ca what is this — 9195979e279504391c49d2f080c1d8c755d044ca ?

Shouldn't this be a long integer? Thanks.

I think you store the length of the permutation as well as it's index in sorted order. Not sure though...

Try "baba".

I fell into the same trap and got WA. Thankfully, I figured it out before the contest was over.

I didn't read your code (but I checked "baba" via custom invocation), but it's most likely due to your use of sorting. The assumption that your range covers all instances of first character and all instances of last character only applies if first character < last character. In the scenario where last character < first character, your range likely does not capture all instances of first and/or last character.

My solutions problem c solution problem D solution

For C or D?

For C, jumping directly to the end yields the minimum cost, which is |last character — first character|. How to maximize jumps? Observe that if you're in $$$\alpha$$$ and you jump to $$$\beta$$$ and then to $$$\gamma$$$ such that $$$\alpha <= \beta <= \gamma$$$, then the cost is the same as jumping directly from $$$\alpha$$$ to $$$\gamma$$$. So you can jump to any character in the range [current character, final character] and it would not affect the final cost.

For example, with "logic", you can go from "l" to "i" to "g" to "c" because "l" > "i" > "g" > "c". To maximize jumps, you need to visit every character in the range [starting character, final character] in order (either non-increasing or non-decreasing order, depending on the relative order between first and last character).

For D, if you calculate $$$y - x$$$, you basically get the person's balance from paying for their meal. This can be negative if they don't have enough money. You can then sort the balances, and try to pair the one with the lowest (i.e., most negative) balance with the highest balance. If the result is non-negative, it's a valid pair, and you can move on. If not, then the lowest balance is hopeless and you move to the next lowest balance (try with highest balance), and so on.

int isn't big enough to hold the values required.

I did feel bothered by the fact that the intended solution is randomized, especially since I was trying much more complicated approaches before the contest ended, and only got AC after it was over.

However, I think it's really a matter of opinion on whether this is appropriate. Randomized algorithms have numerous practical applications in the real world, so this kind of recognition that a randomized algorithm would work is a good skill to have, which can be argued as being among the type of skills that competitive programming should cover. Also, the problem did drop a lot of hints that this was the intended solution ("equal probability" in bold, mentioning that "? a b" and "? b a" are processed independently, mentioning the number of jury tests, etc), so I think it's justified in this case.

I personally think it was a great problem (maybe I have some bias since I solved it quite quickly in the contest). It makes you think outside of the box and consider non standard methods that you don't regularly see in CP, which ultimately is a great way to test/improve problem solving.

It depends on your rank in the contest and your current rating.

The probability of success is over 99%, and the problem dropped a lot of hints to go for a randomized approach ("equal probability" in bold letters, clarifying that "? a b" and "? b a" are processed independently, mentioning the number of jury tests), so I think this was justified. I understand how one would assume there is a deterministic solution, but randomized algorithms have numerous practical applications in the real world, and recognizing when a randomized algorithm would be effective is a valuable skill for a programmer to have, so it can be argued that it should fall within the scope of competitive programming. I understand the concerns, but I think it's a matter of subjective opinion and cannot definitely be ruled as "unfair".

No. An adversary can always ensure that the result for each query is either -1 or some distance that is less than the current lower bound that was established. Therefore, there are essentially two possible types of information to be gleaned from a single query. With 50 queries, this only allows identifying up to $$$2^{50}$$$ different values, which is less than $$$10^{18}$$$. So there is no 100% correct deterministic solution.

there is no need in sqrt decomposition, the only data structure we actually need is prefix sum array