Thanks for the quick editorial.

I think calculating answer for each possible query is also an option in the given constraints in G.

A different approach for F, time complexity is O(n). Consider each permutation number as a node and create a directed graph by making an edge between adjacent nodes of the permutations (doesn't matter if from left to right or right to left). Some cycles may appear and it's obvious that all nodes in a cycle have to have the same letter in a string. Then just get strongly connected components and each can have a different letter. If there's less components than necessary K, print NO, otherwise do a topological sort on those components and give them letters correspondingly. Here's my code: https://codeforces.net/contest/1213/submission/59754658

For problem G, what if the queries are onnline?.

Ого какой быстрый разбор. Благодарю

Hi. Could someone please tell me why, in question D1, the number of possible candidates is O(nlogn) and not O(nlog(max(Ai)))?

Why D2 don't get tle ? We have 1e5 values and we are summing k values so k*1e5 ==> 1e5*1e5 ?

For the problem D1, I don't understand the statement: We can see that there is always O(nlogn) possible candidates because all values x are among all possible values of ⌊ai2m⌋ for some m from 0 to 18. So we need to check each candidate separately and try to update the answer with it.

Also, how are we selecting the value for x? is it in the sequence 2,4,8... or do we calculate x in some way and then use it to check the elements in array which can be reduced to it.

Thanks. :)

Can anyone tell me what's wrong in my code for G. It is failing on the 4th test case. I have done the exact same thing as the editorial suggested.

link

Can some plz explain to me the approach for problem-C? Thanks!!

In G you can also just do $$$res := res + s_{1} s_{2}$$$, since exactly $$$s_{1} s_{2}$$$ new paths are formed by adding the new edge. Indeed,

$$$\binom{s_{1} + s_{2}}{2} - \binom{s_{1}}{2} - \binom{s_{2}}{2} = \frac{(s_{1} + s_{2})(s_{1} + s_{2} - 1) - s_{1}(s_{1} - 1) - s_{2}(s_{2} - 1)}{2} = \frac{s_{1}^{2} - s_{1} + s_{2}^{2} - s_{2} + 2s_{1}s_{2} - s_{1}^{2} + s_{1} - s_{2}^{2} + s_{2}}{2} = s_{1} s_{2}$$$.

vovuh Can you explain why my approach is wrong for D2

I run a loop from j = 1 to j = 200005 considering each j as an optimal value which will be our k equal elements. Now for each j I calculate the minimum number of steps required to get k occurences of j.

For that I have sorted the vector already and follow this startegy

Suppose I want to make x as my optimal value , then in 1 step i can get x from elements which are in the range 2*x to 2*(x+1)-1 in 2 steps i can get x from elements which are in range (4*x) to 4*(x+1)-1 in 3 steps i can get x from elements which are in range (8*x) to 8*(x+1)-1 .... and so on.

to get the number of elements in a range I use upper_bound and lower_bound on my sorted array.

Why is this approach failing for test case 4?

code -> code

Can G be solved without DSU?

All people who managed to solve E problem, I just want to know what struck you? what idea came to your mind. Do you think you solved it because you have solved similar problems in the past... if so do share them?

I think there is an O(N) solution to F (sadly not completed during the contest). See https://codeforces.net/contest/1213/submission/59767381.

My code first inverts the q permutation so that it maps s indexes to q values rather than the reverse; then by working backwards through the p values I can find, for each index of s, the minimum q value corresponding to any later p value.

Finally, it fill in s in p value order keeping track of the maximum q value associated with the letters of s filled in so far. It starts with filling in with 'a's. Whenever the maximum value it has seen is less than the minimum value q value associated with later p values it can move on to the next letter. This continues until it has k different letters, at which point it simply fills in the remaining characters of the string with the final letter.

I have been trying to solve at least problem 'A' in last AUGUST month. But always failed to solve even 'A'. Maybe I am not even considered as a 'newbie' in problem solving.

Another way to look at D2, we consider every value from 1 to MaxVal in array to be the optimal value and choose the best ans.
1. Mark the frequencies of all elements in an array.
2. Consider all values from 1 to MaxVal.
3. For value i we do a BFS on a tree to get the cost.
The tree here is a binary tree with root node as 1 and the child of node i are 2i and 2i+1.
A node at same level as Source node i of BFS will take 0 cost to convert to i, nodes at 1 level under will cost 1 to turn into i.
So the BFS will run till: either we have found k elements or it is not possible to make k elements equal to i. Time Complexity : MaxVal log (MaxVal) https://codeforces.net/contest/1213/submission/59750061

in problem E it's for permutations of c_1 ,c_2,c_3 it's enough to only consider abc & acb because all others permutations will contain the same sequence of repeating letters by just rotating these two permutations so we can only narrow down our search space instead of 12 to be 8

Can someone please help me with understanding the time complexity of "1213D2 — Equalizing by Division (hard version)". I understood the time taken to prepare the array cnt in O(nlogn). After that the process of finding the sum of k smallest values for all values of x should take another O(n*nlog(n)) since for each x [0 to 2*10^5], we need to sort the array of values (the count of these can again be upto n ie. upto 2*10^5 taking O(nlogn)) to obtain the smallest k values? Please let me know where am I getting it wrong? Thank You.

Is this the other correct way to solve problem A?59723491

F можно решить и по-другому. Можно представить ориентированный граф (вершины это позиция символа в строккюе), где ребро из u в v, означает s[u] <= s[v]. Давайте в жадную решать с дфсом, если идём в другую вершину увеличиванм значение буквы. Проблема в том что могут быть циклы, но это решаеться конденсацией графа. Получаеться Топсорт + Конденсация графа

Well.. now I know how to solve problem F. but.. WHY to do so??(#｀-_ゝ-)

I had tried to understand the tutorial's solution for hours but failed.. Could someone give me a explanation? thx ( •̀ ω •́ )✧

What is wrong with my solution for D2 . My solution was also O(nlogn) but got TLE while submitting... Can someone point out the mistake my submission — https://codeforces.net/contest/1213/submission/59748079

Missed expert by 8 points :(

Is it possible to solve G for online queries? Did anyone solve?

I think there is a better solution for F.Time complexity:$$$O(n)$$$

We can build a graph as follows: for each $$$s[p_{i}]\le s[p_{i+1}]$$$,$$$s[q_{i}]\le s[q_{i+1}]$$$, we can connect $$$p_i$$$ and $$$p_{i+1}$$$ . Similarly we connect $$$q_i$$$ and $$$q_{i+1}$$$ .

It is easy to prove that we should set the same letter in those positions which are the points on one cycle on the graph that we built.Then we can use Tarjan to "Shrink point", thus we can get a DAG.

We can think of the DAG as a layered graph. Because we have to use at least $$$k$$$ letters, if the graph doesn't have at least $$$k$$$ layers, it's impossible to construct such an answer.

Then we give each layer one letter in turn. If there are more than 26 layers, just set those layers as letter 'z', it's not difficult to prove it.

Time complexity:$$$O(n)$$$

code 59775323

// I used map to remove duplicate edges, this is not necessary.

Can someone give small test case like TC-20 for problem F? Nvm was a silly mistake.

Duh, in problem C i failed in test 6 when was using the python, and the approach seems to be fine, but I didn't have time to reimplement my solution in C++. Today when I reimplemented it with C++ it passed all tests -------------_________________------------------

btw commented python total calculation is my original formula and it works in cpp, even with algorithm from author python solution didn't work

# python Fails at test 6: wrong answer 212th numbers differ -
# expected: '4999999999999954', found: '4999999999999958'

import math

'''
# 7
# 1 1
# 10 1
# 100 3
# 1024 14
# 998244353 1337
# 123 144
# 1234312817382646 13
'''


def calculate_sequence(m):
    _iter = 0
    _len = 0
    _sum = 0
    while True:
        _iter = int(str(_iter + m)[-1])
        _sum += _iter
        _len += 1
        if _iter == 0:
            break

        
    return _len, _sum

def seq_gen(m, cycles):
    _iter = 0
    while cycles > 0:
        _iter = int(str(_iter + m)[-1])
        cycles -= 1
        yield _iter

def process(n, m):
    seq_len, seq_sum = calculate_sequence(m)
    good_pages = math.floor(n/m)
    multiplier = seq_sum
    complete_sequences = math.floor(good_pages/seq_len)
    left_elements = good_pages%seq_len

    # total = complete_sequences * seq_sum + sum(x for x in seq_gen(m, left_elements))
    total = math.floor(good_pages/10) * sum(m*(i+1) % 10 for i in range(10)) + sum(m*(i+1) % 10 for i in range(good_pages%10))
    return total


datasets = int(input())
for _ in range(datasets):
    n, m = [int(x) for x in input().split(' ')]
    print(process(n, m))

// C++ complete solution

#include <iostream>
#include <list>
#include <algorithm>
#include <map>
#include <string>
#include <math.h>
#include <iostream> 

typedef long long longint;

void calculate_sequence(longint m, longint& len, longint& sum) {
	longint _iter = 0;
	longint _len = 0;
	longint _sum = 0;
	while (true) {
		std::string newIter = std::to_string(_iter + m);
		_iter = std::stoi(newIter.substr(newIter.size() - 1, 1));
		_sum += _iter;
		_len++;
		if (_iter == 0) {
			break;
		}
	}

	len = _len;
	sum = _sum;
}

longint seq_sum(longint m, longint cycles) {
	longint _iter = 0;
	longint result = 0;
	while (cycles > 0) {
		std::string newIter = std::to_string(_iter + m);
		_iter = std::stoi(newIter.substr(newIter.size() - 1, 1));
		result += _iter;
		cycles--;
	}
	return result;
}


longint process(longint n, longint m) {
	longint len;
	longint sum;
	calculate_sequence(m, len, sum);
	longint	good_pages = floor(n / m);
	longint complete_sequences = floor(good_pages / len);
	longint left_elements = good_pages % len;
	longint total = complete_sequences * sum + seq_sum(m, left_elements);
	return total;
}

int main() {

/*
1
1234312817382646 13
*/
	int q;
	longint n[1000];
	longint m[1000];
	std::cin >> q;

	
	for (int i = 0; i < q; i++) {
		std::cin >> n[i] >> m[i];
	}

	for (int i = 0; i < q; i++) {
		std::cout << process(n[i], m[i]) << std::endl;
	}
	return 0;
}

This is a total disaster...

can anyone please tell me why am i getting TLE at testcase number 6 for poblem G. I am using DSU here is my code link

for the problem E how someone will come up with this kind of solution and can be so sure all the ans lies in these 12 pattern. its very difficult for someone to think this way. pls help with your approach.

My code(problem d2) work in 77 ms. 59748709

Anyone please tell me... What is the intuition behind the editorial of Problem F?

In E how one can prove that, by following algorithm we won't miss any possible permutation? can somebody prove that by that construction it is impossible to miss any permutation of 3n numbers(also considering constraints in the problem)

For C I used similar approach as in editorial but getting memory limit exceeded. Can anyone of you help me https://codeforces.net/contest/1213/submission/59756440

Proof of Correctness of E

If you want the graphs to embedded within the text, you can read this link

Let us draw a graph on 3 vertices, namely a , b, and c. There is an edge from i to j if it is permissible to go from i to j. Notice that there can be self loops. Initially, the graph looks like this.
Initial Graph

Now, as soon as we receive a query, we need to remove the corresponding edge in the graph. For example if the string s is ab, it means we won't be able to go from a to b as it is now forbidden. Similarly, if the string t is cc, it means that we need to remove the self loop of c. It is clear that we need to remove exactly 2 edges from the graph, and after that if we can traverse the graph such that all the vertices are visited exactly n times, and at the same time, ensuring that we travel only on permissible edges, then we can get our answer.

Case 1 --> We remove 2 self loops.
Graph of Case 1
Observe that we can travel the graph in the path abc abc ....

Case 2 --> We remove 1 self loop and 1 normal edge.
Graph of Case 2
WLOG, assume that the directed edge from a to b has been removed. This means that if we start at a, we can't directly go to b. Fine, Let us start from the vertex which isn't reachable in one move, i.e b. We traverse the graph in the manner bac bac ....

Case 3 --> We don't remove any self loops. For each edge i --> jwhich is removed, we will call i as being marked.
Sub Case 1 ⇒ Only 1 vertex is marked
Graph of subcase 1
WLOG, Suppose, only the vertex a is marked, this means that both outgoing edges from a is removed. We can traverse the graph in the orderccc... bbb.... aaa...

Sub Case 2 ⇒
Graph of sub case 2
2 Vertices are marked. Suppose they are a and b. If we cutoff both the link of a and b, we can traverse the graph in the manner acb bca acb ..... So now, the only case remaining is the one where the edge a ---> b is cutoff, and the edge b --> c is cutoff. Notice that we can still traverse the graph in the manner acb acb ...

In Problem D1, my approach was similar to the editorial. I sorted the array , now we traverse it and for each element we see that with the next(higher elements after it as array is sorted) elements can give this a[i] element or not. If yes, we add the number of divisions("cost" variable) needed. Repeat till we get k similar elements.(if possible) Repeat this process for all elements of array.

Now we have min divisions needed to form a number. k times. which already existed in original array also. in "ans" variable. Now I checked minimum divisions needed to make k Zero's. Printed minimum of them both.

It Fails on 5th case.Please Help! 59830286

Why the E problem solve is that? Why is the permutations of the string "abc" ? help me. thanks

For problem F, what is the approach or intuition behind vovuh solution in the editorial? Although, I am able to understand what is done while inserting/removing from the set until they are equal but not able to understand why this approach is used and what will be the mindset for similar future problems?

excellent editorial

This O(n*n*logn) solution ( https://codeforces.net/contest/1213/submission/60268220 ) takes ~ 217 ms . However an identical but faster O(n * n) solution (https://codeforces.net/contest/1213/submission/60267572) takes about ~1800 ms and also more memory. Please explain what's wrong? Is the complexity analysis wrong or what?

Thanks for this.

If I am not mistaken, I found a solution for D2 with O(N * log2(max(a[i]))) complexity. Sort of O(N * 20) ~ O(N). That is the same complexity with such limits as O(N * log2(N)), but maybe it would be interesting for someone. I've used binary prefix tree — http://codeforces.net/contest/1213/submission/60412397

In Question E (Two small strings), I am getting wrong answer on fourth test case

1 ab cb

judge's answer is NO but I think we can construct res as "bac".

Please help.

D1/D2:

There exist O(max_value) solution for this problem, which is O(n) by the problem statement.

We create LOGN arrays of sizes MAXN, MAXN/2, MAXN/4, ..., 1. Array number j will store (under index i) how many numbers are there that require exactly j divisions to get to value i.

We see that Array[j][i] = Array[j - 1][2 * i] + Array[j - 1][2 * i + 1], and Array[0][x] = number of occurences of x in the input.

Now, for each candidate value x in range [1 .. MAXN] we only need to greedily take first k cheapest elements that leads to x. We do this by taking elements group by group until we get total of k elements.

This way, we only once compute values for each array element and only once retrieve value from the array. Note, that the total size of the array is MAXN + MAXN/2 + MAXN/4 + ... + 1 <= MAXN * (1 + 1/2 + 1/4 + ...) = 2 * MAXN = O(MAXN).

My C++ code for this solution: submission/60682312. It takes 62 ms to execute.

I can't solve problem D2 (D1 too) in the contest because of my poor complexity analysis. At the time, I thought the complexity was $$$O(n^2 log(n))$$$ and I refused to solve it. Now, I think the complexity exactly is
$$$T = x_1log(x_1) + x_2log(x_2) + ... + x_nlog(x_n)$$$ with $$$x_1 + x_2 + ... + x_n = n$$$.

I want to ask you how to prove: $$$T <= n\ log\ n\ log(n\ log\ n)$$$

i solved D2 using dynamic programming.I created a 2D array a[2.10^5][20]. wherer a[i][j] represent number of element which became i after dividing it j times by 2.

link to my solution: https://codeforces.net/contest/1213/submission/62255328

Another way to think of problem D (or D2 specifically) is to put the numbers [1,2,...,aMax] in a complete binary tree where node i has children 2*i and 2*i+1.

Then the process of equalizing k numbers is equivalent to: choose a subtree of size at least k, with root, say, x; denote Level 0 of the subtree is the number of occurrences of x; Level 1 of the subtree is the number of occurrences of children of x; Level 2 of the subtree is the number of occurrences of grandchildren of x; and so on.

To get the cost of equalizing this subtree, you (greedily) sum 0*(#x's)+1*(#children of x)+2*(#grandchildren of x)+... until you have added up k distances.

It is possible to calculate subtree sizes in linear time, and to build an N-by-log(aMax) matrix descendants[][] where descendants[x][n] = # of generation-n children of x, in O(N log aMax) time.

//My solution for problem A

include

include

include

include

include

include

include

using namespace std; typedef long long ll;

ll solve() { ll ev=0; ll od=0; ll n; cin>>n; vector arr; for(ll i=0;i<n;i++) { ll x; cin>>x; x%2==0?ev++:od++; } return min(ev,od); }

int main() { ll t=1; //cin>>t; while(t--) cout<<solve()<<endl;

return 0;

}

Problem F can be solved differently, too. I think the approach is easier to come up with, but it's harder to implement.

The main idea is that we can construct a graph with the nodes as indices and a directed edge between nodes $$$u$$$ and $$$v$$$ (i.e. indices $$$u, v$$$) if $$$u$$$ appears directly before $$$v$$$ in either permutation. If we ever have a cycle in the graph, then we know that all the elements in the cycle must be the same. (We can detect cycles using Kosaraju's Algorithm to find strongly connected components.) Once we detected SCCs or cycle parts, then we know exactly which elements are less than each other and which elements are equal to each other. Easy from here.

problem F can be done differently, using hashing

here's my submission : 221040748