Hello everyone,

At March 11 there was an annual programming contest in Samara University, and yet again we copy it into Codeforces Gyms. The gym contest takes place on Sunday, March 18, at 11:00 MSK.

Third time in a row it is a personal contest. So we ask everyone to participate solo. The contest is the most interesting for blue and violet coders.

And as usual,

**The list of our previous contests**

Can I register with my team? Or only individual contestants?

You can, but people on the onsite contest played individually.

Will there be an editorial after the contest. It becomes really hard to get solutions for all the problems from the comments for beginners like me.

I enjoyed the contest, the problems were really interesting. Can I see the case I'm failing at on problem M?

This test has n = 3.

I'm like brute forcing, so maybe it's some logical bug.

Can you share the full test? :)

Can someone share his code for C.

Code

I'm not sure how clear it is but I can explain anything if it's unclear.

Could you please explain how your code works. This is my Code. The Idea is same as yours I guess but its giving wrong answer on Test 11.

I start by sorting the ranges by their end points. Then as I'm processing the end points, ill greedily build my set.

Basically, if by the time I get to the end of some range and there's no number in my set (that's the ceiling() call) that belongs in it's range, then I'll add that range's endpoint to the set.

This is always optimal because I'm going in increasing order of endpoints so every time I add a number to my set, it's as large as possible so it's most likely to fit in the other ranges (who all have end points greater than the current one).

Why I sort the ranges by their start points then I got wrong answer ? But sort the ranges by their end points will get AC ?

Any hint for problem H or L???

Problem H:

BFS off of every monster tile and only go a maximum of d distance away. Any tile that was touched by a monster's BFS is now no longer usable. Now BFS from your starting point and do regular shortest path in a grid but making sure to ignore cells touched by the monsters.

Problem L:

For every position

iin the string, find the next position of every letter in the alphabet. Now keep some kind of queue and find the next position of whatever letter is queried (or pop the back of your queue). If the next position of the queried letter doesn't exist, the answer is no otherwise it's yes.So simple BFS's were enough in H? I thought that with n*m up to 4*10^10 that would take too long, even just to calculate 'bad' cells

n*m≤ 2 * 10^{5}Oh.. I guess I can't read :(

Thanks, now it's a lot more clear

`What's output of problem E for this test case:`

`abaca`

`aabac`

The output is "NO"

What is the test 48 on F?

During the contest this test helps me:

Answer is NO

Any hints on how to approach I? My approach can't seem to get past test 12.

I used this approach:

Define a procedure

`findRoot(vertices, leafs, depth)`

for search a tree root among vertices, inside it we need to find two leafs from a different subtrees (relative to root). It can be managed in`O(size(vertices))`

, then you can easily find a root (it is a vertex, that`dist(leaf1, v) = dist(leaf2, v) = depth`

). Then you need to run findRoot recursively from left/right subtree.So, each findRoot procedure takes

`2 * size(vertices)`

queries (`2 * nlogn`

in total) and additional queries at start to find leafs.That makes a lot of sense. Thank you!

What's test 22 on H ?

Test 22 generatorThe game .C.O.N.T.E.S.T: Unexpected Behaviour from Problem K "Video Reviews" does not exist. But recently our gamedev team Veslo Games released the game .T.E.S.T: Expected Behaviour (from creator of Codeforces Simulator!) to the Steam Early Access. If you like puzzles, consider checking this out!