#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I_Love_Tina's blog

Does IOI rank correlate with CF rating?

By I_Love_Tina, history, 6 years ago, In English

Background

I have recently stumbled across a paper which analyzed the correlation between the IMO medal and future success in the mathematical field. So, inspired by annual predictions of IOI rankings based on CF ratings, I ~~don't know what to do with my time~~ decided to take a more "serious" approach.

Method

I collected the data from the last $$$7$$$ editions of IOI in order to create the graph of $$$f(x)$$$ is the maximal rating of the participant with rank $$$x$$$. For the last $$$6$$$ editions, I relied almost solely on the IOI statistics website. The $$$2012$$$ edition, however, is missing a lot of information and I collected the CF handles either from snarknews or by finding the handle on search engines.

I put the participants in the same order they were arranged in the scoreboard, so if there are multiple people on the same position, they would be assigned consecutive ranks. In case there was an unofficial participant, I assigned the mean of the ranks between which this participant was situated.

If there were participants with no competitions, I assigned the rating $$$1500$$$. This should not have big influence on the graph because there were very few such participants.

Things to consider:

A lot of participants from past editions don't participate in CF round anymore
The rating system has undergone inflation.
The rating system fluctuates too much.
The style/difficulty/originality of CF problems highly depends on the round and unlike the AtCoder case this creates disproportionality of rating distribution. So do the div 2/div 3/educational rounds.
Not everybody is active in CF rounds.

IOI 2012

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 25 & 0.96 & 2497 & 2573.5 \\ \hline \text{Silver} & 52 & 0.38 & 2220 & 2247.5 \\ \hline \text{Bronze} & 77 & 0.27 & 2137 & 2100.5 \\ \hline \text{No Medal} & 155 & 0.31 & 1802 & 1839.5 \\ \hline \text{Total} & 310 & 0.47 & 2135 & 2124 \\ \hline \end{array} $$$

IOI 2013

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 25 & 0.96 & 2499 & 2528.7 \\ \hline \text{Silver} & 50 & 0.50 & 2321 & 2322.8 \\ \hline \text{Bronze} & 74 & 0.38 & 2145 & 2127.9 \\ \hline \text{No Medal} & 149 & 0.40 & 1826 & 1850.9 \\ \hline \text{Total} & 298 & 0.60 & 2137 & 2130 \\ \hline \end{array} $$$

IOI 2014

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 25 & 0.875 & 2499 & 2538.8 \\ \hline \text{Silver} & 50 & 0.54 & 2270 & 2333.3 \\ \hline \text{Bronze} & 74 & 0.29 & 2127 & 2119.2 \\ \hline \text{No Medal} & 149 & 0.39 & 1919 & 1920.5 \\ \hline \text{Total} & 298 & 0.58 & 2162 & 2170.4 \\ \hline \end{array} $$$

IOI 2015

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 29 & 1.0 & 2596 & 2714.7 \\ \hline \text{Silver} & 53 & 0.53 & 2364 & 2404.2 \\ \hline \text{Bronze} & 79 & 0.34 & 2187 & 2208.7 \\ \hline \text{No Medal} & 160 & 0.53 & 1794 & 1817.7 \\ \hline \text{Total} & 321 & 0.66 & 2133 & 2162.2 \\ \hline \end{array} $$$

IOI 2016

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 26 & 1.0 & 2579 & 2643.9 \\ \hline \text{Silver} & 51 & 0.66 & 2362 & 2353.6 \\ \hline \text{Bronze} & 77 & 0.40 & 2089 & 2104.6 \\ \hline \text{No Medal} & 154 & 0.51 & 1779 & 1825.4 \\ \hline \text{Total} & 308 & 0.71 & 2103 & 2124.6 \\ \hline \end{array} $$$

IOI 2017

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 26 & 0.84 & 2609 & 2548.2 \\ \hline \text{Silver} & 50 & 0.57 & 2256 & 2293.4 \\ \hline \text{Bronze} & 76 & 0.42 & 2133 & 2129.4 \\ \hline \text{No Medal} & 152 & 0.60 & 1899 & 1889.8 \\ \hline \text{Total} & 304 & 0.73 & 2089 & 2104.1 \\ \hline \end{array} $$$

IOI 2018

$$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline \text{Gold} & 29 & 0.96 & 2459 & 2482.3 \\ \hline \text{Silver} & 55 & 0.57 & 2223 & 2220 \\ \hline \text{Bronze} & 83 & 0.35 & 2164 & 2132 \\ \hline \text{No Medal} & 168 & 0.49 & 1771 & 1782.1 \\ \hline \text{Total} & 335 & 0.65 & 2089 & 2063.1 \\ \hline \end{array} $$$

Conclusion

So, unsurprisingly, on average you can see that the function is decreasing by rank, however it fluctuates too much between close ranks. Therefore, on an individual level, you can't predict someone's future rating based on IOI ranking.

What do you think about this?

Full text and comments »

I_Love_Tina
6 years ago
9

HackerEarth January Circuits '19

By I_Love_Tina, 6 years ago, In English

Hello everyone!

I would like to invite you to participate in January Circuits '19. It's a long contest that will start on Jan 20, 9:00 PM IST (check you timezone. Contest will run for 9 days.

The problemset consists of 7 traditional algorithmic tasks of various difficulties and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

I'm the setter of the problemset and Kmcode is the tester. I would like to thank HackerEarth admin trytolearn for his help.

As usual, there will be some nice prizes for the top five competitors:

$100 Amazon gift card + HE t-shirt.
$75 Amazon gift card + HE t-shirt.
$50 Amazon gift card + HE t-shirt.
HE t-shirt.
HE t-shirt.

GL & HF.

UPD1 There is a problem which is not completely solved by the setter/tester. Let's see if somebody can kill it.

Full text and comments »

I_Love_Tina
6 years ago
2

HackerEarth January Circuits '18

By I_Love_Tina, history, 7 years ago, In English

Hello everyone!

I would like to invite you to participate in January Circuits '18. It's a long contest that will start on Jan 20, 9:00 PM IST (check you timezone). Contest will run for 9 days.

I'm the setter of the problemset and Kmcode is the tester. I would like to thank HackerEarth admin trytolearn for his help.

As usual, there will be some nice prizes for the top five competitors:

$100 Amazon gift card + HE t-shirt.
$75 Amazon gift card + HE t-shirt.
$50 Amazon gift card + HE t-shirt.
HE t-shirt.
HE t-shirt.

GL & HF.

Full text and comments »

I_Love_Tina
7 years ago
20

Codeforces Round #410 (Div. 2) Editorial

By I_Love_Tina, history, 8 years ago, In English

798A - Mike and palindrome

Let cnt be the number of $\text{[math]}$ such that s_i ≠ s_{n - i + 1}.

If cnt ≥ 2 then the answer is NO since we must change more than 1 character.

If cnt = 1 then the answer is YES.

If cnt = 0 and n is odd answer is YES since we can change the character in the middle, otherwise if n is even the answer is NO because we must change at least one character.

Complexity is O(|s|).

Solution: Link

798B - Mike and strings

First of all, you must notice that the operation of removing the first character and appending it to the left is equivalent to cyclically shifting the string one position to the left.

Let's denote by dp_i, j the smallest number of operations for making the first i strings equal to string s_i moved j times.

Let f(i, j) be the the string s_i moved j times,then $\text{[math]}$ .

The answer is min(dp_n, 0, dp_n, 1, ..., dp_{n, |s_n| - 1}).

The complexity is O(|S|³ × n).

Solution: Link

798C - Mike and gcd problem

First of all, the answer is always YES.

If $\text{[math]}$ then the answer is 0.

Now suppose that the gcd of the sequence is 1. After we perform one operation on a_i and a_i + 1, the new gcd d must satisfy d|a_i - a_i + 1 and d|a_i + a_i + 1 $\text{[math]}$ d|2a_i and d|2a_i + 1. Similarly, because d is the gcd of the new sequence, it must satisfy d|a_j, j ≠ i, i + 1.

Using the above observations we can conclude that $\text{[math]}$ , so the gcd of the sequence can become at most 2 times bigger after an operation. This means that in order to make the gcd of the sequence bigger than 1 we need to make all numbers even. Now the problem is reduced to the following problem:

Given a sequence v₁, v₂, ... , v_n of zero or one,in one move we can change numbers v_i, v_i + 1 with 2 numbers equal to $\text{[math]}$ . Find the minimal number of moves to make the whole sequence equal to 0.

It can be proved that it is optimal to solve the task for consecutive ones independently so we divide the array into the minimal number of subarrays full of ones, if their lengths are s₁, s₂, ... , s_t,the answer is $\text{[math]}$ .

Complexity is $\text{[math]}$ .

Solution: Link

798D - Mike and distribution

In the beginning, it's quite easy to notice that the condition " 2·(a_p₁ + ... + a_{p_k}) is greater than the sum of all elements in A " is equivalent to " a_p₁ + ... + a_{p_k} is greater than the sum of the remaining elements in A ".

Now, let's store an array of indices C with C_i = i and then sort it in decreasing order according to array A, that is we must have A_{C_i} ≥ A_{C_i + 1}.

Our answer will always have size $\text{[math]}$ . First suppose that N is odd. Add the first index to our set, that is make p₁ = C₁. Now, for the remaining elements, we will consider them consecutively in pairs. Suppose we are at the moment inspecting A_{C_2k} and A_{C_2k + 1}. If B_{C_2k} ≥ B_{C_2k + 1} we make p_k + 1 = C_2k, else we make p_k + 1 = C_2k + 1.

Why does this subset work? Well, it satisfies the condition for B because each time for consecutive non-intersecting pairs of elements we select the bigger one, and we also add B_C₁ to the set, so in the end the sum of the selected elements will be bigger than the sum of the remaining ones.

It also satisfies the condition for A, because A_p₁ is equal or greater than the complement element of p₂ (that is — the index which we could've selected instead of p₂ from the above procedure — if we selected C_2k then it would be C_2k + 1 and vice-versa). Similarly A_p₂ is greater than the complement of p₃ and so on. In the end we also add the last element from the last pair and this makes the sum of the chosen subset strictly bigger than the sum of the remaining elements.

The case when N is even can be done exactly the same as when N is odd, we just pick the last remaining index in the end.

The complexity is $\text{[math]}$ .

Solution: Link

798E - Mike and code of a permutation

Let's consider a_i = n + 1 instead of a_i = - 1. Let's also define the sequence b, where b_i = j such that a_j = i or b_i = n + 1 if there is no such j. Lets make a directed graph with vertices be the indices of the permutation p with edges of type (a, b) representing that p_a > p_b. If we topologically sort this graph then we can come up with a possible permutation: if S is the topologically sorted graph then we can assign to p_{S_i} number i.

In this problem we will use this implementation of topological sort.

But how we can find the edges? First of all there are edges of the form (i, b_i) if b_i ≠ n + 1 .For a vertex i he visited all the unmarked vertices j (1 ≤ j < a_i, j ≠ i) and you know for sure that for all these j, p_j < p_i. But how we can check if j was already marked? The vertex j will become marked after turn of vertex b_j or will never become unmarked if b_j = n + 1. So there is a direct edge from i to j if j = b_i or 1 ≤ j < a_i, j ≠ i and b_j > i.

Suppose we already visited a set of vertices and for every visited vertex node we assigned to b_node value 0 (for simplicity just to forget about all visited vertices) and now we want to find quickly for a fixed vertex i an unvisited vertex j with condition that there is edge (i, j) or say it there isn't such j, if we can do that in subquadratic time then the task is solved. As stated above the first condition is j = b_i if 1 ≤ b_i ≤ n, this condition is easy to check. The second condition is 1 ≤ j < a_i and b_j > i, now consider vertices with indices from interval 1..a_i - 1 and take j with maximal b_j. If b_j > i we found edge (i, j) otherwise there are no remaining edges. We can find such vertex j using segment tree and updating values while we visit a new vertex. In total we will visit n vertices and query the segment tree at most 2 × (n - 1) times (n - 1 for every new vertex and n - 1 for finding that there aren't remaining edges).

Complexity and memory are $\text{[math]}$ and O(N).

Solution: Link

Full text and comments »

Tutorial of Codeforces Round 410 (Div. 2)

I_Love_Tina
8 years ago
95

Codeforces Round #410 (Div. 2)

By I_Love_Tina, history, 8 years ago, In English

Hi everyone!

I'm pleased to announce Codeforces Round #410 (Div. 2) that will take place on Friday, 17:35 MSK. I'm the writer of the round.

I'd like to say thanks to Alex netman Vistyazh and Marcel please_delete_account Bezdrighin for feedback and help in preparing the round and to MikeMirzayanov for awesome platforms : Codeforces and Polygon.

I hope you will like the problems.

Good luck and have fun!

UPD: Scoring distribution: 500 — 1000 — 1500 — 2000 — 2500

UPD 2. The round is finished. Congratulations to winners:

Div 2:

Div 1:

Editorial: Link

Full text and comments »

Announcement of Codeforces Round 410 (Div. 2)

+240

I_Love_Tina
8 years ago
155

Codeforces Round #361 (Div. 2) Editorial

By I_Love_Tina, history, 8 years ago, In English

A.Mike and Cellphone

Author:danilka.pro.

Developed:I_Love_Tina,ThatMathGuy

We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES".

C++ code

pair < int , int > s[55][55];
int v[55][55];
pair < int , int > where[55];
int main(void)
{
    for (int i = 1;i <= 10;++i)
        for (int j = 1;j <= 10;++j)
            v[i][j] = -1;
    v[1][1] = 1;
    v[1][2] = 2;
    v[1][3] = 3;
    v[2][1] = 4;
    v[2][2] = 5;
    v[2][3] = 6;
    v[3][1] = 7;
    v[3][2] = 8;
    v[3][3] = 9;
    v[4][2] = 0;
    for (int k = 0;k <= 9;++k)
        for (int i = 1;i <= 4;++i)
            for (int j = 1;j <= 4;++j)
                if (v[i][j] == k) where[k] = {i,j};
    for (int i = 0;i <= 9;++i)
        for (int j = 0;j <= 9;++j)
            s[i][j] = {where[i].x - where[j].x,where[i].y - where[j].y};
    string number;
    int len;
    fi>>len;
    fi>>number;
    vector < string > ans;
    for (int k = 0;k <= 9;++k)
        if (k != number[0] - '0')
        {
            string cnt = "";
            cnt += k + '0';
            auto pos = where[k];
            for (int i = 0;i < len - 1;++i)
            {
                pos.x += s[number[i+1] - '0'][number[i] - '0'].x;
                pos.y += s[number[i+1] - '0'][number[i] - '0'].y;
                if (1 <= pos.x && pos.x <= 4 && 1 <= pos.y && pos.y <= 3 && v[pos.x][pos.y] != -1)
                    cnt += v[pos.x][pos.y] + '0';
                else break;
            }
            if (cnt.length() == len) 
            {
                fo << "NO\n";
                return 0;
            }
        }
    puts("YES");
    return 0;
}

Another C++ code

pair<int, int> pos[10];
int n;
char a[100]; pair<int, int> v[100];
pair<int, int> operator - (pair<int, int> a, pair<int, int> b){
    return mp(a.first - b.first, a.second - b.second);
}
pair<int, int> operator + (pair<int, int> a, pair<int, int> b){
    return mp(a.first + b.first, a.second + b.second);
}
bool inside(pair<int, int> pos){
    return (pos.first <= 3 && 1 <= pos.first && pos.second <= 3 && pos.second >= 1) || pos == (mp(4, 2));
}
int main(){
    int cnt = 0;
    FOR(x, 1, 3){
        FOR(y, 1, 3){
            cnt++;
            pos[cnt] = mp(x, y);
        }
    }
    pos[0] = mp(4, 2);
    cin >> n;
    scanf("%s", a+1);
    FOR(i, 1, n-1){
        v[i] = pos[a[i+1] - '0'] - pos[a[i] - '0'];
    }
    if(n == 1) return cout << "NO", 0;
    int c = 0;
    FOR(i, 0, 9){
        bool ok = true;
        pair<int, int> curr_pos = pos[i];
        FOR(i, 1, n-1){
            curr_pos = curr_pos + v[i];
            if(!inside(curr_pos)) ok = false;
        }
        if(ok) c++;
    }
    if(c == 1) return cout << "YES", 0;
    cout << "NO";
}

Another C++ code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
bool mark[11];
bool flag1,flag2;
 
int main()
{
    ll n;
    string s;
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
        mark[s[i]-'0']=true;
    }
    if((mark[1]||mark[2]||mark[3])&&(mark[7]||mark[9]))
        flag1=true;
    if((mark[1]||mark[4]||mark[7])&&(mark[3]||mark[6]||mark[9]))
        flag2=true;
    if((mark[1]||mark[2]||mark[3])&&mark[0]){
        cout<<"YES";
        return 0;
    }
    if(flag1&&flag2){
        cout<<"YES";
        return 0;
    }
    cout<<"NO";
return 0;
}

Python code

n = int(raw_input())
s = raw_input()
a = []
for i in range(10):
	a.append(True)
for i in range(n):
	c = int(s[i])
	a[c] = False
inc = 0
if a[1] and a[2] and a[3]:
	inc = -3
if a[7] and a[9] and a[0]:
	inc = +3
if a[1] and a[4] and a[7] and a[0]:
	inc = -1
if a[3] and a[6] and a[9] and a[0]:
	inc = +1
if inc == 0:
	print("YES")
else:
	print("NO")

B. Mike and Shortcuts

Author:danilka.pro,I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

We can build a complete graph where the cost of going from point i to point j if |i - j| if a_i! = j and 1 if a_i = j.The we can find the shortest path from point 1 to point i.One optimisation is using the fact that there is no need to go from point i to point j if j ≠ s[i],j ≠ i - 1,j ≠ i + 1 so we can add only edges (i, i + 1),(i, i - 1),(i, s[i]) with cost 1 and then run a bfs to find the shortest path for each point i.

You can also solve the problem by taking the best answer from left and from the right and because a_i ≤ a_i + 1 then we can just iterate for each i form 1 to n and get the best answer from left and maintain a deque with best answer from right.

Complexity is O(N).

C++ code with queue

int d[1 << 20];
int s[1 << 20];
queue < int > Q;
void go(int k,int val)
{
    if (d[k]) return;
    d[k] = val;
    Q.push(k);
}
int main(void)
{
    int n;
    scan(n);//scan integer
    for (int i = 1;i <= n;++i) scan(s[i]);
    go(1,1);
    while (!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        go(s[node],d[node] + 1);
        if (node > 1) go(node - 1,d[node] + 1);
        if (node < n) go(node + 1,d[node] + 1);
    }
    for (int i = 1;i <= n;++i) print(d[i] - 1);
    eol;
    return 0;
}

C++ code with deque

#include <bits/stdc++.h>
using namespace std;

const int N = int(1e6) + 5;
int n, d[N], a[N], bd[N];

int main() {
	assert(cin >> n);
	for (int i = 0; i < n; ++i) {
		assert(scanf("%d", &a[i]) == 1);
		a[i]--;
		d[i] = i;
	}
	
	for (int i = 0; i < n; ++i)
		bd[i] = int(1e9);

	deque <int> st;

	for (int i = 0; i < n; ++i) {
		if (i)
			d[i] = min(d[i], d[i - 1] + 1);

		while (!st.empty() && st.front() < i)
			st.pop_front();

		if (!st.empty())
			d[i] = min(d[i], bd[st.front()] - i);

		d[a[i]] = min(d[a[i]], d[i] + 1);
		bd[a[i]] = a[i] + d[a[i]];

		while (!st.empty() && bd[a[i]] <= bd[st.back()])
			st.pop_back();


		st.push_back(a[i]);
	}

	for (int i = 0; i < n; ++i) {
		if (i)
			putchar(' ');
		printf("%d", d[i]);
	}
	return 0;
}

Python code

import Queue
n = int(raw_input())
a = raw_input().split(' ')
used = []
d = []
for i in range(0, n):
    used.append(False)
    d.append(-1)
q = Queue.Queue()
q.put(0)
d[0] = 0
while not(q.empty()):
    v = q.get()
    for dl in range(-1, +2):
        u = v + dl
        if 0 <= u and u < n and d[u] == -1:
            d[u] = d[v] + 1
            q.put(u)
    u = int(a[v]) - 1
    if d[u] == -1:
        d[u] = d[v] + 1
        q.put(u)
for i in range(0, n):
    print(d[i])

$\text{[math]}$ What if you have Q queries Q ≤ 2 × 10⁵ of type (x_i, y_i) and you have to answer the minimal distance from x_i to y_i.

C. Mike and Chocolate Thieves

Author:danilka.pro,I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

Suppose we want to find the number of ways for a fixed n.

Let a, b, c, d ( 0 < a < b < c < d ≤ n ) be the number of chocolates the thieves stole. By our condition, they have the form b = ak, c = ak², d = ak³,where k is a positive integer. We can notice that $\text{[math]}$ , so for each k we can count how many a satisfy the conditions 0 < a < ak < ak² < ak³ ≤ n, their number is $\text{[math]}$ . Considering this, the final answer is $\text{[math]}$ .

Notice that this expression is non-decreasing as n grows, so we can run a binary search for n.

Total complexity: Time ~ $\text{[math]}$ , Space: O(1).

C++ code


ll get(ll x)
{
    ll ans = 0;
    for (int i = 2;1ll * i * i * i <= x;++i)
        ans += x / (1ll * i * i * i);
    return ans;
}
int main(void)
{
    ll m;
    fi>>m;
    ll n = 0;
    for (ll k = 1ll << 60;k;k /= 2)
        if (n + k <= 1e16 && get(n+k) < m) n += k;
    ++n;
    if (get(n) == m) fo << n << '\n';
    else fo << "-1\n";
    return 0;
}

Another C++ code


# include <bits/stdc++.h>
using namespace std;

long long get(long long n)
{
    long long ans = 0;
    for (long long i = 2; i * i * i <= n;++i)
        ans += n / (1ll*i * i * i);
    return ans;
}

int main()
{
    long long m,n=-1;
    cin>>m;
    
    long long l=0,r=5e15;
    while (l<r)
    {
        long long mid = (l+r)/2;
        if (get(mid)<m) l=mid+1;
        else r=mid;
    }
    
    if (get(l)==m) n=l;

    cout << n << '\n';
    return 0;
}

D. Friends and Subsequences

Author:I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

First of all it is easy to see that if we fix l then have $\text{[math]}$ . So we can just use binary search to find the smallest index r_min and biggest index r_max that satisfy the equality and add r_max - r_min + 1 to our answer. To find the min and max values on a segment [l, r] we can use Range-Minimum Query data structure.

The complexity is $\text{[math]}$ time and $\text{[math]}$ space.

C++ code O(N)


#include <bits/stdc++.h>
using namespace std;

int n, a[200001], b[200001];
long long ans;
deque<int> mx, mn;
int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for(int i = 1, j = 1; i <= n; i++) {
        while(!mx.empty() and a[mx.back()] <= a[i]) mx.pop_back();
        while(!mn.empty() and b[mn.back()] >= b[i]) mn.pop_back();
        mx.push_back(i);
        mn.push_back(i);
        while(j <= i and a[mx.front()] - b[mn.front()] > 0) {
            j++;
            while(!mx.empty() and mx.front() < j) mx.pop_front();
            while(!mn.empty() and mn.front() < j) mn.pop_front();
        }
        if(!mx.empty() and !mn.empty() and a[mx.front()] == b[mn.front()]) ans += min(mx.front(), mn.front()) - j + 1;
    }
    printf("%lld", ans);
}

C++ code O(N log N)


# include <bits/stdc++.h>
# define scan(x) scanf("%d",&x)
using namespace std;
# define fi cin
# define fo cout
int dx[20][1 << 20];
int dy[20][1 << 20];
int lg[1 << 20];
int mx(int l,int r)
{
    int p = lg[r - l + 1];
    return max(dx[p][l],dx[p][r - (1 << p) + 1]);
}
int mn(int l,int r)
{
    int p = lg[r - l + 1];
    return min(dy[p][l],dy[p][r - (1 << p) + 1]);
}
int main(void)
{
    int n;
    scan(n);
    for (int i = 1;i <= n;++i) scan(dx[0][i]);
    for (int i = 1;i <= n;++i) scan(dy[0][i]);
    for (int p = 1;(1 << p) <= n;++p)
        for (int i = 1;i + (1 << p) - 1 <= n;++i)
            dx[p][i] = max(dx[p-1][i],dx[p-1][i + (1 << (p-1))]),
            dy[p][i] = min(dy[p-1][i],dy[p-1][i + (1 << (p-1))]);
    for (int i = 2;i <= n;++i)
        lg[i] = lg[i >> 1] + 1;
    long long ans = 0;
    for (int i = 1;i <= n;++i)
    if (mx(i,i) <= mn(i,i))
    {
        int l = i-1,r = i;
        for (int p = 1 << lg[n - i + 1];p;p >>= 1)
            {
                if (p + l <= n && mx(i,l+p) < mn(i,l+p)) l += p;
                if (p + r <= n && mx(i,r+p) <= mn(i,r+p)) r += p;
            }
        ans += r - l;
    }
    fo << ans << '\n';
}

C++ code O(N log ^ 2 N)


int a[1 << 20];
int b[1 << 20];
int Sa[1 << 20];
int Sb[1 << 20];
int n;
int lg[1 << 20];
void updA(int i,int val)
{
    for (;i <= n;i += i&(-i)) Sa[i] = max(Sa[i],val);
}
int quA(int i)
{
    int ans = -(1e9+1);
    for (;i;i -= i&(-i)) ans = max(ans,Sa[i]);
    return ans;
}
void updB(int i,int val)
{
    for (;i <= n;i += i&(-i)) Sb[i] = min(Sb[i],val);
}
int quB(int i)
{
    int ans = (1e9+1);
    for (;i;i -= i&(-i)) ans = min(ans,Sb[i]);
    return ans;
}
int mx(int T)
{
    return quA(T);
}
int mn(int T)
{
    return quB(T);
}
int main(void)
{
    for (int i = 2;i <= 1e6;++i) lg[i] = lg[i/2] + 1;
    scan(n);
    for (int i = 1;i <= n;++i) scan(a[i]),Sa[i] =-(1e9+1);
    for (int i = 1;i <= n;++i) scan(b[i]),Sb[i] = (1e9+1);
    ll ans = 0;
    for (int i = n;i;--i)
    {
        updA(i,a[i]);
        updB(i,b[i]);
        if (mx(i) > mn(i)) continue;
        int l = i-1,r = i;
        for (int p = 1 << lg[n - i + 1];p;p >>= 1)
            {
                if (p + l <= n && mx(l+p) < mn(l+p)) l += p;
                if (p + r <= n && mx(r+p) <= mn(r+p)) r += p;
            }
        ans += r - l;
    }
    fo << ans << '\n';
    return 0;
}

Another C++ code


#include <bits/stdc++.h>
using namespace std;

const int N = int(1e6) + 5;
int a[N], b[N], n;
int lfa[N], rga[N], lfb[N], rgb[N], nxt[N];

void calc_max(int *a, int *lf, int *rg) {
	stack <int> st;
	a[n] = int(1e9) + 1;

	for (int i = 0; i <= n; ++i) {
		while (!st.empty() && a[st.top()] < a[i]) {
			rg[st.top()] = i;
			st.pop();
		}

		lf[i] = st.empty() ? -1 : st.top();
		st.push(i);
	}
}

int naive() {
	int res = 0;
	for (int i = 0; i < n; ++i)
		for (int j = i; j < n; ++j)
			if (*max_element(a + i, a + j + 1) == *min_element(b + i, b + j + 1))
				res++;
	return res;
}

bool read() {

	if (!(cin >> n))
		return false;

	for (int i = 0; i < n; ++i)
		assert(scanf("%d", &a[i]) == 1);
	for (int i = 0; i < n; ++i)
		assert(scanf("%d", &b[i]) == 1);
}

void solve() {
	calc_max(a, lfa, rga);

	for (int i = 0; i < n; ++i)
		b[i] = -b[i];
	calc_max(b, lfb, rgb);

	map <int, int> pos, last;

	for (int i = 0; i < n; ++i) {
		b[i] = -b[i];
		nxt[i] = n;

		if (!pos.count(b[i]))
			pos[b[i]] = i;
		else
			nxt[last[b[i]]] = i;
		last[b[i]] = i;
	}

	long long res = 0;
	
	for (int i = 0; i < n; ++i) {
		if (!pos.count(a[i]))
			continue;

		int pb = pos[a[i]];

		while (nxt[pb] <= i) {
			pb = nxt[pb];
			if (lfb[pb] != -1 && b[lfb[pb]] == b[pb])
				lfb[pb] = lfb[lfb[pb]];
		}
		pos[a[i]] = pb;

		for (int t = 0; t < 2 && pb < n; ++t, pb = nxt[pb]) {
			int lf = max(lfa[i], lfb[pb]);
			int rg = min(rga[i], rgb[pb]);

			if (lf < min(i, pb) && max(i, pb) < rg)
				res += (min(i, pb) - lf) * 1ll * (rg - max(i, pb));
		}
	}

	cout << res << endl;
}

int main() {
	while (read())
		solve();
	return 0;
}

$\text{[math]}$ What if you need to count (l₁, r₁, l₂, r₂), 1 ≤ l₁ ≤ r₁ ≤ n, 1 ≤ l₂ ≤ r₂ ≤ n and $\text{[math]}$ .

Hint:Take idea from this problem.

C++ code for Bonus


const int mod = 1e9 + 7;
int a[1 << 20];
int b[1 << 20];
int st[1 << 20];
int dr[1 << 20];
map < int , ll > A,B;
int main(void)
{
    int n;
    IOS;
    fi>>n;
    for (int i = 1;i <= n;++i) fi>>a[i];
    for (int i = 1;i <= n;++i) fi>>b[i];
    deque < int > d;
    for (int i = 1;i <= n;++i)
    {
        while (!d.empty() && a[d.back()] < a[i]) d.pop_back();
        if (d.empty()) st[i] = 0;
        else st[i] = d.back();
        d.push_back(i);
    }
    d.clear();
    for (int i = n;i;--i)
    {
        while (!d.empty() && a[d.back()] <= a[i]) d.pop_back();
        if (d.empty()) dr[i] = n+1;
        else dr[i] = d.back();
        d.push_back(i);
    }
    for (int i = 1;i <= n;++i)
        A[a[i]] += 1ll * (i - st[i]) * (dr[i] - i);
    while (!d.empty()) d.pop_back();
    for (int i = 1;i <= n;++i)
    {
        while (!d.empty() && b[d.back()] > b[i]) d.pop_back();
        if (d.empty()) st[i] = 0;
        else st[i] = d.back();
        d.push_back(i);
    }
    d.clear();
    for (int i = n;i;--i)
    {
        while (!d.empty() && b[d.back()] >= b[i]) d.pop_back();
        if (d.empty()) dr[i] = n+1;
        else dr[i] = d.back();
        d.push_back(i);
    }
    for (int i = 1;i <= n;++i)
        B[b[i]] += 1ll * (i - st[i]) * (dr[i] - i);
    for (auto &it : A) it.y %= mod;
    for (auto &it : B) it.y %= mod;
    int ans = 0;
    for (auto it : A)
        ans = (ans + 1ll * it.y * B[it.x]) % mod;
    fo << ans << '\n';
    return 0;
}

E. Mike and Geometry Problem

Author:I_Love_Tina

Developed:I_Love_Tina,ThatMathGuy

Let define the following propriety:if the point i is intersected by p segments then in our sum it will be counted $\text{[math]}$ times,so our task reduce to calculate how many points is intersected by i intervals 1 ≤ i ≤ n.Let dp[i] be the number of points intersected by i intervals.Then our answer will be $\text{[math]}$ . We can easily calculate array dp using a map and partial sum trick,here you can find about it.

The complexity and memory is $\text{[math]}$ and O(n).

C++ code


# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
const int nmax = 2e5 + 5;
const int mod = 1e9 + 7;
int pow(int a,int b,int mod)
{
    int ans = 1;
    while (b)
    {
        if (b&1) ans = (1ll * ans * a) % mod;
        a = (1ll * a * a) % mod;
        b /= 2;
    }
    return ans;
}
int f[nmax];//factorial
int c[nmax];//inverse of factorial
map < int , int > s;
int C(int n,int k) // combination
{
    int ans = (1ll * f[n] * c[k]) % mod;
    return (1ll * ans * c[n - k]) % mod;
}
main(void)
{
    int n,k;
    int ans = 0;
    ios_base :: sync_with_stdio(0);
    fi>>n>>k;assert(1 <= k && k <= n && n <= 2e5);
    f[0] = c[0] = 1;
    for (int i = 1;i <= n;++i) f[i] = (1ll * f[i-1] * i) % mod,c[i] = pow(f[i],mod-2,mod);
    for (int i = 1;i <= n;++i)
    {
        int a,b;
        fi>>a>>b;
        assert(-1e9 <= a && a <= b && b <= 1e9);
        ++s[a];--s[b+1];
    }
    int l = s.begin()->x;
    int sum = 0;
    for (auto it : s)
    {
        int dist = it.x - l;
        if (sum >= k) ans += (1ll * C(sum,k) * dist) % mod;
        ans = (ans >= mod ? ans - mod : ans);
        sum += it.y;
        l = it.x;
    }
    return fo << ans << '\n',0;
}

Another C++ solution

#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

const int mod = 1e9+7;

ll pp(ll x, int y)
{
	if (!y) return 1;
	ll t = pp(x,y/2);
	t = 1ll*t*t;
	t%=mod;
	if (y%2) t*=1ll*x;
	t%=mod;
	return t;
}

int n,k;

struct s
{
	int x;
	int y;
};

s a[2*200000];

ll c[200001];

void gen()
{
	ll b = 1;
	
	c[k] = 1;
	for (int i=k+1; i<=n; i++)
		b*=	i,b%=mod,b*=pp(i-k,mod-2),b%=mod,c[i]=b;
}


ll ans = 0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

	cin>>n>>k;
	
	gen();
	
	for (int i=0; i<n; i++)
		cin>>a[2*i].x>>a[2*i+1].x,a[2*i].y = 1,a[2*i+1].y=-1,a[2*i+1].x++;
		
	sort(a,a+2*n, [] (s x, s y) { if (x.x!=y.x) return (x.x<y.x); return (x.y>y.y);});
	
	int last = a[0].x;
	int now = 0;
	
	for (int i=0; i<2*n;)
	{
		int d = a[i].x;
		ans += 1ll * c[now] * (d-last);
		ans%=mod;
		while (a[i].x==d)
			now+=a[i].y,i++;
		last = d;
	}
	
	cout<<ans;
		
    return 0;
}

$\text{[math]}$ what if $\text{[math]}$ where l, r are given in input.

I'm really sorry that problem A was harder than ussually.

Full text and comments »

Tutorial of Codeforces Round 361 (Div. 2)

+113

I_Love_Tina
8 years ago
132

Codeforces Round #361 (Div. 2)

By I_Love_Tina, history, 8 years ago, In English

Hi everyone!

I want to present you the Codeforces Round #361 (Div. 2) that will take place on the 6th of July at 19:35 MSK. The contest was prepared by Gabriel I_Love_Tina Cojocaru and Mihail ThatMathGuy Tarigradschi.

I'd like to thank Dan danilka.pro Sagunov and Gleb GlebsHP Evstropov for their help in preparing the round and for making the round possible,Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

Good luck in the contest!!

UPD1.In this round you will help our hero Mike solve tasks he encounters every day.

UPD2. Editorial

UPD3.Congratulations to the winners of the round.

Div 1:

1.Um_nik

2.cgy4ever

3.anta

4.HellKitsune

5.ksun48

6.waterfall

7.Kaban-5