Bad luck...

Ildar 300iq Gainullin

Probably not.

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

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

Maybe user profiles)

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

but it isn't infact.

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

Who knows?

Yes.Me too

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

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.

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

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.

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.

I dont know how to say but here it is

res <- 0
for i = 1 -> n
-- input >> x
-- map[x - i] += x
-- res = max{res, map[x - i])
output << res

for 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.

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.

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.

Me too, WA on test4 countless times :(

Think is something like

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

Then i looked at

And when i solved that, it was AC.

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 shrug

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)

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

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

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

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

What's the same?

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.

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.

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

We cant read your code now.

And this `Block`

//if it is test case 5 then you have divide by 0.
//for example may be you have calculated 
int count_r = if(r[i] == 1 && b[i] == 0);
int count_b = if(r[i] == 0 && b[i] == 1);
and for answer you may have done 
cout << (count_b/count_r) + 1;
//here count_r can be zero 

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).

do they livestream?

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.

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

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?

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.

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.

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

Hahaha

Yes.

Me too :(

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

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.

May you are dividing by zero

I did this. submission

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.