Educational Codeforces Round 96 — Editorial

#	User	Rating
1	tourist	3565
2	Benq	3540
3	Petr	3519
4	maroonrk	3503
5	jiangly	3391
6	ecnerwala	3363
7	Radewoosh	3349
8	scott_wu	3313
9	ainta	3298
10	boboniu	3289

#	User	Contrib.
1	1-gon	198
2	Errichto	196
3	rng_58	191
4	awoo	186
5	SecondThread	185
6	Um_nik	182
7	vovuh	177
8	Ashishgup	176
9	antontrygubO_o	174
10	-is-this-fft-	173

Tutorial

Solution (fcspartakm)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

li n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	if (n == 1 || n == 2 || n == 4) {
		cout << -1 << endl;
		return;
	}
	if (n % 3 == 0) {
		cout << n / 3 << ' ' << 0 << ' ' << 0 << endl;
	} else if (n % 3 == 1) {
		cout << (n - 7) / 3 << ' ' << 0 << ' ' << 1 << endl;
	} else {
		cout << (n - 5) / 3 << ' ' << 1 << ' ' << 0 << endl;
	}
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
 
    //cerr << "TIME: " << clock() << endl;
}

1430B - Barrels

Idea: fcspartakm

Tutorial

Solution (fcspartakm)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n, k;
int a[N];

inline void read() {	
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
}

inline void solve() {
	sort(a, a + n);
	reverse(a, a + n);
	li ans = 0;
	for (int i = 0; i <= k; i++) {
		ans += a[i];
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
 	}
    //cerr << "TIME: " << clock() << endl;
}

1430C - Numbers on Whiteboard

Idea: BledDest

Tutorial

Solution (fcspartakm)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);

int n;

inline void read() {	
	cin >> n;
}

inline void solve() {
	multiset<int> was;
	for (int i = 1; i <= n; i++) {
		was.insert(i);
	}
	vector<pair<int, int> > ans;
	for (int i = 0; i < n - 1; i++) {
		auto it = was.end();
		it--;
		int a = *it;
		was.erase(it);
		it = was.end();
		it--;
		int b = *it;
		was.erase(it);
		was.insert((a + b + 1) / 2);
		ans.pb(mp(a, b));
	}
	cout << *was.begin() << endl;
	for (int i = 0; i < sz(ans); i++) {
		cout << ans[i].ft << ' ' << ans[i].sc << endl;
	}	
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    cerr << setprecision(10) << fixed;
    
    int t; cin >> t;
    while(t--) {
    	read();
    	solve();
    }
    //cerr << "TIME: " << clock() << endl;
}

1430D - String Deletion

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

char buf[200043];

int main()
{
	int t;
	scanf("%d", &t);
	for(int tc = 1; tc <= t; tc++) {
		int n;
		scanf("%d", &n);
		scanf("%s", buf);
		string s = buf;
		queue<int> q;
		int cur = 0;
		for(int i = 0; i < n; i++)
		{
		 	if(i > 0 && s[i] != s[i - 1])
		 		cur++;
		 	if(i > 0 && s[i] == s[i - 1])
		 		q.push(cur);
		}
		int deleted = 0;       
		int score = 0;
		for(int i = 0; i < n; i++)
		{
			if(q.empty())
				break;
			q.pop();
			deleted++;
			score++;
			while(!q.empty() && q.front() == i)
			{
				q.pop();
				deleted++; 	
			}
			deleted++;
			//cerr << deleted << endl;
		}
		score += (n - deleted + 1) / 2;
		printf("%d\n", score);
	}
}

1430E - String Reversal

Idea: fcspartakm

Tutorial

Solution (fcspartakm)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <string>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <ctime>
#include <cmath>

#define forn(i, n) for(int i=0;i<n;++i)
#define fore(i, l, r) for(int i = int(l); i <= int(r); ++i)
#define sz(v) int(v.size())
#define all(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair
#define x first
#define y1 ________y1
#define y second
#define ft first
#define sc second
#define pt pair<int, int>

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;

using namespace std;

const int INF = 1000 * 1000 * 1000;
const ld EPS = 1e-9;
const ld PI = acos(-1.0);
const int N = 200 * 1000 + 13;

int n;
string s;
string revS;
vector<int> posS[30];
vector<int> posT[30];
int cnt[30];
int t[N];

inline int sum (int r) {
	int result = 0;
	for (; r >= 0; r = (r & (r+1)) - 1)
		result += t[r];
	return result;
}

inline void inc (int i, int d) {
	for (; i < n; i = (i | (i+1)))
		t[i] += d;
}

int sum (int l, int r) {
	return sum (r) - sum (l-1);
}
     
inline void read() {	
	cin >> n >> s;
}

inline void solve() {
	revS = s;
	reverse(all(revS));
	for (int i = 0; i < sz(s); i++) {
		posS[s[i] - 'a'].pb(i);
		posT[revS[i] - 'a'].pb(i);
	}
	li ans = 0;
	for (int i = 0; i < sz(revS); i++) {
		int let = revS[i] - 'a';
		int cur = posS[let][cnt[let]];
		int oldC = cur;
		cur += sum(cur, n - 1);
		int need = i;
		ans += cur - need;
		inc(oldC, 1);
		cnt[let]++;
	}
	cout << ans << endl;
}

int main () {
#ifdef fcspartakm
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    cerr << setprecision(10) << fixed;
    
    read();
    solve();
 
    //cerr << "TIME: " << clock() << endl;
}

1430F - Realistic Gameplay

Idea: BledDest

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n, k;
vector<int> l, r, a;

inline bool read() {
	if(!(cin >> n >> k))
		return false;
	l.resize(n);
	r.resize(n);
	a.resize(n);
	
	fore(i, 0, n)
		cin >> l[i] >> r[i] >> a[i];
	
	return true;
}

inline void solve() {
	vector<li> d(n + 1, INF64);
	d[0] = 0;
	
	li ans = INF64;
	fore(i, 0, n) {
		li rem = k, total = d[i];
		for (int j = i; j < n; j++) {
			li cntReloads = (max(0LL, a[j] - rem) + k - 1) / k;
			if (cntReloads > r[j] - l[j])
				break;
			
			li newRem = (rem + cntReloads * k) - a[j];
			total += a[j];
			if (j + 1 < n) {
				if (l[j] + cntReloads < l[j + 1])
					d[j + 1] = min(d[j + 1], total + newRem);
			} else
				ans = min(ans, total);
			rem = newRem;
		}
	}
	if (ans > INF64 / 2)
		ans = -1;
	cout << ans << endl;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	if(read()) {
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

1430G - Yet Another DAG Problem

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

typedef long long li;

const int N = 18;
const int M = (1 << N);
const li INF64 = li(1e18);

int n, m;
vector<int> g[N];
li sum[N];
int need_mask[N];
li dp[N + 1][N + 1][M];
bool p[N + 1][N + 1][M];

vector<int> order;       
vector<int> used;

void dfs(int x, bool build_topo)
{
    if(used[x])
    	return;
    used[x] = 1;
    for(auto y : g[x])
    	dfs(y, build_topo);
    if(build_topo)
    	order.push_back(x);
}

int main()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
	 	int x, y, w;
	 	cin >> x >> y >> w;
	 	--x;
	 	--y;
	 	sum[x] += w;
	 	sum[y] -= w;
	 	g[x].push_back(y);
	}
	used.resize(n);
	for(int i = 0; i < n; i++)
		dfs(i, true);
	for(int i = 0; i < n; i++)
	{
	 	used = vector<int>(n, 0);
	 	dfs(i, false);
	 	for(int j = 0; j < n; j++)
	 		if(j != i && used[j] == 1)
	 			need_mask[i] |= (1 << j);		
	}
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
				dp[i][j][k] = INF64;
	dp[0][0][0] = 0;
	reverse(order.begin(), order.end());
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k < (1 << n); k++)
			{
			 	if(dp[i][j][k] > INF64 / 2)
			 		continue;
			 	if(j == n)
			 	{
			 	 	if(dp[i + 1][0][k] > dp[i][j][k])
			 	 	{
			 	 	 	dp[i + 1][0][k] = dp[i][j][k];
			 	 	 	p[i + 1][0][k] = false;
			 	 	}
			 	}
			 	else
			 	{
			 		int v = order[j];
			 		li add = sum[v] * i;
			 		if(dp[i][j + 1][k] > dp[i][j][k])
			 		{
			 		 	dp[i][j + 1][k] = dp[i][j][k];
			 		 	p[i][j + 1][k] = false;
			 		}
			 		if(((k & (1 << v)) == 0) && ((need_mask[v] & k) == need_mask[v]))
			 		{
			 		 	int nk = k | (1 << v);
			 		 	if(dp[i][j + 1][nk] > dp[i][j][k] + add)
			 		 	{
			 		 	 	dp[i][j + 1][nk] = dp[i][j][k] + add;
			 		 	 	p[i][j + 1][nk] = true;
			 		 	}
				 	}
				}
			}
	vector<int> ans(n);
	int i = n;
	int j = 0;
	int k = (1 << n) - 1;
	while(i > 0 || j > 0 || k > 0)
	{
	 	if(j == 0)
	 	{
	 	 	j = n;
	 	 	i--;
	 	}
	 	else
	 	{
	 	 	if(p[i][j][k])
	 	 	{
	 	 	 	int v = order[j - 1];
	 	 	 	ans[v] = i;
	 	 	 	k ^= (1 << v);
	 		}
	 		j--;
	 	}
	}
	for(int i = 0; i < n; i++)
		cout << ans[i] << " \n"[i == n - 1];
}

void solve() { int n; cin>>n; if(n==1 || n==2 || n==4) { cout<<-1<<endl; return; } if(n%3==0){ cout<<n/3<<" 0 0"<<endl; return; } if(n%3==2) { int x=n/3; x--; cout<<x<<" 1 0"<<endl; return; } if(n%3==1) { int x=n/3; --x; --x; cout<<x<<" 0 1"<<endl; return; } return; }

Comments (75)

Write comment?

BledDest

5 months ago, # |

Editorial in Russian will be posted soon. Please be patient!

→ Reply

o-sky

4 months ago, # ^ |

Great round. Thanks =)

_aayush_

My solution of A got hacked! Lesson learnt.

saw.ai

5 months ago, # ^ |

I'm saying it every contest)

agayush

A,B,C were easy to do but couldn't solve out D in time :(

asisdeo

same pinch bruh !!!

traviscott

-51

Does anyone give a f?

+57

did I ask for anyone to give f?

nFlamel

← Rev. 3 →

-10

a1000

Can A be solved using a linear diophantine equation in 3 variables?

LUL____SEPLED1305

← Rev. 2 →

Yes. Nugget number tells us that all number more than or equal to $$$3*5-3-5 = 8$$$ could be written in the form $$$3a+5b$$$ where $$$a,b \geq 0.$$$ So, now you get the general formula

1,2,4 -> no answer

7 -> 0,0,1

The rest could be either brute force or notice that the smallest $$$a$$$ is either $$$0,1,2,3$$$ or $$$4.$$$ So, you could solve this in $$$O(1)$$$

Thanks for helping :)

dvjakhar31

An easier O(1) solution to A..

Aryan-Raina

Thanks it was helpful.

I converted it to diophantine by doing this: 3x+5y=n-7z for z = 0 to n/7 Then using the extended euclids algorithm I found x0 and y0 st 3x0+5y0=gcd(3, 5)=1 and multiplied x0 and y0 by n-7z. Then I tried to find t such that x0+5t, y0-3t are positive. We can use some inequalities to determine range of t and loop over these t and check if the current is correct if yes return. Actually all values in the range are correct but i looped over some modification of the range because I could not think whether to +1 at each iteration or -1(i am new to CP and CS in general) so i checked the cases. My algorithm was correct(you can check my profile for code) but it was very messy, hard to implement for someone not good in math, a lot of code so I don't suggest this.

Thanks, I had trouble implementing it too will check out your solution

moli2398

Can F be solved using BinarySearch? I tried but because of poor implementation and slow speed, got wrong answer on test case 6? Did anyone else try using binary search?

pranshukas

If I am not Wrong this is your Fake Account to hack your own solutions and try some alternate solutions if passed you can just make some changes submit with your original ID so that your rating will not be disturbed.

Lol! Bro you can search this username. It's everywhere. Facebook, Instagram, LinkedIn, Codeforces, Codechef, AtCoder, XDA-Dev, Hackerrank, HackerEarth, LeetCode, and any possible site where one can register and choose a username irrespective of whether it's a coding platform or not. Cant think of any reason why you thought so, but that's not the case. Peace :)

Sorry, Yes You are right. I earlier thought it to be suspicious. Sorry Bro Again, No such intention. !!

I got to know I was about to delete my comment but it was already more than 2 min..

Apologies from my Side. !!!

GladwinRojer

moli2398 I see your solution for problem B got hacked. Is it because of Arrays.sort() being O(N^2) ? Just curious.

Yeah I guess!

aditya_sheth

+15

Can someone please tell their solution for G using Flows?

SecondThread

+13

I solved G with Simplex. I don't have any proof that the answer will always be an integer though. I guess I just got lucky that it was in this case.

cuiaoxiang

+11

Same here.

I think it can be converted into an equivalent mincost maxflow

Veladus

Yes it can.

The linear dual of this problem is actually maximizing the sum of flows along all edges — not just the source. And from each node with negative $$$c_v$$$ you need to send $$$-c_v$$$ units of flow more than goes into this node and each node with positive $$$c_v$$$ needs to receive $$$c_v$$$ flow more than it sends.

inszva

+20

The incidence matrix of a non-empty directed acyclic graph is totally unimodular matrix.
A linear problem whose matrix is totally unimodular matrix always has integer optimal solution.
In this problem, the matrix is the incidence matrix of DAG.

sid9406

I see some people solving E without merge sort tree or fenwick tree . Can someone explain their approach . I know Merge sort tree is the most standard approach for counting inversions but in this case string will have max 26 distinct characters . Can this constraint be used as an advantage to solve in more simpler way ?

cubefreak

These are the 2 approaches I know for calculating inversions in an array other than merge sort and Fenwick tree(If it's relevant to the current discussion).

DIVIDE_AND_CONQUER_SOLUTION

#include <bits/stdc++.h>
using namespace std ;
#define int long long 
int ans =0,b[61]  ;
void dp(vector<int>&a,int i1){
	int c=0,n=a.size(),ans1=0;
	if(n<2||i1<0)
		return ;
	for(int i=0;i<n;i++){
		c+= ((a[i]>>i1)&1) ;
		if(!((a[i]>>i1)&1LL))
			ans1+=c ;
	}
	b[i1]+=ans1 ;vector<int>a1,a2 ;
	for(int x:a){
		if((x>>i1)&1LL)
			a1.push_back(x);
		else 
			a2.push_back(x);
	}
	dp(a1,i1-1);dp(a2,i1-1) ;
}
void solve(){
	int n ;ans=0 ;
	cin >> n ;
	vector<int>a(n);
	for(int &x:a)
		cin >> x ;
	dp(a,61) ;
	for(int i=0;i<61;i++)
		ans+=b[i]  ;
	memset(b,0,sizeof(b)) ; 
	cout << ans <<'\n' ;
}
signed main(){
	int t ;cin >> t ;
	while(t--)
		solve() ;
}

PBDS_SOLUTION

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std ;
#define ar array 
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
void solve(){
    int n ,ans=0 ;
    cin >> n ;
    vector<int>a(n);
    for(int &x:a)
        cin >> x ;
    oset<ar<int,2>>s  ;
    for(int i=0;i<n;i++)
        s.insert({a[i],i});
    for(int i=0;i<n;i++)
        ans+=s.order_of_key({a[i],-1}),s.erase({a[i],i}) ;
    cout << ans << '\n' ;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t ;cin >> t ;
	while(t--)
		solve() ;
}

FiveSixFiveFour

You can also do coordinate compression + segment tree / BIT. Note that if it's a permutation (or something you can transform to a permutation easily) you do not need coordinate compression.

1800O-R_Bust

Can you explain the divide and conquer solution?? Thanks

humbertoyusta

I have an alternative solution to G:

First assign to each node the number given by the following greedy algorithm: Process all nodes in order of topological sort starting from the leaves and assign 0 to a leaf and maximum of values of all the children plus 1 if it's not a leaf.

But this greedy will be not optimal in cases like this: There are four nodes, and there is an edge from node 1 to node 2, another from node 2 to node 3, and another to node 1 to node 4. Here the optimal solution is 2 1 0 1 while the greedy gives 2 1 0 0. But this can be improved with the following greedy brute force-like algorithm:

Select some subset of nodes and try to sum 1 to all nodes in this subset, check if it not ruins anything and if the profit(change to the total answer if we sum 1 to all nodes in this subset) is positive, then if the profit is positive and we can apply the operation we will apply them.

We can do this step to all 2^n subsets, and when it's finished repeat them n — 3 times(because it may be optimal add more than 1 to some nodes). The overall complexity is 2^n*n^3 but in practice is much lower, i have passed the time limits without many optimizations.

However, i have no idea of why it works, so, if anyone can prove it or hack me, i would be really grateful.

ivan100sic

I had the same idea. It's correct because you're effectively emulating the simplex algorithm for linear programming.

Wow, I didn't knew about simplex algorithm, i will find it in google, thanks.

XDD_____

Can someone point whats wrong in my submission for D? https://codeforces.com/contest/1430/submission/95385972

Perry_Prasad_Platypus

your solution will fail in these kind cases: 01110 expected output: 3 your output: 2

Lain

Here is another BIT solution for problem E, which I found more intuitive as a speedup on the naive O($$$n^2$$$) solution.

Explanation:

In the naive solution, you would like to iterate in the reverse direction on the reversed string $$$t$$$, at each position check which character should be there, and then try to move the closest character to its position. That would take $$$i-j$$$ swaps to move the character form position $$$i$$$ to $$$j$$$. But when we do this swap, the positions of the elements after it get messy so if we did it in a dumb way, we would need O(n) to maintain the new positions.

To get around this, we can use a BIT. Store 1 in all positions [0,n-1]. Now, when we query on any position, we would get its one based index in the string. The next observation is that we are always fixing the suffix of the string, so when we swap, we are effectively deleting it from out original string. To simulate this, we can make its value in the BIT 0, and now we can once again find every character's position in O(logn). This way, we could speed it up to O(nlogn)

NeutralMilkHotel

Can someone explain why in the editorial code for D we have deleted++ at the end of the while loop?

DeathHunter

Same doubt.

Harshlyn94

Since for let's say any consecutive block of length in particular 3 that is it maybe like 1110.. then the cnt will remain same for only 2 times starting from the beginning of the block but we are deleting the whole block so the score gets increased only by one while the deleted has to go 3 so first time before the loop while pop from the queue and second time while matching the 2nd and the 3rd character and finally to eliminate the 3rd character we make deleted++ , i hope it helps!

kstheking

my solution to D here
which uses a simple visited array to keep track of deleted numbers by the first operation

Prajwal_

can you explain it, i didn't understood D

You see the second operation always strips away the first continuous segment of the string, so to maximize operations we need to delete using first operations in a way in which the number of continuous segments doesn't decrease a lot
For example in 1011 if you remove 0 you'll be left with 111 which is one segment but if you remove the last one you'll get 101 which has three continuous segments So what we wanna do here is in first operation if possible choose a position which has the same value at its adjacent, because deleting it won't decrease the number of segments such as in 1101 deleting first one will result in 101 which still has 3 segments So in my code I use a visited array to keep track of what positions I deleted with my first operation I try to find what is the first position which is the same as the number after it, and I visit it, after that I use the j variable and traverse it until the end of the first continuous segment, now in next iteration i need to choose another position so it needs to start from i+1 but also after j so i updated it accordingly
In the end i might run out but we might still have j left this will happen in cases like 1010101 In these cases we can simple cut one by one

Thank you so much sir, now i got it

Heisenberg_71

← Rev. 4 →

The second paragraph of editorial of problem D it's written, "It's never optimal to delete a character that's different from both adjacent characters". I think it will be " always " instead of " never ".

not really, you wanna delete characters which are same to the adjacent guys so you don't end up reducing the number of operations for example in 1011 if you delete 0 it will become 111 and will be reduced in just one operation

oh. I got it now. Thank you very much

kushagrasri

I request all the people contributing to the editorial to not use their templates while giving solutions. It would be very helpful to see whole for loop written instead of just seeing inc(l,r) because we have to search through your templates where that is, and then we have to put that code along with your other code and then see it in continuation with that code. It would be easier for better coders to see through it, but for noobs like me, it is just confusing.

SkroX_5

Can anybody provide me with proof as to why choosing the two biggest numbers in problem C always leads to the smallest number remaining at last? It was intuitive but why does that greedy actually works? Thanks in advance!

If you look at the sum of the entire array, you'll see that after n-1 operations this sum is the number itself, which we have to minimize At each operation we are removing (a + b) /2
From the sum, so to minimize the sum you'll choose the largest 2 numbers

Abdullah_Abu_Tasneem

For problem E (String Reversal), can anyone tell me how the answer is 30 for test case 3?

notcool908

can someone please explain to me the solution to problem D. I understood the concept behind the problem, but I am having trouble understanding the code. Thanks.

Falcon__

I think I have a better solution for F in implement,if the n is 5000 , we can use HashMap or other "almost" O(1) datastruct to replace map.Let's get down to our business,we just naive denote dp[i][j] is we finish i task and we left j bullets , we cost the minmum bullets , and normal transtation which should consider if we finish the i in advance or R[i]!=L[i+1] we can refresh the dp[i+1][k] the Code: https://codeforces.com/contest/1430/submission/95434956

avsd_47

-12

Does anyone have flow solution for problem 'G'?

discussed

codingkshatriya

D was a very good greedy, thanks, but why shouldn't we delete the first character if no 2 adjacent characters are equal ?

Trgt_2021_explosion

You can delete the first Character if no 2 adjacent are equal 95567422

Extremely simple O(1) soln for A 95195199

kirakira

It may sound stupid but anyone can explain or proof why problem E

"so the first character a in the original string is the first character a in the resulting string, the second character a in the original string is the second character a in the resulting string, and so on."

will give the optimal solution?

Zahid_Hasan_Sahin

Easy implementetion of C: 95793125

SarthakBansal

I was trying to debug my Solution for E for the past hour. I realized that I declared the vector as char, instead of int -_- (95816212)

I love how bugs in Competitive Programming makes you want to kill yourself!

bluescorp

Stop writing "it's easy to see that" in tutorials. Makes me feel dumb.

EVERNEWBIE

Yep, apparently if you are good at something, you have to tell others that it is easy, in order to increase your ego.

Tony_Stark96

in problem E i cant visualize how counting inversions is the final ans,can anyone help me visualize. Thanks in advance;)

ayirohtip

I am not sure if this question has been asked, I am not finding it. I wanted to ask, "Why the rating of the questions has not been updated yet ?"

kshitijg9899

Hello. Can anyone please explain what is wrong in this code? It is for problem D. Any help would be highly appreciated. Thank You. Problem: 1430D - String Deletion

Code

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
int32_t main() {
    fast;
    int t = 1;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        deque<int> dq;
        int ct = 1;
        char curr = s[0];
        for(int i=1;i<n;i++) {
            if(s[i] == curr) ct++;
            else {
                dq.push_back(ct);
                curr = s[i];
                ct = 1;
            }
        }
        if(ct != 0) dq.push_back(ct);
        int ans = 0;
        while(!dq.empty()) {
            int f = dq.front();
            int b = dq.back();
            if(f == 1) {
                b--;
                dq.pop_back();
                if(b > 0) dq.push_back(b);
                if(!dq.empty()) dq.pop_front();
            } else dq.pop_front();
            ans++;
        }
        cout << ans << endl;
    }
}

La_Liability

Give the input as 10001 and your code would give the output as 2. The current answer should be 3.

10001->1001->001
001->01->1
1->empty

trycod3

4 months ago, # |

please help me with D problem, i tried a lot of tests but still don't know where i was wrong :(, thanks for your care , link submit: https://codeforces.com/contest/1430/submission/96215681

RukahtNama

can someone help me with D

dvjakhar

Can someone explain E?

I don't know if you already solved, but i'll try to explain in a different way from the editorial.

Let's call t the inverted string s, and let's define an array p of n positions where:

p[i] = position of the character of s that is in position i of t.

It can be seen that if p = [n, n-1, n-2, ..., 3,2,1] we would have the string s inverted.

Example:

s = "abcad"
t = "dacba"
p = [5,4,3,2,1]

It can also be seen that the number of inversions in this array is equal to the number of operations required to place all letters in their initial positions.

But here we are faced with a problem, we can see that the number of inversions of this array is maximum (read the article in the link to understand), so we need to somehow try to minimize it to the maximum, how to do this?

Since some characters in the string s can be repeated, let's take advantage of this.

s  = "abcad"
t  = "dacba"
p  = [5,4,3,2,1]
p' = [5,1,3,2,4]

Note that in the example above the two arrays p create the same string t, but p' needs a smaller number of operations to be ordered (it has less inversions). This is because the 'a' appears twice in s. After that, it is possible to notice that if there are repeated letters, their positions in p must be in ascending order in the order in which they appear in s, thus the number of p inversions will always be minimized.

The final answer will be the number of inversions in p.

My solution (don't forget to use long long): 97206684

E solution with merge-tree https://pastebin.com/M0QhbX3F

Teva_

nice contest

meesgood

3 months ago, # |

In B how do we know that lower bound of (a+b)/2 has to be taken? It is not even mentioned!

rgnerdplayer

6 weeks ago, # |

what is dp array in the solution code, seems very different from the tutorial

BledDest's blog