Yeap, but Andersen Programming Contest 2020. Qualification 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.