Hello everybody!

Today, on March 1st, 2020 the final round of Technocup olympiad for Russian-speaking high school students is held. The round starts at 13:00 Moscow time.

For those who want to compete on the same problems, we will host two Codeforces rounds: one for the first, and one for the second division. The rounds will start at 13:05 UTC, don't miss them! The round will start just after the onsite contest ends, so it can be postponed slightly if the onsite event timetable changes.

If you compete in the Final Round today, you can't compete in the Codeforces round #625.

The problems are prepared by MikeMirzayanov, Endagorion, tourist, Roms, vovuh, voidmax, adamant and me. Many thanks to KAN, AndreySergunin, antontrygubO_o, kuviman, MrPaul_TUser, Stepavly, artsin666, Pavs, AdvancerMan, Stresshoover, Peinot, geranazavr555, defolaut, sladkayaKlubnichka, cannor147, PrianishnikovaRina and Pavlova for testing the problems!

P.S. Because of the onsite contest, some Codeforces features may be disabled today.

Good luck!

Congratulations to the winners of the round:

**Div1**

1) ksun48

2) maroonrk

3) jijiang

4) Radewoosh

5) Um_nik

**Div2**

1) DraqonLore

4) endbringer

5) cml

Good luck with editorial this time)

Bad luck...

Good luck everyone!

How many problems will be?

Who was the last year's winner ?

Ildar 300iq Gainullin

Make the editorial with you.

I believe the timing clashes with ABC 157.

How many problems there will be? And what's the score for each problem?

why The round will start just after the onsite contest ends?

So can we still hack in this round?

is this a rated contest?

Probably not.

All the rounds containing the name "Codeforces Round #XXX" are rated.

you mean that the round on Mar.03 is not?

Negation of RubenAshughyan's statement : -->Some of the rounds containing the name "Codeforces Round #XXX" are not rated.

or

-->Some of the rounds not containing the name "Codeforces Round #XXX" are rated.

There might be unethical and ugly behavior! Be prepared to downvote it!

will there be an interactive problem?

At Technocup Final Round 2018 and 2019, there was no interactive problem. So probably ...

Hope there will be no online analysis of problems during the contest.

I have not competed for a long time, so good luck for me ^_^

This contest is "Hello March 2020".

May I ask which features will be disabled?

Maybe user profiles)

as well as others submission

Score distribution?

what's the score distribution?

Maybe that is what the blog said to be disabled today :D

it is said that problem setters and testers are very busy checking whether their problems are readable, their tests are strong enough etc, and also the score distribution (but I don't believe that :D )

if programming was an anime XD

but it isn't infact.

This was so cool and then he said "question"...

What's the problem with that word?

Will the difficulty of this two contests equals to usual Div.1 & Div.2 respectively?

Who knows?

Two legends MikeMirzayanov and tourist have prepared this contest. It will definitely be a great contest. Thank you codeforces :)

as usual, these contests with suffix "based on ..." are always good.

Can I get ratting?

CF-visualiser doesn't work.

Yes.Me too

Why did administrator block my me ? Now I can't submit in the Round #625 QAQ

P.S. Because of the onsite contest, some Codeforces features may be disabled today. (The last line of the blog post)

Thanks

How to solve Div.1 C (Div.2 E) within TL?

try fast io

ios_base:: ...

worked for me.

You can sort them and compute the contribution of each one.Use binary search and segment_tree.

Let's for each armor keep the balance you can achieve (initially it is -cb_i). Sort the weapons according to their attack modifiers, and process them one by one. Each time you process a weapon, add all monsters (also pre-sorted) with defense levels lower than current attack modifier. For each added monster with attack y_i, for all armors with defense modifiers > y_i add the reward for this monster (you can do this in a binary tree). Then just keep track of price of current weapon + maximum of balances for all armors, and remember the best sum.

Just a little curious, why downvotes for all replies? Are they wrong or wtf happened here?

Using lazy segment tree(range-add and range-max), which has 10^6 element

This is one of the most boring contests I've participated in.

I wholeheartedly agree. Nothing interesting at all in ABCE (div1) and F almost made me rage quit. D had some potential but it was lost in a sea of boredom.

What is wrong with F? (Except a quite long statement)

A culmination of uninterestingness? Its statement aside, the task itself feels very repulsive to me. Maybe it would be even okay if it went together with some other problemset, but this felt like a "cherry" on the "cake".

How to solve Div-2 B problem? :)

Each place can only be in a tour with other places that have the same value of j — b[j]. Just count the frequencies for each value of j — b[j] and output the highest one.

This solution is beautiful. What thought process is leading to it? I mean how to come to "minus index" idea in the first place?

This implies that the $b_i-c_i$ values of all cities in a journey are equal.

If you want to take (x1, y1), (x2, y2) then they belong to the same line with slope (y2 — y1) / (x2 — x1) since (y2 — y1) = (x2 — x1) then slope = 1 using line equation m * x + b = y since m = 1 then x1 + b = y1, x2 + b = y2. You can imagine x is the index in the array and y is the beauty.

I dont know how to say but here it is

HintYou shift the

`value`

to`value - position`

then you add the

`value`

to`map[value - position]`

than the final answer will be max of the

`map`

pseudo solutionfor each element in the array we see what is its difference between its index and its value. because if some differences are equal then it means these elements can be used together as a possible answer. just like if the array was: 1 2 3 4 5 since each element's difference between its index and value is 0 they can all be used together to create an answer. map each possible difference and the map's answer would be the sum of all of these values. then print the maximum answer by iterating over the map.

create a array "ans" of size n and intialise it to 0. and also define a map<int,int>mp iterate form 0 to n if the value of a[i]-i not exist in map then ans[i] updated to a[i] and if it exist then update the value of ans[i]=a[i]+ans[mp[a[i]-i]. and also update mp[i]=a[i]-i every time Now print the maximum value of ans.

Thanks for the contest <3

AskHow to solve

`C`

the string problemAskHow to solve

`D`

the graph problem ?Ctry to delete all 'z' that satisfy the condition then all 'y' then all 'x' and so on to 'b' .. when you try to delete some char x from string you can iterate over all subsegment that equal to x let us say from L to R (indexes) then if (s[L-1]==x-1 or s[R+1]==x-1) you can delete all segment [L,R]

Oh, thanks <3

Is that

`O(n * k)`

solution where k = 26 ?yes it is

WishIf I werent late for the contest...

sorry my solution is wrong (i got wrong answer) :(

i don't know the correct solution

Your idea is correct, probably just an implementation issue

CYour idea is good, I did the same. As |s| is small, it is easy to solve with text-processing language (here is Perl solution — 72183066, used look-ahead and look-behind inside regex).

I solved C this way: while there is symbol that can be deleted, I check for all symbols how much symbols going in the alphabet after this symbol is in string(let it be help), and then delete symbol with smallest help.

Dyou can solve it by bfs from t to other vertices (you reverse the edges then start bfs from t) then

I did the same but still got WA on pretest 4. Curious to know what went wrong once the test is released! 72197623

i can't see the submission :(

You are not checking edge between path[i — 1] and path[i] before updating max_routing number value in the else part.

No, that is not the reason. I am failing in the 4th test case which has answer is "3 3" where as I output "5 5". The else part just increases the max_builds, it should not effect the min_builds

Another Error which is causing wrong min_routing(and max_routing as well) is that you are comparing dist[path[i]] with K — 1 — i but instead it should be compared with (dist[path[i-1]] — 1). If both are not equal, only then we should increase min_routing.

why does even second question of div2 have such hard time contrainst and test cases( tc 8)??

i skipped all repeated elements still it contains test cases where worst case give n^2, case where all elements are different and not included in any series.

## include<bits/stdc++.h>

using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int ans[n]={0},maxa=0; for(int i=0;i<n;i++) { maxa=max(maxa,a[i]); ans[i]=max(a[i],ans[i]); for(int j=i+1;j<n;j++) { if(a[j]-a[i]==j-i) { ans[j]=max(ans[j],ans[i]+a[j]); } } } for(int i=0;i<n;i++) maxa=max(maxa,ans[i]); cout<<maxa; } I think this solution is good.

You should use

The Spoilerto show your code

In fact I kinda like the first line. So bold and confident with what you should include.

So why dont you bold your sentence :DYou can do it in O(n)

Can anybody suggest me what the test is like in test 4 of problem D div 2. :<

Me too, WA on test4 countless times :(

I kept getting hit by at TLE on test 7 :(

Think is something like

test5 5

1 2

2 3

3 4

4 5

3 5

5

1 2 3 4 5

Because when i solved that, it was WA on test 5

Then i looked at

test6 7

1 2

2 3

3 4

4 5

3 5

1 6

6 4

5

1 2 3 4 5

And when i solved that, it was AC.

Are the answers on your tests are

`1 1`

and`1 2`

?My solution outputs this answers and still fails in

`Test 5`

. 72205820Don't know, if it was intended, that

`Test 4`

and`Test 5`

contents are hidden.We can't see others' submission in this contest. Please try another way to show your code.

https://pastebin.com/hddadG3K

A very stupid mistake was found, finally AC.

Thanks for your data, even though I also made another stupid mistake :(

Pls help how to solve D div 2 (B div 1)

Is it only me that E was straightforward and D was undoable?

I just read E after the competition after being stuck at D, and immediately regretted not doing so earlier. I reckon the main reason D is solved more is just the (questionable) order.

For me it's the opposite

shrugHow to solve Div 1 C?

You can read the comment above.

it seems that creating events for the second stuffs and the third sorting by their first entry and using segment tree to maintain the answer is enough for this task. (Though it may involves some details I guess)

About problem D1C. I came with this approach. First use only useful weapon and defense. (Higher attack cost more money). Then sort all monsters on their defense and lets add them one by one. When we are adding monster we should increase our attack to kill him, and find minimal needed defense to kill him(using upper bound). Then for all defenses higher then found we will get reward for him also. Lets maintain segtree on the array $$$a$$$, where $$$a_i$$$ = amount of money you get using i-s defense item. Firstly $$$a_i = -d_i[cost]$$$ Then when adding a monster k we add $$$z_k$$$ on the segment $$$[pos, m - 1]$$$ (pos is minimum defense needed). And update ans. So the question is, has someone submitted solution using same approach? Or whats wrong with this approach? Code: https://pastebin.com/jZyVajPi

My approach is the same, and my solution passed all pretests.

How to solve problem D div2?

pls give me sone hint....

Dijkstra(O(mlogm)) Count the number of minimum paths as well.

I think " bfs " is enough .

thanks you.

If I had been calmer than I would have done it. So sad

When standing in an intersection a, if the direction ploycarp is going, is not on the shortest path within the neighbours of a to the work, then we have to rebuild no matter what. If the shortest path from the way polycarp is going is the shortest path within all paths from neighbours of a to work, then if there are no other paths as short, we dont need to rebuild, and if there are other paths as short, then the maximum number of rebuilds should go up by one, but the minimum should stay the same

thanks you.

It's quite weird that my solution can't pass sample test(Runtime error), since it passes sample test on my laptop, and I didn't do anything may lead to RE. (Since I have a WA 3 submission)

And when I just changed my modulo, and it passed sample test, but get RE on test 2.

72201472 72202006

Can anyone explain why?

Here are my many other submissions:

Link

ppow has maxn size, which is 2e5+7. And on line 99 you run loop on 4e5 elements, so it is out of bounds access to array. You can easy catch such errors if you compile your code with -fsanitize=address

Thank you!

It seems that I have never gotten rid of those stupid mistakes :(

Thanks mr. Endagorion for letting this problem from your past contest into this contest.

What's the same?

div1E, it's not 100% the same but after building the virtual tree it's trivial.

It's not the same problem, it's the same technique. I'd argue it's not interesting and doesn't deserve to be an E, but it's definitely not the same problem.

Agree with Encho, it's just the same technique.

Fair enough, I don't remember what the problem is about. For me this problem all about the technique and the rest is not important/easy.

It is trivially similiar.

Ugh, I would definitely not call it the same problem. Compressing the induced tree is very common trick and that is basically whole intersection of solutions.

I don't see how this is the same problem as E.

why the system tests didn't start ?

How to solve div1 D?

You can remove "11" substring. Then reduced strings should be the same.

To find a reduced string of a substring I used rolling hash along with the segment tree.

Why this is enough?

You can imagine that '0' stands for a coin and '1' stands for an empty position. So for each move, a coin is moved across two empty positions backward or forward. In this move, for every two adjacent coins, the parity of distance between them will not change. So you can keep moving the coins to the left, and finally you will find the sequence that no two adjacent coins have a distance greater than one. That's the same as the result of removing all '11' substring.

Why can't I submit a task during system testing?

How to solve div2 E (div1 C)?

Sort armor by incresing

`b`

. Create segement tree and update it with`-cb`

for every armor piece.Then do a sweep on monsters(by their

`x`

) and weapons(by their`a`

):if current event is weapon, update solution to

`sol = max(sol, -ca + (max element in segment tree))`

else find first armor set with

`b > y`

(denote it as pos) and update interval`[pos, m - 1]`

in segement tree with`+z`

You can implement additions in segement tree with lazy propagation, and finding first armor set with binary search or lower_bound

I can't seem to understand why am I getting

REin [problem:https://codeforces.com/contest/1321/problem/A] onpretest 5.SpoilerCode 72185248

int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);

}

We cant read your code now.

Use this `Spoiler``to show your code`

Can't seem to make it work. Can you see the code now?

Oh yes! Can't believe I didn't think of that case. :/

Thanks!

i wasted nearly 20 min looking at my code and then looked at the result and released it was runtime error rather than wrong answer :(

Did you pass test case 10?

yes

How to solve div2

B?Let's say you want to go from $$$i$$$ to $$$j$$$ such that $$$i < j$$$.

The given condition is that $$$j - i = b[j] - b[i]$$$

So rearranging that: $$$j - i = b[j] - b[i] \Leftrightarrow$$$ $$$ j - b[j] = i - b[i]$$$.

So now for every equal value of $$$i - b[i]$$$, get the maximum sum of all $$$b[i]$$$ (you can do that using a map).

I got it now Thanku :)

appriciate your answer

Thank U.

Hi! The tests, practice and some functionality are hidden because of the onsite event. We will open it after the official award ceremony in Moscow. Please be patient a little!

do they livestream?

yep, here is a link https://vk.com/techno_cup?z=video-114611688_456239139%2F2e4a5fcbfbd8119b19%2Fpl_wall_-114611688

It's possible to have O(log) in div1 D only because of one modular division (and have no segment trees at all).

We know that we can move two adjacent ones. Due to the statement, we can swap them with an adjacent zero and of course, we can imagine swapping them with an adjacent one.

So, when we have a string, let's imagine turning it into its canonical form — let's pull all the pairs of adjacent ones to the left: 011101111010->111111010010. This new string has a prefix which consists of an even number of ones and then some suffix which has no neighboring ones (but can start with a one).

As we are asked if two string of the same length are reachable from each other, we can assume that we want to compare only these two suffixes. If these two strings have different number of mentioned pairs, then the suffixes will have different lengths, so we'll know that they are not reachable from each other. If the suffixes have the same length, we'll just compare them as strings.

So, we need some hash function, which will "skip" adjacent pairs of ones. I'll use linear functions as the hashes of zeroes and ones, let's call them $$$f_0$$$ and $$$f_1$$$. The hash of a concatenation of two strings will be the composition of the two functions. The only condition is that $$$f_1(f_1(x))=x$$$ must hold for every possible $$$x$$$. Let's then set $$$f_0=random \cdot x+random$$$ and $$$f_1=-x+random$$$.

The composition is associative, so we can calculate the composition for every prefix and then calculate the function for an interval with one modular division.

I think you can calculate more straightforward hash for each prefix, for example, consider a string: the number of ones modulo 2 before the fixed zero. And after that you should binary search for each query, to find the set of zeroes. Then you should check that two substrings are equal (or check that one substring is inverse of another one, if parity is different).

Also you can change binary search to some straightforward linear time precalc, and solve the problem in linear time.

Yea, there are different solutions, but I think that mine is quite educational, so I've described it.

It is possible to have O(1) in div 1 D.

I couldn't find the observation that we need to remove pairs of 11 during the contest. Instead of it, I found other pairs of observations:

1) numbers don't change the parity of their positions

2) If one zero was before another zero, they should store the order.

It is actually identical to removing 11.

But these lead to the solution, that because the number can change their position, but can't change the parity of position. Let's just compare the parity of positions where zeros are located.

101011 -> 2 4 -> 0 0

010111 -> 1 3 -> 1 1

Now let's just remove all ones from the initial string, and just store the parity of positions of zeros. And build hash over this string.

To answer query just compare hashes of this new string in compressed positions. To solve the problem of different parity of initial start, we need to build hashes of two string, where second just inverse of first.

I had O(log) just to find the position of beginning new interval in the compressed string. But it can be done in O(1) with O(n) preprocessing just store position of start for each index.

P.S. my code is a bit messy, because I wrote another solution and only then added this idea. Better refer to the text.

72206443

Better version of code here -> 72212662

Do you have a solid proof for why just comparing parities of zero positions works?

Yes, I would try to explain.

it can be easily transformed into removing 11 and comparing the rest of the string by equality.

What information we are losing, the pairs of 11 between zeros. Because removing 11 didn't change the parity of positions.

0110 -> 0 1 and 00 -> 0 1

But as it was described above it is redundant information, it didn't change anything.

Then we can lose some lonely ones :

010 01010,

But actually we are not losing because knowing the parity of two consecutive zero, we can understand if it was 1 between them

010 -> 0 0

00 -> 0 1

0010 -> 0 1 1

000 -> 0 1 0

So storing the parity of zero's position is the same as storing the whole string of 0s and 1s (where there is no two consecutive 1)

Yep, one of solutions we had for this problem works in a similar manner, but we substitute $$$0$$$ and $$$1$$$ by some matrices $$$A$$$ and $$$B$$$ such that $$$B^2=k \cdot I$$$ for some number $$$k$$$ and unit matrix $$$I$$$. We check that matrix products on corresponding segments are equal, which may be done in $$$O(1)$$$ per query with a bit of prefix and suffix products. You may also solve this problem in a similar manner.

~~Though I still think that one should solve this problem in a deterministic way.~~Hey! Don't quite understand how to "inverse" the prefix for the substring in that case. So, as I understand $$$ prefix_i = f_{s_i}(prefix_{i-1}) $$$. Having that, we need to take $$$prefix_r(prefix_{l-1}^{-1}(0))$$$ and this requires to maintain the polynomial. Probably I got it wrong. Could you elaborate please on that?

Really cool! Do you know how to reason about the probability of error?

did anyone think to solve C div 2 using 0/1 dp? i was trying to solve it like knapsack but didn't get it right..any suggests will be highly appreciated

For C you could've just used basic greedy solution that uses bfs. Just try some cases and see that greedy solution works all the time and try to implement it with bfs.

i am trying to upvote you after a stupid mobile misclick on the downvote but it seems i cant undo my stupid mistake, please accept my appology and if you reply to this i will upvote so you dont get negative upvotes, and thanks for your response i will try it out, iam kinda new in here, once again i am very sorry

remove biggest possible option until you run out of options.

Using knapsack DP is invalid because your state has to indicate which indices have been deleted (using bit-masking or similar) which can't be done given that the size is 100, same principle applies to back tracking or any permutation technique I can think of.

HintThink of some brute force solution where you start by deleting each occurrence of some alphabet that does not affect the solution (the alphabet that does not contribute in deleting any other alphabets)

Achievement unlocked: Place last in a Codeforces round

Why is this an achievement, I do this all the time.... :(

Hahaha

round is rated or not ?

Yes.

How to solve Problem B(Div 2)?

This is the solution that I found the easiest to understand: Comment

When will they put the tutorials/solutions?

shit! I misread the sentence is div.2 C. Because the title contains the word "Adjacent" I thought it is allowed to remove character not only the adjacent in position but also in the alphabets. I am so sad.

Me too :(

But any idea on how to solve this version of the problem?

What I tried to do is firstly devide-and-conquer approach: If we know range [l,r) is deletable then l-1 and r becomes adjacent now and may be deletable. Secondly, I thought it is graph something. The alphabetical adjacency can be expressed as graph and it is obvious that at some moment, a node with degree one should be higher priority than those with higher degrees. After these thinkings however, I couldn't find the way out. Regret is that I should test the sample 1 so I could find myself misunderstood the problem sentence.

one of the weirdest and most boring rounds I've ever participated . I hope next round will be more exciting and fun XD

For me the problems where not that bad. The fact that others solved them much faster than me was :/

However, I think Div2 B and C where kind of math problems, since once the key observation is clear, it is more or less trivial implementation.

When will ratings get updated?

.

cool and nice div1 contest :)

My (correct) div2 D solution timed out using py3 in post contest tests but when I resubmit I pass based on random variation in timing... Anything I can do or is it just what I get for using python?

why im getting runtime error and tle at test case 5 of div2 A..?

May you are dividing by zero

How to solve Div 2 Problem C: "Remove Adjacent" ?

I did this. submission

Submissions are not visible right now

I started at the maximum value in the string and kept deleting elements before and after it until I there are no elements which satisfy the given condition and do it all over again while decreasing the maximum value. I hope that makes sense.

Got it, thanks

Where can I find Editorials of these questions..?

Became a Candidate Master ~ Happy happy day >__<!

me too, bro — ^__^

became an expert again:(

Final round rated?

Ummmm..... I cannot find the solution, editorial please help me

The pretests in this contest is too weak :( I have dropped my rating because of this too many time. I hope this is the last :(

How terrible!The second problem in Div 2 is the first problem in Div 1!

When will be the editorial?