Codeforces Round #790 (Div. 4) Editorial

#	User	Rating
1	tourist	3805
2	maroonrk	3637
3	Benq	3513
4	ecnerwala	3506
5	MiracleFaFa	3466
6	slime	3428
7	jiangly	3415
8	Radewoosh	3399
9	greenheadstrange	3393
10	djq_cpp	3391

#	User	Contrib.
1	awoo	192
2	-is-this-fft-	191
3	Monogon	185
4	Um_nik	182
4	YouKn0wWho	182
6	maroonrk	170
7	antontrygubO_o	167
8	errorgorn	166
8	kostka	166
10	SecondThread	165

Thank you for participating!

Tutorial

Solution

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

void solve() {
	string s;
	cin >> s;
	if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

1676B - Equal Candies

Idea: Errichto

Tutorial

Solution

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

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int> a(n);
        int mn = INT_MAX, ans = 0;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
            mn = min(mn, a[i]);
        }
        for(int i = 0; i < n; ++i) {
            ans += a[i] - mn;
        }
        cout << ans << "\n";
    }
}

1676C - Most Similar Words

Idea: MikeMirzayanov

Tutorial

Solution

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

int cost(string& a, string& b) {
    int val = 0;
    for(int i = 0; i < a.size(); ++i) {
        val += abs(a[i] - b[i]);
    }
    return val;
}

int main() {
    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        vector<string> s(n);
        for(int i = 0; i < n; ++i) {
            cin >> s[i];
        }
        int ans = INT_MAX;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                ans = min(ans, cost(s[i], s[j]));
            }
        }
        cout << ans << "\n";
    }
}

1676D - X-Sum

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
	int n, m;
	cin >> n >> m;
	int a[n][m];
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	int mx = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			int now = 0;
			int ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci--;
				cj--;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci++;
				cj--;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci--;
				cj++;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci++;
				cj++;
			}
			now-=a[i][j]*3;
			mx = max(mx, now);
		}
	}
	cout << mx << endl;
}

int main() {
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}

1676E - Eating Queries

Idea: mesanu

Tutorial

Solution

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

int main() {  
    int t; cin >> t;
    while(t--) {
        int n, q; cin >> n >> q;
        vector<long long> a(n), p(n);
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.rbegin(), a.rend());
        for(int i = 0; i < n; ++i) {
            p[i] = (i ? p[i - 1] : 0) + a[i];
        }
    
        while(q--) {
            long long x; cin >> x;
            int l = 1, r = n, ans = -1;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(p[mid - 1] >= x) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            cout << ans << "\n";
        }
    }
}

1676F - Longest Strike

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
	int n, k;
	cin >> n >> k;
	int a[n];
	map<int, int> mp;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		mp[a[i]]++;
	}
	vector<int> c;
	for(auto x : mp)
	{
		if(x.second >= k)
		{
			c.push_back(x.first);
		}
	}
	if(c.size() == 0)
	{
		cout << -1 << endl;
		return;
	}
	sort(c.begin(), c.end());
	int mx = 0;
	int lans = c[0], rans = c[0];
	int l = c[0];
	for(int i = 1; i < c.size(); i++)
	{
		if(c[i]-1 == c[i-1])
		{
			if(c[i]-l > mx)
			{
				lans = l;
				rans = c[i];
				mx = c[i]-l;
			}
		}
		else
		{
			l = c[i];
		}
	}
	cout << lans << " " << rans << endl;
}

int main(int argc, char * argv[])
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}

1676G - White-Black Balanced Subtrees

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	vector<int> child[n + 7];
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		child[x].push_back(i);
	}
	string s;
	cin >> s;
	int res = 0;
	function<int(int)> dp = [&] (int x) {
		int bal = (s[x - 1] == 'B') ? -1 : 1;
		if (child[x].empty()) {return bal;}
		for (int i : child[x]) {
			bal += dp(i);
		}
		if (bal == 0) {res++;}
		return bal;
	};
	dp(1);
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

1676H1 - Maximum Crossings (Easy Version)

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] >= a[j]) {res++;}
		}
	}
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

1676H2 - Maximum Crossings (Hard Version)

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

long long merge(int a[], int temp[], int left, int mid, int right) {
   int i, j, k;
   long long count = 0;
   i = left;
   j = mid;
   k = left;
   while ((i <= mid - 1) && (j <= right)) {
      if (a[i] <= a[j]){
      temp[k++] = a[i++];
      } else {
         temp[k++] = a[j++];
         count += (mid - i);
      }
   }
   while (i <= mid - 1)
      temp[k++] = a[i++];
   while (j <= right)
      temp[k++] = a[j++];
   for (i=left; i <= right; i++)
      a[i] = temp[i];
   return count;
}
long long mergeSort(int a[], int temp[], int left, int right){
   int mid;
   long long count = 0;
   if (right > left) {
      mid = (right + left)/2;
      count = mergeSort(a, temp, left, mid);
      count += mergeSort(a, temp, mid+1, right);
      count += merge(a, temp, left, mid+1, right);
   }
   return count;
}
long long aInversion(int a[], int n) {
   int temp[n];
   return mergeSort(a, temp, 0, n - 1);
}

void solve() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long res = aInversion(a, n);
	sort(a, a + n);
	long long curr = 1;
	for (int i = 1; i < n; i++) {
	    if (a[i] != a[i - 1]) {res += (curr * (curr - 1)) / 2; curr = 1;}
	    else {curr++;}
	}
	res += (curr * (curr - 1)) / 2;
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

{ long long l = 0 ; long long r=0; long long maxD = -1; long long maxL = 0; long long maxR = 0; long long counter = 0; for(it ; it != m1.end() ; it++){ if(it->second >= k && l==0) { l = r = it->first; } if(it->second >= k && it->first == r+1) { r = it->first; } else if(k > it->second){ long long diff = r-l; if(diff>maxD){ maxL = l; maxR = r; maxD = diff; } l = 0; r = 0; counter++; } } if(counter == m1.size()) cout<<"-1"<<endl; else if((maxR-maxL)<=(r-l) && r>maxR) cout<<l<<" "<<r<<endl; else if((maxR-maxL)>=(r-l)) cout<<maxL<<" "<<maxR<<endl; }

Comments (81)

Write comment?

Codula

8 days ago, # |

← Rev. 2 →

+25

It was honor to test this contest.Thanks for the Great round.Also great blog thanks for helping the community.

→ Reply

t.alhumaidi

Thanks for the effort, much appreciated!

HurricaneCoder

I had another solution for 1676G - White-Black Balanced Subtrees — I used DFS to recursively compute all vertices' values, saved them in an array and then just scanning the array for the vertices that have the equal number of white and black vertices in their subtrees. Maybe this is an easier explanation not containing DP clearly.

ishaank10

8 days ago, # ^ |

This approach is DP as well as you are finding and storing all the values for black and white vertices for each subtree and then later only just iterating over all vertices to check which have equal no. of white and black vertices in their subtree. Actually it is quite similar to what is being done in the editorial as well except the fact that they are just finding number of balanced subtrees while doing dfs only and you are just running a separate loop after the dfs.

cleanser

I really threw on C and D cuz I'm bad at determining time complexity.

kl1dd

The same with D

For C, I calculated the number of operations as (100 * 50 * 8)^2 instead of (50 * 8)^2 * 100. For D, I assumed that the intended solution was actually O(n^2)

Quicksvolex

5 days ago, # ^ |

isn't the time compelexity of C O(n^2 * m)??

fuadul

my first unrated round and I have solved all of the problem in the contest time. happy coding :) problems were so interesting.

QuieterHabit

wow..i saw ur profile if ur rating was just 12 less, your rating would go like a slingshot , just a little back,,,and so much further.

Yes you are right.. but I enjoyed this round. :)

ug123458

← Rev. 8 →

-8

156676512 It was working fine and was accepted how can it be hacked I checked everything while submitting

HarshitKumarGupta

You have linearly searched for the query in your prefix sums array. While the approach is not wrong, under the given constraints of sum of $$$N$$$ and $$$Q$$$ over all cases to go up to $$$1.5 * 1e5 = 150000$$$, which can cause Time Limit Exceeded (TLE) on higher values, close to the constraint limits.

GOD_LYNXX

-16

The Time complexity of Problem D O(qlogn+n). But If we calculate for the worst-case according to given constraints then it should be -: 10^7 * 10^3 + 10^7. Also you are not considering the loop for test cases, so according to me its T.C should be. O(T*N*qlogN) However this T.C also not fast. So I am getting this doubt. Please correct me if I am wrong.

Maybe you have gone through Problem E instead of Problem D, or could have mentioned it otherwise?

nekoyukino

I guess you are talking about problem E but not D.

It is guaranteed $$$\sum n$$$ and $$$\sum q$$$ over all test cases don't exceed $$$1.5\times10^5$$$, so there's no need to multiply $$$T$$$ when calculating the time complexity.

On this condition, the time complexity is $$$O(q\log n)\approx 1.5\times 10^5\times 17 = 2.6\times 10^6$$$, it's able to pass easily under the 3.5 seconds time limit.

afshaan08

This is the best div 4 contest, for beginners. All problems are completely balanced in terms of difficulty. Expecting more similar div 4 contests in future.

tzhang995

Got lazy on the last question and didn't do it (especially sinced I had work). Oooo well

BelalMoawad

Great Round, I am really excited to see my new cyan color.

khadzakos

E, F and H2 are really good problems.

Nice Div. 4!

Uzumaki_TheLoser

problem h2 : Has anyone used ordered_set (multiset using pair) (pbds) ??

Omar_Hafez

I used it but i had crazy bug in my code and i couldn't fix it during the contest

rishab.ladha

Yes , i have used it.

IanAbusa

Can someone please help me to understand the ordered_set solution to problem H2? I understand that "order_of_key(k)" returns the number of elements strictly less than k. However, I have seen many solutions that use an ordered_set with a pair to find the number of elements i<j && a[i] >= a[j], like this one:

ordered_set<ll>st;
    for(i = n;i>0;i--)
    {
        ans+=(st.order_of_key({a[i], inf}));
        st.insert({a[i],i});
    }
    cout<<ans<<"\n";

Why does order_of_key(a[i]) not work(to me, it seems that the index is irrelevant), and what is the functionality of pairs in an ordered_set? Any help would be appreciated.

Mistri_

To what I can understand, people use pairs so that they do not have to worry about equal values. Since we need to find inversion that might be equal, it is a good idea to use pair<int,int> where every value had its unique index and we can get out answers simply by using order_of_key function call. You can also do this without using pairs, just use greater_equal<int> in your ordered_set typedef and use a map to store equal values.

Thanks for the explanation. Your clever usage of maps along with order_of_key() helped me understand what was going on.

InfinteIllusion

u can replace less with less_equal for using ordered_multiset

Here is my submission : https://codeforces.com/contest/1676/submission/156780422

7 days ago, # ^ |

Very useful. Thanks!

yayy

I loved the round! The problems all had short and clean implementations, and I had a good take taking the contest.

EbrahimElhabashy

In E the binary search part why did you use l = 1 instead of 0 and r = n instead of n-1 ? I have a problem with boundaries of binary search that costed me 40 minutes :(

GlenBzc

I was in the same situation as you, I was stuck on the dichotomous boundary condition for at least 30 minutes until I remembered a function called lower_bound() ....

Yes, I remember it now but still I need to learn how to use my own binary search.

KK_1729

thanks a lot for the round. It was great. hope to have many more Div4 rounds like this.

TMJYH09

The problems of this contest are very good, it is very suitable for people of my level XD

0x3F

+91

-13

这图笑死了

Juanm1

and they sort too

fluorspar

Can someone please explain how the BIT approach works for H2? Or maybe redirect me to some article which explains it well. Thanks.

Monohydr

My BIT approach for H2:156714981

apoorv_me

so you have to find ai >= aj for i < j, so if you know BIT than we can process range sum queries so, at each step we will calcumlate, rangesum(a[j], max(a)) = this will give count of all elements greater than j that you hav eupdated in BIT, after doing this you will inccrease count of a[j] in BIT

Got it thanks!

https://codeforces.com/blog/entry/86294 — Inversion count

Editorial solution for F in python TLE's

singh0

Hi, can someone explain why my nlogn solution failed for problem F. It got accepted during the contest and even after the hacking phase finished it was accepted. But now when I checked (14 hours) after the contest it suddenly got TLE on 18th test case.

KingRayuga

It's because after the hacking phase is over all the solution are again tested with the test case used in hacks and so is yours, the main reason the worst time complexity is not nlogn it n^2, because the c++ unordered map uses linear data structure in case of collision to search for the elements , ideally it should be nlogn if instead of linear data structure, AVL tree is used which is the case with Java

Thank you for the explanation. So is it not suggested to use unordered_map? I usually avoid using ordered map for better time complexity, but if unordered_map is not consistent, should I just stick with ordered map or any other alternative?

Try to avoid them as much as you can but use ordered map always if Time complexity allows

ajit_25

Can someone please tell me why its giving tle its very similar to whats given in tutorial here is my submission https://codeforces.com/contest/1676/submission/156791528

You are getting TLE because rather than iterating over the n values in the array your loop is iterating over all values in mini to maxi which can be very large of the range 10^9 as it is given in the constraints that 1 <= a[i] <= 10^9

misorin

+10

If you use python and get TLE in problem F, I suggest you read this blog.

https://codeforces.com/blog/entry/101817

DeathCoder_Ji

Can someone explain F? I got confused during the contest.

you have to output a range L, R

such that every element between L, R has count greater than equal to k, if there is no element in array its count is considered zero

shuriksokol

Why does solution for F have linear time complexity? Insertion of the new key into map works is logarithmic time, so in the worst case (n different values in the array) it will take O(n log n) time to insert all the keys into map

orz

Vergil_God

Can somebody help me with my Solution for question F. It got accepted last night during the contest but it was rejected in the system checking stating that it is giving TLE for Test case 18. My Solution for F

I am basically doing exactly what is mentioned in the editorial but mine is getting TLE.

See this comment https://codeforces.com/blog/entry/102710?#comment-911393

robostac

https://codeforces.com/blog/entry/62393

hitbit

I am not able to understand why is this happening ? Why using unordered_maps results in tle and while using map it works fine ?

Hash collisions!!!!!!!

I have experienced some shocking results in F problem where if I use unordered_map it gives me TLE but on using map its working fine! Am I missing something?

When the value of n is large (usually larger than 10^5) then because there can be high number of collisions so hashmaps gives its worst case time complexity for insertion operations that is O(n) and not O(1) which is why the overall time complexity becomes O(n^2).

The solution is to use a map as there we don't have a problem of collisions and the time complexity is logn per operation.

gavricnikola7

Took me a while because I tried optimising problem D. Didn't realize n*m*(n or m) fits the time limit. Can anyone explain me how do i calculate what constraints take what time for a given big O.

zeyf

Hey, honestly with some experience you start to get a feel for when you can just do pure bruteforce. It's funny, in university, bruteforce is not really liked as it typically denotes a poor solution. I used to do a lot of Leetcode, and rarely is bruteforce the solution needed or would be acceptable (aside from the fact they don't really have that many bruteforce-based questions). So when I got into CP, it was a shift in perspective on when I can or can't do bruteforce based on the constraints.

You can do some quick math, at worst 200*200 board, so n*m alone will be 4*10^4. Then you will do at most n or m iterations depending on your location, so let's say worst case n and m are 200 again. You have two go over the diagonal twice

2*200*(4*10^4) = 16*10^6 = 16,000,000 operations at worst. Even then, this is way over since pretty much the middle will be the only one where you iterate the full n or m. Meaning as we are left, right, up, or down from the middle, we have less than 2*200 iterations over diagonal at every other location.

Now I didn't go through this in my head or used this in my reasoning. Like I said, you do these problems enough and you "know" if bruteforce is fast enough.

The solution to eating queries would be O(NlogN + QlogN). They did not consider the sorting as part of the runtime, only the read in of the numbers.

Demr64

7 days ago, # |

Nice div. 4! I love the problems solutions!

Saroboii

I really couldnt understand the 1676C problem. Can someone care to explain the algorithm?

rebel_roar

Please can you tell me what my submission giving TLE ?

Submission

It is because you are using unordered map and not map, I have already explained the reason in an earlier comment. Check this out if interested

qbs

Hi mesanu, for D. X-Sum my python code got TLE. I looked up the editorial, it looked similar to mine. Is it a language problem (like I have to use C++ rather than python) or I am missing something in my code?

My submission Id: 156738601

Thanks!