are there names for each color? (like pupil, expert etc on cf)

Maybe a little bit to exited for a contest that happens once a week. :)

I can't solve C either until I use cin cout instead of scanf printf :(

I thought I was the only one.

Why to use chainsaw when work can be done with butter knife!

Yes it can be solved without segment tree My approach

1) Keep track of current sum of total elements

2) Keep track of numbers of all the integers in array (i.e in array {1,2,1,3,1,,2,3,4} a[1] = 3, a[2] = 2, a[3] = 2, a[4] = 1. And current sum = 14.

3) Than for each query update update the sum as

sum = sum + (number of element in a[first number]) * (second number — first number)

4) than change the array a at appropriate indices

Segment tree is way overkill. It is actually quite simple. ARR[100005] stores the number of occurrences of each number in V[N] (V is the inital array given in the input). SUM stores the current sum of all elements. Then you encounter a query for example (1, 2). You know you should change all 1's into 2's. So just do S -= ARR[1] (coz 1's no longer exist). then S += ARR[1]*2 (coz all 1's are now 2's). And then ARR[2] += ARR[1] and ARR[1] = 0.

Use Map

C

E

E was Easy

C:

E:

For E:
Observe that you can get value of ith scarf if you xor all a[j] (where, 0<=j<n and j!=i). But if you calculate all values like this, then complexity will be O(n*n), so what you can do to optimise is calculate any ith scarf value using method described above(say value of 1st scarf) and xor it with a[i] (here a[0]) , it will give us xor of all scarf values(say x). Then you can use this value(x) and xor it with each a[i] (for 0<=i<n) to get ith scarf value. My solution : Solution
C is just calculating column name in a spreadsheat for given row(N) ,refer this : GeekForGeeks

Check the video editorial out

Basically, keep a map which has the count of all numbers occurring in the array, and after each query, update the map. My submission-https://atcoder.jp/contests/abc171/submissions/14549573

Can you please tell the approach after the contest ends? Thanks.

This sentence you wrote here, google it when contest is running, you'll find an answer

Check out My Video Editorial — F

Why are we doing n-=1 every time in the question c?

How did you come with that solution for F.

I thought something like:- 26^k * (n+k)Ck ,then subtract all cases.

in prob. C, can you explain why n -= 1 ?

alexwice could you elaborate how did you come up with such simple approach for F? My approach was to build strings which have the given string S as a subsequence, So we would need to choose |S| positions from K+|S| places, and fill the rest with any 26 letters, but the problem is overcounting. How does your solution handle this?

For F, why is this Wrong:

Number of strings such that S is a subsequence of string of length |S|+K : C(|S|+K,K)

Number of strings of length K : 26^K

So answer = C(|S|+K,K) * 26^K

Can you explain why only the length of S matters?why different string of the same length won't affect the answer?

your F code is giving WA.

Why the answer is the same if S was all 'a's ?

What else of a meaning can that be? It must be distinct strings even without the word distinct.

It involves fundamental combinatorics only — of placing x same objects in N different places and filling the rest with any object other than x . If you still are having problem understanding the editorial refer to this Video Editorial — F.

convert N into base 26

It was in January or february cookoff this year. I couldn't solve it then but watched a video tutorial of it after the contest. I solved it today in one go without even reading the problem completely :)

[deleted]

I manually computed the initial sum instead of using accumulate , and got AC using your code. I don't understand why accumulate was giving you WA though.

Thanks!

Yes I tried that in the same way but it's wrong. I think it's because your counting some things more than once.

You end up overcounting, because you can reach the same final string $$$T$$$ in many ways (for example, if you start with $$$S$$$ = abc, you can reach $$$T$$$ = abbc by inserting a b either before or after the middle b).

I have a detailed explanation in this post.

Key observation: ans is fixed whatever the string is. Only length of string matters (and K too).

Your code with minor changes..

I removed accumulate line because I didn't know what it did and precomputed res while taking input, and changed a bit in calculating res during query.

thanks a lot for such a good explanation.

btw could you suggest me some problems on combinatorics(or any sources) if you know any?.

Seems so easy after reading this explanation. Thanks! Minor typo in the last formula $$$i$$$ should be $$$x$$$.

It should be $$${|S|-1+k-x \choose |S|-1}$$$?

Why build 'a' such that 'ai' is minimum ? What about the other cases ?

In the last formula, it should be $$$+k$$$ instead of $$$-k$$$. It confused me for a while until I see your code.

There are repetitions in your approach. You are fixing say: _ _ o _ _ o_f_

but then _ o o _ _ o _ f _ is counted thrice