Educational Codeforces Round 64 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	int sum = 0;
	int lst = 1;
	vector<int> figs;
	forn(i, n){
		int x;
		scanf("%d", &x);
		if (lst != 1 && x != 1){
			puts("Infinite");
			return 0;
		}
		if (x != 1){
			figs.push_back(x);
			sum += x + 1;
			if (i != 0 && i != n - 1)
				sum += x + 1;
		}
		lst = x;
	}
	forn(i, int(figs.size()) - 1) if (figs[i] == 3 && figs[i + 1] == 2)
		--sum;
	printf("Finite\n%d\n", sum);
}

1156B - Ugly Pairs

Tutorial

Solution (PikMike)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

bool check(string s){
	bool ok = true;
	forn(i, int(s.size()) - 1)
		ok &= (abs(s[i] - s[i + 1]) != 1);
	return ok;
}

int main() {
	int T;
	scanf("%d", &T);
	static char buf[120];
	forn(_, T){
		scanf("%s", buf);
		string s = buf;
		string odd = "", even = "";
		forn(i, s.size()){
			if (s[i] % 2 == 0)
				odd += s[i];
			else
				even += s[i];
		}
		sort(odd.begin(), odd.end());
		sort(even.begin(), even.end());
		if (check(odd + even))
			printf("%s\n", (odd + even).c_str());
		else if (check(even + odd))
			printf("%s\n", (even + odd).c_str());
		else
			puts("No answer");
	}
	return 0;
}

1156C - Match Points

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int n, z;
int a[N];

int main()
{
	scanf("%d", &n);
	scanf("%d", &z);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int l = 0;
	int r = n / 2 + 1;
	while(r - l > 1)
	{
		int m = (l + r) / 2;
		bool good = true;
		for(int i = 0; i < m; i++)
			good &= (a[n - m + i] - a[i] >= z);
		if(good)
			l = m;
		else
			r = m;
	}
	cout << l << endl;
}

1156D - 0-1-Tree

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int p[2][N];
int siz[2][N];

int get(int x, int c)
{
	if(p[c][x] == x)
		return x;
	return p[c][x] = get(p[c][x], c);
}

void merge(int x, int y, int c)
{
	x = get(x, c);
	y = get(y, c);
	if(siz[c][x] < siz[c][y])
		swap(x, y);
	p[c][y] = x;
	siz[c][x] += siz[c][y];
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		p[0][i] = p[1][i] = i;
		siz[0][i] = siz[1][i] = 1;
	}
	for(int i = 0; i < n - 1; i++)
	{
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		--x;
		--y;
		merge(x, y, c);
	}
	long long ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(p[0][i] == i)
			ans += siz[0][i] * 1ll * (siz[0][i] - 1);
		if(p[1][i] == i)
			ans += siz[1][i] * 1ll * (siz[1][i] - 1);
		ans += (siz[0][get(i, 0)] - 1) * 1ll * (siz[1][get(i, 1)] - 1);
	}
	cout << ans << endl;
}

1156E - Special Segments of Permutation

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 200043;

int lf[N];
int rg[N];
int n;
int ans = 0;
int p[N];
int q[N];

void update(int l, int r, int l2, int r2, int sum)
{
	for(int i = l; i <= r; i++)
	{
		int o = sum - p[i];
		if(o >= 1 && o <= n && l2 <= q[o] && q[o] <= r2)
			ans++;
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &p[i]);
		q[p[i]] = i;
	}
	stack<pair<int, int> > s;
	s.push(make_pair(n + 1, -1));
	for(int i = 0; i < n; i++)
	{
		while(s.top().first < p[i])
			s.pop();
		lf[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	while(!s.empty())
		s.pop();
	s.push(make_pair(n + 1, n));
	for(int i = n - 1; i >= 0; i--)
	{
		while(s.top().first < p[i])
			s.pop();
		rg[i] = s.top().second;
		s.push(make_pair(p[i], i));
	}
	for(int i = 0; i < n; i++)
	{
	//	cerr << i << " " << lf[i] << " " << rg[i] << endl;
		int lenl = i - lf[i] - 1;
		int lenr = rg[i] - i - 1;
		if(lenl == 0 || lenr == 0)
			continue;
		if(lenl < lenr)
			update(lf[i] + 1, i - 1, i + 1, rg[i] - 1, p[i]);
		else
			update(i + 1, rg[i] - 1, lf[i] + 1, i - 1, p[i]);
	}
	cout << ans << endl;
}

1156F - Card Bag

Tutorial

Solution (Roms)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5005;

void upd(int &a, int b){
    a += b;
    a %= MOD;
}

int mul(int a, int b){
    return (a * 1LL * b) % MOD;
}

int bp(int a, int n){
    int res = 1;
    for(; n > 0; n >>= 1){
        if(n & 1) res = mul(res, a);
        a = mul(a, a);
    }
    return res;
}

int getInv(int a){
    int ia = bp(a, MOD - 2);
    assert(mul(a, ia) == 1);
    return ia;
}

int n;
int cnt[N];
int suf[N];
int dp[N][N];
int sum[N][N];
int inv[N];

int main(){
    for(int i = 1; i < N; ++i)
        inv[i] = getInv(i);
        
    cin >> n;
    for(int i = 0; i < n; ++i){
        int x;
        cin >> x;
        ++cnt[x];
    }
    cnt[0] = 1;
    for(int i = N - 2; i >= 0; --i)
        suf[i] = suf[i + 1] + cnt[i];
        
    for(int x = n; x >= 0; --x)
        for(int y = n; y >= 0; --y){
            if(cnt[x] == 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            int s = n - y;
            if(s <= 0){
                upd(sum[x][y], sum[x + 1][y]);
                continue;
            }
            
            upd(dp[x][y], mul(cnt[x] - 1, inv[s]));
            upd(dp[x][y], mul(sum[x + 1][y + 1], inv[s]));
            
            upd(sum[x][y], sum[x + 1][y]);
            upd(sum[x][y], mul(cnt[x], dp[x][y]));
        }
    
    cout << dp[0][0] << endl;
	return 0;
}

1156G - Optimizer

Tutorial

Solution (e-maxx)

Solution described in a tutorial.

Jury's solution:

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;


struct expr {
	string t; // variable name or operation
	expr * l, * r; // only if operation
	long long hash;
	
	expr (string var)
		: t(var), l(0), r(0), hash(0)
		{ }
	expr (char op, expr * l, expr * r)
		: t(1,op), l(l), r(r), hash(0)
		{ }

	long long calc_hash() {
		if (!hash)
			if (!l) {
				long long pw = 257;
				for (size_t i=0; i<t.length(); ++i,  pw*=97)
					hash += t[i] * pw;
			}
			else
				hash += l->calc_hash() * t[0] + r->calc_hash() * 31;
		return hash;
	}
};

map<string,expr*> var;

void inc_var_name (string & cur) {
	for (size_t i=cur.length()-1; ; --i)
		if (cur[i] < 'z') {
			++cur[i];
			break;
		}
		else
			cur[i] = 'a';
}

string generate_var() {
	static string cur = "aaaa";
	while (var.count(cur))
		inc_var_name (cur);
	string res = cur;
	inc_var_name (cur);
	return res;
}

vector<string> ans;
map<long long,string> calced;

string restore (expr * e, string name = "") {
	if (!e->l)  return e->t;
	long long h = e->calc_hash();
	if (calced.count(h))  return calced[h];
	string l = restore (e->l),  r = restore (e->r);
	string my = name.empty() ? generate_var() : name;
	calced[h] = my;
	ans.push_back (my + "=" + l + e->t + r);
	return my;
}

int main() {
	int n;
	scanf ("%d\n", &n);
	for (int i=0; i<n; ++i) {
		static char buf[100];
		gets (buf);
		string s = buf;

		size_t pos1 = s.find ('='),  pos2 = s.find_first_of ("&^$#");
		string lname = s.substr (0, pos1);
		string r1name = s.substr (pos1 + 1, pos2 - pos1 - 1);
		if (!var.count(r1name))
			var[r1name] = new expr (r1name);
		if (pos2 != -1) {
			string r2name = s.substr (pos2 + 1);
			if (!var.count(r2name))
				var[r2name] = new expr (r2name);
			var[lname] = new expr (s [ s.find_first_of ("&^$#") ], var[r1name], var[r2name]);
		}
		else
			var[lname] = var[r1name];
	}

	if (!var.count("res")) {
		cout << 0;
		return 0;
	}

	string name = restore (var["res"], "res");
	if (name != "res")
		ans.push_back ("res=" + name);

	cout << ans.size() << endl;
	for (size_t i=0; i<ans.size(); ++i)
		puts (ans[i].c_str());

}

Comments (69)

Show archived | Write comment?

hacker_de_sentimente

6 years ago, # |

← Rev. 2 →

In problem B tutorial, it should be "odd positions in alphabet ("aceg…") and even positions in alphabet ("bdfh…")", instead of "odd positions in alphabet ("acef…") and even positions in alphabet ("bdgi…")"

→ Reply

awoo

6 years ago, # ^ |

Whoops, one sec.

YahiaAglan74

+43

wonderful tutorial thank you awoo, we appreciate your effort

pepelats

Problem C. Why does my java code fail? https://mirror.codeforces.com/contest/1156/submission/53668587

wjli

Your "i" never got incremented if there is no match.

Ok, but this one works https://mirror.codeforces.com/contest/1156/submission/53671611

There is time limit exception. Apparently there is endless loop somewhere.

step_by_step

Arrays.sort(a) works in $$$O(n^2)$$$ in the worst case. Somebody created an anti-sort test.

Thanks. I got you.

BrutBurger

I love the solution for E, great task ^^

shahidul_brur

In B, complexity is not O(n), it is O(n log n) for sorting.

gratus907

Solution on the editorial is $$$\mathcal{O}(n \log n)$$$, but since we are only sorting alphabets we can use counting sort to fit the solution in $$$\mathcal{O}(n)$$$. Of course it would be better to write the correct complexity on the editorial, since this optimization is not very needed in this problem :)

Yes, I know that it is possible to achieve $$$O(n)$$$ by using counting sort. I also told about the solution in editorial.

pk842

can someone please explain the proof of the problem C a little bit more? I didn't get it from the editorial.

hackslash_123

It's easy to check if m pairs can be formed from the array or not in O(n) time. So you perform binary search on the answer(no. of pairs to be formed) which is done O(nlogn) time.

If i am not wrong then again checking for that will require the same proof anyways?

saint_coder

← Rev. 6 →

+11

Suppose let's say for k=4, that means we assume that we can make at least 4 pairs. then we can make pairs in the following manner:

I have marked the leftmost points as 1,2,3 and 4. They have been paired with points at the end of dotted path.

We have to prove that the minimum distance in a pair is maximized.

Suppose if the point 4 is being paired with any other point other than the right most it will minimize its distance. Similarly for 3rd we then choose the best available points. Similar for 2nd and 1st.

If any other 4 pairs are possible then it is always possible to change them into these pairs by swapping(see editorial). But if even these pairs are not possible then we cannot make 4 pairs.

Sorry for poor drawing :P

zarif_2002

let's imagine k is the answer. so, there are k pairs. so, what do you think? We would pair 1st one of left with 1st one of right. then, 2nd one of left with 2nd one of right and so on. now, suppose this algo fails. let's say in m-th item it fails, so, you paired m-th of left with the (m + 1)-th of right. now, in right side, you have only k — m — 1 elements. m-th of right cannot pair with the remaining ones of left and it's trivial to find out why. so, the pairs you can get is maximum of m + (k — m — 1) = k — 1 which is not true since we imagined k is the answer. so, this algo doesn't fail(proof by contradiction).

dqa2021

+10

Problem E

In fact this problem can be solved using Divide and Conquer. :)

Let's consider all the subsegments $$$[l',r']$$$ whose left bound $$$l'$$$ is in $$$[l,mid]$$$ and whose right bound $$$r'$$$ is in $$$(mid,r]$$$ ($$$l,r$$$ and $$$mid$$$ are known in this part of the Divide and Conquer) . When $$$l'$$$ moves from $$$mid$$$ down to $$$l$$$, we can know the rightest pos satisfying $$$\max_{i=mid+1}^{pos}p_i<\max_{i=l'}^{mid}p_i$$$ (it is certain that they cannot be equal) using a pointer $$$rpos$$$. And we are now looking for those $$$r'$$$s. When $$$mid<r'\leq rpos$$$, the maximum value is in $$$[l',mid]$$$. Now $$$l'$$$ and the maximum value (let's call it $$$maxn$$$) are fixed, so we check if the $$$j$$$ whose $$$p_j$$$ is $$$maxn-p_{l'}$$$ is in the range of $$$(mid,rpos]$$$ and update the answer. When $$$rpos<r'\leq r$$$, the maximum value is in $$$(mid,r']$$$. Let's solve this part of the problem offline. When we enumerate $$$i$$$ from $$$r$$$ down to $$$mid+1$$$, we put $$$maxn-p_i$$$ (where $$$maxn=\max_{j=mid+1}^i p_j$$$, which can be got very quickly) into a bin and for an $$$l'$$$ whose $$$rmax+1$$$ is just $$$i$$$ we calculate how many times we put the value of $$$w_{l'}$$$ into the bin.

The time complexity is $$$O(n\log n)$$$.

Code: 53674474

ZeyadKhattab

I don't quite get why the mentioned solution for problem E is O(n(log(n)). Can someone explain more ?

cr8

I don't have the proof but i run a dp to see the worst case
https://pastebin.com/6ZmH8uEX pd. it's slow but it will work in a couple of minutes

hemanthvhr_arg

As given in the tutorial, we will first find the left and right boundaries of each element upto which it is the maximum element and for finding the solution for segments with size $$$m$$$, will iterate through the half which has fewer elements i.e. $$$< m/2$$$ elements in it.

Given all this, consider the segments with max element $$$n$$$ present some where in the array, and divides it into two parts of size $$$m_{1}, m_{2}$$$ such that $$$m_{1}+m_{2} = n-1$$$, so here iterate through $$$min(m_{1}, m_{2}) \lt (m/2) = O(n)$$$ elements.

Now consider the segments with max value = max value in $$$m_{1}$$$-segment & $$$m_{2}$$$-segment. Lets say the array is now partitioned into segments of size $$$m_{3}, m_{4}, m_{5}, m_{6}$$$, with $$$m_{3}+m_{4} = m_{1}-1$$$ and $$$m_{5}+m_{6} = m_{2}-1$$$, now the number of elements to be iterated in total of the the $$$2$$$ selected maximum elements is $$$< (m_{1}/2) + (m_{2}/2) = O(n)$$$ and so on for next $$$4$$$ max elements is $$$< (m_{3}/2)+(m_{4}/2)+(m_{5}/2)+(m_{6}/2) = O(n)$$$, so on for next $$$8$$$ max elements, $$$16$$$ max elements, .... So to check for all the elements $$$O(n) * (log(n)+1) = O(n(log(n))$$$.

I got it now. Thank you!

golions

here is my solution for D that uses DP on Trees. The implementation is extremely simple, but the transitions are more complex to come up with. 53644201

agarus

To make it easier for those who would attempt this riddle: sub[node][0/1] — is an array that counts how many paths can be made by 1-edges and 0-edges when going from leaves to the root. dp[node][0/1] — is an array that counts how many paths are there to the current node, from the root (by subtracting number of paths going up from those going down() ) plus number of paths from the leaves(from first array — "sub"). Pretty smart.

Rodp63

+12

I think problem C doesn't need a binary search. A single loop solves the task. Look at my submission 53648314

Please explain your solution, it looks amazing!

+20

At most we can find $$$n/2$$$ pairs of points. So, first we have to sort the array and start to iterate from the middle of the array to the beginning. Also we need a pointer to the last element. If the current point match with the last point, increment the answer by 1 and decrement the pointer of the last element. :) That works because the way we choose the points is optimized.

ffbh

Good solution

Windsky_M

← Rev. 3 →

could anyone help me to understand "if(siz[w][x] < siz[w][y]) swap(x, y);" what mean this code ?

i found that just like Union Find's rank unite, when i delete this code , i got ac too(even faster).

But if i delete this code, i think it will change the size of siz[0][i] or siz[1][i], maybe when i calculate the root "if(par[0][i] == i) ans += (siz[0][i] — 1) * 1LL * siz[0][i];"

and got wrong answer.

I think this code maybe reduce time of path compress sometimes , but it also takes time to run this code

This means that when merging two trees in union-find BledDest merges smaller tree to bigger one. To balance resulting tree, so the "find" operation wouldn't become O(n) in worst case, and solution wouldn't become O(n^2).

sidgooner

In B why do we have to check whole list cant we check only at junction of odd and even array?

Certainly ， it works

zyaad

After sorting the string, I used a greedy approach, together with a stack and a double ended queue to construct the final string.

The idea:

If a character cannot be appended at either end of the deque, it is pushed on the stack.
Before and after consuming s[i], the stack is checked to see if any character can be added at either end.
If any character remains on the stack at the end, then there is no solution.

Here is my submission 53699191

opooopooo

Problem E,you can use Sparse-Table and Union-Find. https://codeforc.es/contest/1156/submission/53700970

mohamedeltair

+14

Two things need to be proved are missing in C's editorial:

Q1) For a fixed $$$k$$$, why does matching the $$$ith$$$ element from the first $$$k$$$ elements with the $$$ith$$$ element from the last $$$k$$$ elements maximize the minimum distance across all pairs?

A1) Consider the two pairs $$$(L1, R1)$$$ and $$$(L2, R2)$$$, where $$$L2>=L1$$$ and $$$R2 \leq R1$$$. The minimum distance here is $$$R2-L2$$$. We can swap $$$R1$$$ and $$$R2$$$ producing the pairs $$$(L1, R2)$$$ and $$$(L2, R1)$$$. Where $$$R1-L2 \geq R2-L2$$$ and $$$R2-L1 \geq R2-L2$$$. So the minimum distance now is $$$>=$$$ the previous minimum distance. This implies that for any two pairs, the pair with less $$$L$$$ should have the less $$$R$$$. In other words, the $$$ith$$$ elements of the first and last $$$k$$$ elements should be matched.

Q2) Why does binary search work for this problem?

A2) After sorting the array $$$arr$$$, denote $$$least[i]$$$ to be $$$j-i$$$ where $$$j$$$ is the least index such that $$$arr[j]-arr[i] \geq z$$$, or $$$+\infty$$$ if no such $$$j$$$ exists. For a valid $$$k$$$, $$$max_{i=1}^{i=k}\ least[i] \leq n-k$$$ (Assuming $$$1$$$-based indexing). If the previous inequality doesn't hold, we won't be able to match some $$$ith$$$ elements of the first and last $$$k$$$ elements. Denote $$$k\_inv$$$ to be the least invalid $$$k$$$, $$$max_{i=1}^{i=k\_inv}\ least[i]>n-k\_inv$$$. So any $$$k'$$$ where $$$k'>k\_inv$$$ will be invalid also, because $$$max_{i=1}^{i=k'}\ least[i] \geq max_{i=1}^{i=k\_inv}\ least[i]$$$ and $$$n-k'<n-k\_inv$$$.

Febrin

[Problem B]

I am thinking about pretty straight forward, yet quite interesting solution to this problem. It is random shuffling till we get good arrangement or terminating and saying "No answer" after 1000 iterations.

I reckon that many people did it this way. Wonder if it is 100% correct and provable.

Solution: 53719836

dalt

Another solution for problem E. First, you need to build a tree representing the whole permutation. Choose the largest element n as the root of tree, then elements on the left side of n in the permutation form the left subtree of root, elements on the right side of n in the permutation form the right subtree of root.

The question is about how many pairs of (u, v) for each node x, where u locates in the left subtree of x and v locates in the right subtree of x.

After building the tree, do dsu on the tree. The total time complexity is O(nlogn).

VLADO

Can you explain what you mean by "do dsu on the tree"? I know what DSU is.

see this blog

Thank you.

In problem E. Why did solutions like these https://mirror.codeforces.com/contest/1156/submission/53741778 pass on time? For example test is [1, n, 2, n-1, 3, n-2, ...]

ngvan1612

I can't understand: "we should match the leftmost L-point with the leftmost R-point, the second L-point with the second R-point, and so on, in order to maximize the minimum distance in a pair". Can someone explain me with?

Muhimin_Osim

Can anyone please explain these words with some examples? I haven't a clear idea about that.

pms_venkatesh_saki_147

nice problems

Kartik_715

Can anyone help me with problem C ! I've used two pointers to make pairs Here is my submission

Edit: Sorry i figured the problem!

can you please share the idea of your two pointer solution, I only found out just a binary search solution with a greedy approach.

Yeah sure! I just sorted the array first! Then set my leftPtr to start of array and rightPtr to the mid of array At start of loop i make sure that the numbers at which leftPtr and rightPtr point at have difference greater than z! If i reach the end of array! I break the loop! You can see my submission!

I have got another idea to solve seeing your short tutorial. queue based solution. two queue. q1 and q2. pushing and popping would be done such that q2.front() — q1.front() >= z. when, we would push an element in q2. we would increament answer.

I don’t think i get the idea fully! Did you make a submission related to your idea? Maybe I’ll look into source code and see what you’re talking about?

i would do it later. i am on gaming yeah.

I think I have got a simple explanation of D. No dsu, no dp, just simple bfs + combinatorics. Here we go. 1. split the tree into two graphs, one containing only 0-edges and other containing only 1-edges. 2. count the number of nodes in each components for both graphs. 3. to find the number of only 0-containing paths and 1-containing paths, we can just count the paths inside all components(a path belonging to only a single component). 3. let's assume 1, 3, 4, 20 lies in a component. now, for this component, valid path is 20. let's face it. for a valid path, we need to pick two nodes and then we need to do permutation of two nodes. picking two nodes take p*(p — 1)/2 ways and ways of permutation of two nodes is only two. so, the number of valid paths is p*(p — 1)[p is the number of nodes in a component]. also, in a component, the number of ways you can go to a node belonging to a component is (p — 1).(going to node from all other p — 1 nodes of the component.) 4. thus, we can count only the answers that belongs to only a component of a graph. that is only 0-containing paths and 1-containing paths. 5. now, we have to face the paths that contains 0-edges at first and then 1-edges later. to do this let's define a vertex v. for paths going through v, we have to come into v through 0-edges and go out of v through 1-edges. as, we have found the number of ways to go into v in a 0-containing component and a 1-containing component, we can easily do this work just using multiplication law of permutation.

finally, here is the code(if needs). https://mirror.codeforces.com/contest/1156/submission/54551825

Ohh... I solved a 2300 ranked problem! without seeing tutorial! how? how?

caa_tomsk

5 years ago, # |

Better late than never. Problem E was really nice!

Jhin

5 years ago, # ^ |

can you explain the statement I didn't understand this part pl+pr=maxi=lrpi.
what does pl+pr means :/

Mohinem

For 1156C, why doesn't the greedy solution work. Like matching a point with another point on its right which is nearest to it, provided the distance is greater than or equal to z ?

scameeer

4 years ago, # ^ |

Consider the test case:

4 3

7 15 50 51

ritesh1340

Thanks for the test case, it helped me too : )

SugA

Can someone tell me what is wrong with my solution for D. I used dp on trees to find the no.of invalid pairs and remove it from the total no. of possible pairs ( i.e n*(n-1) ).
Please find my submission here.

Mooncrater

How to do Div2C using DP?

SPyofgame

Thank you problem setters, who made this contest for us. And thanks for the tutorial ^^

abj

4 years ago, # |

https://mirror.codeforces.com/contest/1156/submission/81658673 Div2C.Its showing error in test 7. Someone pls explain.

u33how

For problem 1156B - Ugly Pairs, I used kind of an ad-hoc case-by-case solution.

Let, n = number of different characters in string s.

If n is odd and greater than 3, then there is always an answer. The answer is constructed like this. eg: abcdefg ==> ce, bf, ag, d. (Notice the pattern)
If n is even and greater than 2, then there is always an answer. The answer is constructed like this. eg: abcdef ==> cf, be, ad (Notice the pattern)
If n is 2, then just have to check whether those 2 are neighbors or not.
And if n is 3 and all 3 are consecutive, then there is no answer. Else, the answer is always possible.

Solution: 86424440

towrist

Problem D can be solved by simple re-rooting. 87430433

akashtadwai

Can someone help why the multiset approach for the problem 1156C - Match Points is not working??

Code

int n, d;
  cin >> n >> d;
  multiset<int> s;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    s.insert(a);
  }
  int ans = 0;
  while (s.size() >= 2) {
    int left = *s.begin();
    auto it = s.lower_bound(left + d);
    if (it == s.end())
      break;
    ++ans;
    s.erase(s.begin());
    s.erase(it);
  }
  cout << ans << endl;

BeruboIV

You are using a Greedy Approach for this problem which is wrong.

Try this test case:

4 4

1 5 6 9

SarthakBansal

I feel the editorial to Problem C is very unclear. I still don't get what is meant by "swap" them. Swap whom ? L? R? the one behind L ? idk.

Here's my attempt for an editorial.

Test case

It is clear to use Binary search. If we can make 'mid' pairs, we can surely make 'mid-1' pairs, we may/may not be to make 'mid+1' pairs.
Therefore, l (Minimum Pairs Possible) =0 and r (Maximum Pairs Possible)=n/2.
So applying binary search , mid=(l+r)/2. Now the main tricky part is to check whether we can form mid pairs or not ?
For an array [a1 , a2 ... an], what is the best/surest way to make 'mid' pairs?
It is to take {a[1],a[n-mid]} , {a[2],a[n-mid+1]} .... {a[mid],a[n]}. But why? Simply because these would have the maximum possible diference.

93012535

adderall

Can there be any possible solution to solve F that use expected value like expected value of remaining elements when iterating to the ith element ?

mukul166

Can anyone tell me in Card Bag problem (F) for the test case 4 1 3 4 3 how the answer is 1/4? awoo

awoo's blog