Yeap, but [contest:297213] will be officially for students of regional universities Belarus and Ukraine only.

Comon, I was typing when the first guy put the message and it went unnoticed to me and i get 22 downvotes, nice.

Yeah, same here, 10AM for me :)

Perhaps they both prepared the problems and tested each other's problems :)

my experience says it will be similar to the one you mentioned.

Absolutely it was not like Round 657, but the scoring distribution was not standard. I am not sure why people strictly prefer downvoting comments, I was just talking of a possibility which came almost true for this round.

And Now you are getting contribution for your efforts. Enjoy! :)

*Asian

Jokes over, you're dead!

It will be 12.04 am ig

Woah! Could you please prove it... Might be a hacking attempt or you are just upto defaming me. If the latter case, then you might have read the article on 'evercookie' too. Mike can easily find you, if he wants to.

Consider the contribution of each digit to the sum. For each digit count the number of subarrays before it which were deleted. In this case the contribution is fixed. Consider 1,2,3,4 and the contribution of the 3 for all subarrays before it which could be deleted. The contribution would be 30 * (number of such subarrays) which is 30 * 3.

Then count the contribution for the subarrays after it which can be deleted. This required some weird sum manipulation. Consider 1234. Consider the digit 2. There can be one subarray of size 2 after the digit 2 which can be deleted and 2 subarrays of size 1. So, the contribution of 2 would be 2 + 20 + 20. This can be written as 2 * (1 + 20). If you do this, you'll see a pattern.

Consider the given string in reverse. Now for each position $$$i$$$ from 1 to $$$n$$$, let us calculate the contribution of $$$s_i$$$. In case the removed substring was to the right of it, then the contribution of $$$s_i$$$ is $$$10^{i-1}s_i$$$. The number of such substrings are $$$n - i + 1 \choose 2$$$. In case removed part is to the right, then the contribution is $$$s_i\sum_{z=1}^{i-1}z10^{z-1}$$$. The summation can be maintained while iterating over the string.

https://medium.com/@harryjobz/bargain-a6cf0b9a5262 I have explained it here since the actual explanation is too long to write it here

Basically for a particular cell $$$a[i][j]$$$ the palindrome squares which should be equal are

(notice this works even when these are 2 cells and not 4), now our task is to chose an $ x$ such that $$$|x-a|+|x-b|+|x-c|+|x-d|$$$ is minimized where $$$a,b,c,d$$$ are the four cells mentioned above,its easy to see that if $$$a\leq b\leq c\leq d$$$ then any $$$b\leq x \leq c$$$ minimizes this expression; so for convinience pick the average of the middle two numbers.

Here is my submission 94697945

My Approach was a[i][j],a[m-i+1][j],a[i][n-j+1],a[m-i+1][n-j+1] should be equal

I'm not sure if this is the best solution, but here goes

Iterate through the entire array. If for all elements in the array, ar[i][k] = ar[n-i-1][k] = ar[n-i-1][m-k-1] = ar[i][m-k-1], that means that the array is a nice array (this is derived from the definition of a nice array)

So we iterate through all the elements in the array, and we have to make adjustments to the four elements that I listed above in order to make it a nice array.

Call the four elements in question, a_1, a_2, a_3, and a_4. Let the value that we want to change all the four elements to be x. Clearly we want to minimize |a_1 — x| + |a_2 — x| + |a-3 — x| + |a_4 — x|. This is a pretty standard greedy algorithm problem, and the minimum ends up being achieved when x is the median of a_1, a_2, a_3, and a_4.

My Solution: 94693568

I was printing last two letters wrong in some cases and got pretests passed, so i think that was not covered on pretests

my first submission fails on "bbzzbzzba"

Some fail on "bccba"

yzzyx

From my experience, there were 2 things to consider:
1. You can't remove pairs which are not continuous in the original sequence
2. You need to keep the two stacks in sync, the one with the last different element and the one with the current answer. If you pop from one, you need to pop from the other too. Similarly for pushing

Mine broke on aaffaihe

Ashishgup were you able to figure out the hack for your solution?

I am asking since my solution had the same wrong answer on the same line in the same testcase so I was just wondering if you figure it out do reply. Thanks

think dp

Is "write a DP" elegant enough?

My DP state is

[processed prefix length][# of blocks of removed digits so far][did we remove the last digit?]=(sum of possible numbers, count of possible numbers)

Transition is to consider two options: to remove the current digit or to keep it. Code: 94671611.

My approach was, take every suffix of the string, now we have to combine it with every prefix(there should be gap of atleast one character between ending of prefix and starting of suffix),maintain sum of prefixes.Combining is multiplying length of suffix with the sum of prefixes and adding it to current suffix.

94711980

My approach didn't have much edge cases except for the first and last digit. You can calculate the contribution of each digit in answer by considering 2 cases :
1. If a substring before the current index is removed, it won't affect the place value of the current digit, say $$$d$$$ and is equal to $$$d*i*(i+1)/2*10^{n-i-1}$$$.(0 based indexing)
2. If the substring removed is to the right of the current index, it's contribution is : sum of $$$(j)*10^{j-1}*d,$$$ where j is from (n-i-1) to 1.
My implementation.

vector<ll> pw(100005,0);
string s;cin>>s;
int n = (int)(s.size());
ll cur = 0, ans = 0;
for(int i=0;i < n; i++){
    ll pos = 1LL*i*(i+1)/2;
    int d = (int)(s[i]-'0');
    (pw[n-i-1]+= pos*d)%=mod;
    (cur += d)%=mod;
    if(n - i - 2 >=0)
        (pw[n-i-2] += 1LL*(n-i-1)*cur)%=mod;
}
for(int i=0;i<=100005;i++){
    (ans += 1LL * pw[i] * powmod(10,i)%mod)%=mod;
}
cout<<ans;

I don't have a proof but... I built a graph:

• vertexes are the given points

• connect start and all "movement points" with weight: min(abs(s_x — x), abs(x_y — y))

• connect each "movement point" with 4 the closest "movement points" by x and y.

And then run Dijkstra on this graph!

Seems if you want to jump from "movement point" A to "movement point" B you have to spend the same time as if you visit all "movement point" between them.

shortest path problem

For each number at ith index, try to see how much contribution it can give to final answer.

Observe the pattern :

S = "12345"

Removable Sub-Strings :

length_1 = '1', '2', '3', '4', '5'
length_2 = '12', '23', '34', '45' length_3 = '123', '234', '345'
length_4 = '1234', '2345'
length_5 = '12345'

Strings Left after removing the above Sub-Strings :

'2345' (after removing '1')
'1345' (after removing '2')
'1245' (after removing '3')
'1235' (after removing '4')
'1234' (after removing '5')
'0345' (after removing '12')
'0145' (after removing '23')
'0125' (after removing '34')
'0123' (after removing '45')
'0045' (after removing '123')
'0015' (after removing '234')
'0012' (after removing '345')
'0005' (after removing '1234')
'0001' (after removing '2345')
'0000' (after removing '12345')

'0's are appended at the first for the ease of understanding. You can ignore them.

Contribution of every index in the total sum :

0th index ('1') = 1 * (4*pow(10,3) + 3*pow(10,2) + 2*pow(10,1) + 1*pow(10,0) + 0*pow(10,4))
1st index ('2') = 2 * (------------------- 3*pow(10,2) + 2*pow(10,1) + 1*pow(10,0) + 1*pow(10,3))
2nd index ('3') = 3 * (---------------------------------------2*pow(10,1) + 1*pow(10,0) + 3*pow(10,2))
3rd index ('4') = 4 * (------------------------------------------------------------1*pow(10,0) + 6*pow(10,1))
4th index ('5') = 5 * (------------------------------------------------------------------------------10*pow(10,0))

Hope it helps !!!

The memory limit is tight for segment tree with persistency. 1024 MB may be better.

I think, it's to cut off solution with algorithm Мо.

I know how a persistent segment tree works, but I'm not too familiar how to use it. Can you explain how you used a persistent segment tree in F?

I thought everything other than A was really difficult

I dunno. Maybe slightly more difficult that a typical div2

NOt completely div ,but much harder than a general div2 round

The contest was not horrible. Your participation was horrible

I agree, I spent too much time on D(which I couldn't solve). I missed to submit E by just 1min. By correct scoring distribution we could have seen atleast 600 people solving E.

I wasn't able to understand E

In the second example, for the longest suffix "abbcdddeaaffdfouurtytwoo" choose three pairs (11,12), (16,17), (23,24) and we obtain "abbcdddeaadfortytw"

Why (2,3),(5,6), etc weren't selected? I apologize if I missed something?

Much easier if you don't read the statement, amirite?

in my computer, all of things is going fine

Before system test

After system test

Yes you can calculate an AGP by dp see the below comment of mine!

One more dp solution for problem C: 94861783

I store 3 things:

1. value of substring that ends in current pos and has no crosses

2. (count, sum) of substrings that end in currend pos and last digit is crossed

3. (count, sum) of substrings that end in current pos and last digit is uncrossed, but it already has some cross before

1 transition is just prev*10 + current

2 transition: we can cross current digit only if we have previous digit crossed, or if we take substring without any crosses and put first cross now, hence count is 1 + all that end in previous digit and last is crossed, and value is just sum of same things: value ended in previous digit and all sum of values that crossed in prev step. Since we don't add anything to the end we don't need to multiply.

3 transition: we can add new digit (uncrossed) to any sequence that ends in previous digit and last is either crossed or not crossed (but already has some crosses before). (it's sum of 2 and 3 in dp) also we multiply it both by 10 and add current digit respective number of times. Because if we have 3 sequences that end in previous digit and we can add new digit to all of them and and this will create 3 different combinations.

And the answer is sum of all sequences where last index is crossed and last index is not crossed but it has some crosses before.

I'm not sure that it helps anyone, but I was so glad this solution worked, so I couldn't help but share with you guys.

What is agp?

Can you please explain how you got this AGP for the right part of every ith digit, I tried to make a formula but that's completely different from this, I thought that if I am at particular index 'i' then contribution of this digit will be

i*(i+1))/2 *10^(n-1-i) *d[i] where d is digit sequence + .

(zC1*10^(z-1) + zC2*10^(z-2) + ... + zCz*10^0)*d[i].

Not: here 'z' refers to s.size() — 1 — i

Can you please help me in getting why my second part of formula is wrong? According to me there should be zCx ways to remove x elements from the given number of elements will it not be correct here?

Similar to what I did in-contest, but I think my approach might be quite a bit cleaner:

My submission

why i*(i+1)/2?

nice sarcasm on pretests

Thank you, we tried our best.

Actually this one is trivial. The reason why we need testers is Education Round 95. Though it seems they had a couple of testers.

1 1 1 9

n=2, m=2 1 2 3 10

(a[i][j] + a[n-i+1][j] + a[n-i+1][m-j+1] + a[i][m-j+1]) / 4 = 4, which gives a total modification cost of 12, however the solution is actually to change all values to 2, or 3, giving a total modification cost of 10.

Constraints on the number of pretests?

Yeah, its a while ago I was solving a problem that asked us to equalize all elements of an array where you could only use an increment. I misinterpreted it as equalize using either an increment or decrement. Broke my head for 15 min to either prove that it was equalized to median or most frequent element or avg, and gave up, only to realize I had read the q wrong. But luckily after the contest when searched up upon the misinterpreted problem, I found this — proof

Happy learning!

aropan can you please explain?

Got it. Thanks

1 2 3 4
5 6 7 8
9 10 11 18

The last element is $$$18$$$, but not $$$12$$$.

Even if you use your matrix, the answer is still 42, not 36.

Exactly.. How?

bccba

Correct answer: 3 bba ...

you: 1 a ...

Check for "bxxb", you will understand that we had to do the operation only once. The answer for this is -
2 bb
1 b
2 xb
1 b