> last Educational Round of 2021
he doesn't know

No please don't say that

liar

alga kazakhstan

17:35(Moscow)

.

Why you just keep on posting same thing again and again in every contest's announcement.My advice to you is not to focus on others whether they are cheating or not rather you should practice more and more to surpass those cheaters. And for cheaters they can become expert or CM by cheating but ratings without having knowledge is of no use they can't use it anywhere be it in Online tests,interviews.

So just focus on developing skill and you can see positive outcomes after sometime :D.

A was harder than C, change my mind lmao

If I am not wrong for the third test case of C 6 3 20 **a*** output -- babbbbbbbbb The strings are --

- a
- ab
- abb
- abbb
- abbbb
- abbbbb
- abbbbbb
- abbbbbbb
- abbbbbbbb
- abbbbbbbbb
- ba
- bab
- babb
- babbb
- babbbb
- babbbbb
- babbbbbb
- babbbbbbb
- babbbbbbbb
- babbbbbbbbb

btw was not able to solve it.. RIP

The number of possibilities is not 16. In the first group of asterisks, we can have at most 6 'b'. In the second group of asterisks, we can have at most 9 'b'. So, the total number of possibilities is (6 + 1) * (9 + 1) = 70.

You can fix the first group of asterisks with some number of 'b'. Then, you can have 10 different strings as you can adjust the number of 'b' in the second group of asterisks.

linked list

its actually just basic implementation [too easy for position E, I think].

For each query of type-1, find the nearest to the right query of type 2 which has the same $$$x$$$ and add an edge between these two indices. For each query of type 2, find the nearest to the right query of type 2 which has $$$x$$$ as the $$$y$$$ of current query and add an edge.

this structure forms a forest.

Then the value of each type 1 query in the final array is just the value of the root of the tree this index is a part of.

Try to build array by performing actions given in input in reverse order and store some useful information.

You can store for each x, all indices that have value equal to x in a vector, let's call it v[x].

For the queries: set all elements equal to x to y, you can move all the elements from v[x] to v[y], use small to large to do this.

I think simplest solution is to iterate the queryies from last to first. We maintain a transision table, no tree or something complecated needed.

see 139792544

My solution uses array of linked lists.

For query of the form 1 x, we add index of x (which is equal to current number of appended elements so far) to the end of the linked list located at array[x].
For query of the form 2 x y we move all elements of the linked list located at array[x] to array[y].

At any given point, array[val] stores all the original indices which ended up holding the value of val. https://mirror.codeforces.com/contest/1620/submission/139814623

If you execute the operations from the last going backwards you can keep&update a mapping for each number quite easily. At the start, mapping[x] = x for every x. Then:

• type 1, append mapping[x] to the result
• type 2, update mapping[x] = mapping[y]

then print reversed(result)

Yes, I solved it in this way.

No

Actually, you can , if you hack someone else's solution whose ranking above yours.

I just needed one more minute to submit my solution.. ://///

It's because Base*Height may exceed int range.

The attempt was so blatant lol, Dude commented the block of code and then wrote the same code and thought that he wouldn't be caught by the CF plag system.

The first thing any plag tool does is to wipe off all the comments, spaces and indents and read the code as one single line.

How dumb can one be.

No.

please don't die

metoo.. still don't know why the 4th test case doesn't work out -.-

I learned that lesson ones or twice (or more?) and now I try to avoid the guess game — today (again) I had to write a tests with brute force function that generates all possible strings for a small templates, that can be easily understood. Sorted them and compared to my solution for every X. 15 extra minutes was enough to find I had >= instead of > in some place. Some times I search for this 30 — 45 — 60, but it is definitely giving me more than wild guessing.

I tried using DSU (along with a hashmap and a pointer array), but am getting WA on Test 4 itself.
What could be wrong with my code?
My Submission.
Thanks.

no, there is no way to pass test case 5

Unfortunately, it was hard to cut all of them off. The model solution works in $$$O(2^n \cdot (n + A))$$$, but its constant factor is kinda big so I couldn't set $$$n = 24$$$. In retrospect, perhaps it would be better to swap F and G and set something like $$$n = 20$$$ instead of $$$23$$$.

How do you do it with that complexity? Is it even easier than $$$O((n + 26) 2^n)$$$? I can't imagine a solution where it is not immediately clear how to optimize.

Please don't ask me :((

Let $$$cnt$$$ is the number of $$$N$$$ between $$$s_i$$$ and $$$s_{n-1}$$$.

• $$$cnt = 0$$$ means $$$a_1 = a_n$$$ or $$$s_n = E$$$.
• $$$cnt = 1$$$ means $$$a_1 \neq a_n$$$ or $$$s_n = N$$$.
• Otherwise, there always exists a solution.

Same dude, 1 minor mistake let maxx be the biggest element in array i didnt check if there were any maxx-1 — s elements in the array if maxx%1=3

The second one will contribute, the first one is kind of nullified by your second submission.

Because your complexity is not good?

Actually this is more or less the defintion of educational rounds. If you do not like this you should not participate in them.

4th test case: 2 * 3 + 3 * 257=777

Same :( I spend like an hour trying to find what to issue was, only to realize after the contest that it was overflow :(

I solved using DSU. But somehow my solution got Memory Limit error. And i don't know why. Here is my solution. https://mirror.codeforces.com/contest/1620/submission/139812356

Tried it in Python first too, got 2 TLEs, wrote the same code in C++, got AC.

There is a lot — check out submission stats for a problem — and you can just switch to pypy3 sometimes it helps. is yours code AC in pypy3.

PS. And to add: you are creating a lot of objects (lists) to encode input. Try to simplify it and get rid of them.

P.P.S. Or maybe not and I am wrong (about creating a lot of objects) — cause your solution is faster than my when I run it on PyPy :)

PPPS. Oh, no, I was right, but you have reall-really-really good "fast-input". My solution become twice faster with it — thank you very much!

I think you have overflow issue.

A given string may have b, but your program did not consider it.

You are overflowing LLONG_MAX (9e18) on the line temp *= (v[i]*k)+1;. This is undefined behaviour and you are TLEing because of this. Be sure to make sure that temp is not overflowed.

haha~

That is correct, in the optimal answer you get at most one 1-token and at most two 2-tokens.
That is because you can always break two 1-tokens into one 2-token and break three 2-tokens into two 3-tokens thus getting a better answer always:
1) (1+1) -> (2)
2) (2+2+2) -> (3+3)

1
6 1 1
a*a*a*

Your answer gives abaa. Correct answer should be aaa.

yupp.

Oh great i didn't knew that it is some technique. Well i discovered already discovered technique.

That problem not being skipped has worked to his disadvantage.

If all the solutions would have been skipped then he would have no valid submission and the round would become unrated for him. However the solution for problem A not skipping means that the round is rated for him and due to only 1 correct submission , there's a huge negative delta.

Why I didn’t get penalty is because I solved the problem earlier than you.

You are right about time complexity of your solution. What you are missing is that using input() for 500_000 of entries is too long. Look into other solutions to see "fast input" for python. Here is your solution with 1 variant of fast input: 139998877

PS. And this fast-input: 139999694 I have just found in sur's solution is even better — it just made my solution twice faster. Thought, you should be careful with what you get — there will be unprintable symbols in your input.