Educational Codeforces Round 150 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 (BledDest)

t = int(input())
for i in range(t):
    n = int(input())
    print('Alice' if n >= 5 else 'Bob')

1841B - Keep it Beautiful

Idea: BledDest

Tutorial

Solution (awoo)

for _ in range(int(input())):
	q = int(input())
	a = []
	cnt = 0
	for x in map(int, input().split()):
		nw_cnt = cnt + (len(a) > 0 and a[-1] > x)
		if nw_cnt == 0 or (nw_cnt == 1 and x <= a[0]):
			a.append(x)
			cnt = nw_cnt
			print('1', end="")
		else:
			print('0', end="")
	print()

1841C - Ranom Numbers

Idea: BledDest

Tutorial

Solution 1 (Neon)

#include <bits/stdc++.h>

using namespace std;

const int val[] = {1, 10, 100, 1000, 10000};
const int INF = 1e9;

string s;
int dp[2][5][2];

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> s;
    reverse(s.begin(), s.end());
    for (int j = 0; j < 5; ++j)
      dp[0][j][0] = dp[0][j][1] = -INF;
    dp[0][0][0] = 0;
    for (auto c : s) {
      int x = c - 'A';
      for (int j = 0; j < 5; ++j)
        dp[1][j][0] = dp[1][j][1] = -INF;
      for (int j = 0; j < 5; ++j) {
      	for (int t = 0; t < 2; ++t) {
      	  for (int y = 0; y < 5; ++y) {
      	  	int nj = max(j, y);
      	  	int nt = t + (x != y);
      	  	if (nt < 2) dp[1][nj][nt] = max(dp[1][nj][nt], dp[0][j][t] + (y < nj ? -val[y] : val[y]));
      	  }	
      	}
      }
      swap(dp[0], dp[1]);
    }
    int ans = -INF;
    for (int j = 0; j < 5; ++j)
      ans = max(ans, max(dp[0][j][0], dp[0][j][1]));
    cout << ans << '\n';
  }
}

Solution 2 (BledDest)

def replace_char(s, i, c):
    return s[:i] + c + s[i + 1:]
    
def id(c):
    return ord(c) - ord('A')
    
def evaluate(s):
    t = s[::-1]
    ans = 0
    max_id = -1
    for x in t:
        i = id(x)
        if max_id > i:
            ans -= 10 ** i
        else:
            ans += 10 ** i
        max_id = max(max_id, i)
    return ans

t = int(input())
for i in range(t):
    s = input()
    candidates = []
    for x in ['A', 'B', 'C', 'D', 'E']:
        for y in ['A', 'B', 'C', 'D', 'E']:
            if not (x in s):
                continue
            candidates.append(replace_char(s, s.find(x), y))
            candidates.append(replace_char(s, s.rfind(x), y))
    print(max(map(evaluate, candidates)))

1841D - Pairs of Segments

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

bool comp(const pair<int, int>& a, const pair<int, int>& b)
{
	return a.second < b.second;
}

void solve()
{
	int n;
	scanf("%d", &n);
	vector<pair<int, int>> s(n);
	for(int i = 0; i < n; i++)
		scanf("%d %d", &s[i].first, &s[i].second);
	
	vector<pair<int, int>> pairs;
	for(int i = 0; i < n; i++)
		for(int j = i + 1; j < n; j++)
			if(max(s[i].first, s[j].first) <= min(s[i].second, s[j].second))
				pairs.push_back(make_pair(min(s[i].first, s[j].first), max(s[i].second, s[j].second)));
			
	int cnt_pairs = 0;
	sort(pairs.begin(), pairs.end(), comp);
	int last_pos = -1;
	for(auto x : pairs)
		if(x.first > last_pos)
		{
			cnt_pairs++;
			last_pos = x.second;
		}
		
	printf("%d\n", n - cnt_pairs * 2);
}

int main()
{
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++) solve();
}

1841E - Fill the Matrix

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

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

using namespace std;

struct seg{
	int l, r;
};

bool operator <(const seg &a, const seg &b){
	return a.l < b.l;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n;
		scanf("%d", &n);
		vector<int> a(n);
		forn(i, n) scanf("%d", &a[i]);
		long long m;
		scanf("%lld", &m);
		map<seg, int> used;
		used[{0, n}] = n;
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 0);
		sort(ord.begin(), ord.end(), [&a](int x, int y){
			return a[x] > a[y];
		});
		long long ans = 0;
		int j = 0;
		vector<long long> cnt(n + 1);
		for (int i = n; i >= 0; --i){
			while (j < n && a[ord[j]] >= i){
				auto it = used.upper_bound({ord[j], -1});
				--it;
				auto tmp = it->first;
				cnt[tmp.r - tmp.l] += it->second - i;
				used.erase(it);
				if (tmp.l != ord[j])
					used[{tmp.l, ord[j]}] = i;
				if (tmp.r != ord[j] + 1)
					used[{ord[j] + 1, tmp.r}] = i;
				++j;
			}
		}
		for (int i = n; i > 0; --i){
			long long t = min(cnt[i], m / i);
			ans += t * 1ll * (i - 1);
			m -= t * 1ll * i;
			if (t != cnt[i] && m > 0){
				ans += m - 1;
				m = 0;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

1841F - Monocarp and a Strategic Game

Idea: TheWayISteppedOutTheCar and BledDest

Tutorial

Solution (TheWayISteppedOutTheCar)

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
#define x first
#define y second
const int MAXN = 2e6 + 16;
int a[MAXN], b[MAXN];
pair<int, int> v[MAXN];
int section(pair<int, int> a) {
    if (a.x > 0 && a.y >= 0)
        return 0;
    else if (a.x <= 0 && a.y > 0)
        return 1;
    else if (a.x < 0 && a.y <= 0)
        return 2;
    else
        return 3;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (section(a) != section(b))
        return section(a) < section(b);
    else
        return (__int128)a.x * (__int128)b.y - (__int128)a.y * (__int128)b.x > 0;
}
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
signed main() {
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
		vector<int> t(4);
		for(int j = 0; j < 4; j++)
			cin >> t[j];
		a[i] = t[0] - t[1];
		b[i] = t[2] - t[3];
	}
    int it = 0;
    __int128 sx = 0, sy = 0;
    for (int i = 0; i < n; ++i) {
        v[i << 1].x = a[it];
        v[i << 1].y = b[it];
        ++it;
        v[i << 1 ^ 1].x = -v[i << 1].x;
        v[i << 1 ^ 1].y = -v[i << 1].y;
        if (!v[i << 1].x && !v[i << 1].y) {
            --i, --n;
            continue;
        }
        if (v[i << 1].y < 0 || (!v[i << 1].y && v[i << 1].x < 0))
            sx += v[i << 1].x, sy += v[i << 1].y;
    }
    sort(v, v + 2 * n, cmp);
    __int128 ans = sx * sx + sy * sy;
    for (int i = 0; i < 2 * n; ++i) {
        sx += v[i].x;
        sy += v[i].y;
        ans = std::max(ans, sx * sx + sy * sy);
    }
    print(ans);

    return 0;
}

#include <string> #include <iostream> int main() { std::string s; for (int i = 1; i <= 1e6; ++i) s += 'c'; for (int i = 1; i <= 1e6; ++i) { // s += "c"; // s += 'c'; // s = s + "c"; // s = s + 'c'; } std::cout << s << '\n'; }

int ptr = 0; lll x = 0, y = 0, mx = 0; for(int i = 0; i < n; i++) { while(ptr < i + n) { lll cp = cross(A[i % n][0], A[i % n][1], A[ptr % n][0], A[ptr % n][1]); lll dp = dot(A[i % n][0], A[i % n][1], A[ptr % n][0], A[ptr % n][1]); if(cp < 0 || (cp == 0 && dp < 0)) { break; } // remember to add this condition to not loop back if((cp == 0) && (dp > 0) && ((ptr % n) < i)) { break; } x += A[ptr % n][0]; y += A[ptr % n][1]; ptr++; mx = max(mx, x * x + y * y); } x -= A[i][0]; y -= A[i][1]; mx = max(mx, x * x + y * y); }

Comments (71)

Show archived | Write comment?

maityankan10

17 months ago, # |

← Rev. 2 →

I am facing time-limit-exceeded in test-case3 Problem B solution

→ Reply

Siddharth81

17 months ago, # ^ |

Remove the line // s = s + "1" from your code because adding "1" instead of '1' works as string concatenation and its time complexity is O(n^2) thus making your code's overall complexity as O(n^3) for large n.

_Fusu

I made a test to find that it has nothing to do with whether you use "1"(string) or '1'(character).

I wrote such code below:（my compilation standard is G++17)

If I run the first two annotations I wrote(which means removing // in front of s += "c" or s += 'c'), it would complete and output immediately. Instead, if I run the last two annotations I wrote(which means removing // infront of s = s + "c" or s = s + 'c', the program ran for a long time without outputing.

So the key is that you can't use operator = but you must use operator +=. The former is $$$O(|s|)$$$ for there is a copy occurs, while the latter is $$$O(1)$$$(in average) for it would just append a character/string(with a constant length) to the end of $$$s$$$.

Soultaker

+12

According to the C++ standard, only s.push_back('c'); is guaranteed to have amortized constant time complexity. In practice s += 'c'; will behave the same, since there is no practical benefit to making it any slower.

So the key is that you can't use operator = but you must use operator +=.

Using += is good advice, but the reason that a copy is made isn't because of the use of = for assignment, but rather because s is an lvalue in the expression s + 'c'. You can make the assignment equally efficient with:

s = std::move(s) + 'c';

Of course, it's much easier to just write s += 'c' at this point.

noobiesAG

I have made a detailed video (its in hindi language) to solve problem C using 3 different approaches.
Video link : link
Let me know if it helps you :)

Proofy

← Rev. 5 →

+24

I'm going to share some of my solutions since they are not mentioned in the editorial.

For 1841C - Ranom Numbers, I basically did some sort of brute force, checking every possible replacement for a character and taking the maximum.

The trick is that when you decrease a character, some of the characters that are directly affected by you may not be affected anymore (or may be affected by some other letter on the right of the current letter), and when you increase a character, some of the characters are before you and not affected by anybody may be affected by you.

To check this, I made a vector called where where where[i] are the indices where character i occurs, so that when checking whether there is a greater or smaller character after some index it becomes easy with a std::lower_bound (or binary search). Moreover, I maintain a frequency of all non-affected characters before me and all characters that are directly affected by me, and then do some calculations. (I admit it, the solution is hairy) Code here

For 1841D - Pairs of Segments, I sorted according to the left boundary (and so let [l[i], r[i]] denote the intervals after sorting).

Now, use Dynamic Programming where dp[i] is the minimum number of removed intervals starting at i, and the transitions are either dp[i] = dp[i + 1] + 1 where we just remove the current interval or we try to see if we can merge it, so we loop over all segments with index j > i to find the segment that intersects with i with minimum right boundary, let this interval be x (if not found, just don't proceed with this transition), and let R = max(r[x], r[i]) (basically the right boundary after merging)

and then we basically try to minimize with dp[j] + removed where j is such that j > i and l[j] > R and removed denotes all segments k where i < k < j and k is not x, which are all the removed segments. Code here

For 1841E - Fill the Matrix, I used the same general idea: we just collect all contiguous segments in the same row in the matrix by considering from the bottom row to the top row and noting that some of the black towers split some segments in two.

However, I feel my implementation was a bit simpler, it was using an idea called deltaing that I learned from Algorithms Live's amazing episode 9: "Solution Bags".

The idea is to maintain

A vector called where where where[i] are the indices where the number i in the array.
A set (called st cause I didn't think what to call it) containing all the indices of the black cells in the current row. It initially contains -1 and n (since indices are zero-based)
A vector segments where segments[i] denotes the frequency of all segments of size i, initially all zeros except for segments[n] = n, this is to denote that for all we know, all segments didn't occur, and a segment of size n occurs n times (as if the table is empty), and we will update this as we go (this is the "deltaing" part)

Now, we loop on row j from n down to 1, and we note that there are black cells in where[j] that split the segments. How do we know which segments are being split? Using the set st: -

Suppose that a black cell appears at index i, we can find the previous black cell as L = *prev(st.lower_bound(i)) and the next black cell as simply R = *st.lower_bound(i), and we know they both exist since we started with -1 and n in the set. The update goes as follows:

The segment with length R - L - 1 will be removed, meaning that it will not exist for j rows from now on, so we decrement segments[R - L - 1] -= j, meaning that for all we know, we assumed it exists for all segments[R - L - 1] rows but now we know that it will not exist for j rows (from now on).
A segment with length R - i - 1 will exist now, so we increment segments[R - i - 1] += j, meaning that for all we know, unless we update it, a segment of length R - i - 1 will exist for j more rows.
A segment with length i - L - 1 will similarly exist now, so segments[i - L - 1] += j, for the same exact reason.
We insert i in the set st.

After we're done we basically have the frequency of each size of a segment, and we can just loop greedily from the largest segment to the smallest segment and fill as much as we can with our m integers. Code here.

Abito

I did same in C 209455681 but different imp

yadavDipesh

← Rev. 3 →

In D soln , In last paragraph shouldn't it be

and then we basically try to minimize , instead of maximize

Fixed it, thanks.

tanishgoyal16

Your explaination for 1841D is brief and awesome.

Could you reason about why you are pairing the i'th segment with the segment whose right boundary is minimum (In case we are not removing the i'th pair) ?

It's because whatever segment x you choose to pair with, you'd have to go minimize with all dp[j] where l[j] > R and noting that R = max(r[x], r[i]), so whenever you minimize this R, you get more options of j to pair with, so we just choose the one with the minimum r[x].

aapoorv

209599406 I'm facing runtime error for this solution but it works locally for me

vgtcross

Compiling with debug flag -D_GLIBCXX_DEBUG gives "Error: attempt to subscript container with out-of-bounds index -1". This is happening on the line return dp[id][k][mx]=res;, since mx can be equal to -1.

nicksms

+14

F can be solved in higher dimensions $$$d$$$ in $$$O(n^{d-1}(d + \log n))$$$: https://link.springer.com/article/10.1134/S1990478917040160

V4V

+53

There is O(NlogN) solution for D, we can sort segments by right border, then calculate dp = answer for prefix, if we using i-th segment in pair, we can greedily use intersecting segment with the maximum left border (we can find it with segment tree), we can do this because it increases left border of their union. here is the code 209602279

ankancool

I don't like DP

davi-v

By the way, you don't need to sort by the left endpoint: 209680351

DangKhoaWillWinIOI2024

16 months ago, # ^ |

Nice Solution!!!

nikilrselvam

For F, what does it mean to calculate the Minkowski sum of a single set of points?

I’m familiar with Minkowski sum of two sets / convex polygons. However, Minkowski sum of the set of all vertices with itself only gives pairwise sums. It looks like here we are interested in sums of all subsets though, which looks harder.

oursaco

For each group add (0, 0) and (a - b, c - d) to the Minkowski sum to give the option of taking or not taking.

Ah that’s clever, thanks! I misinterpreted the editorial to mean “sum of {(0,0), (x1,y1), (x2,y2), …}” instead of “sum of all {(0,0), (x,y)} pairs”

propane

Sorry to bother you, but can you explain how the code in the solution computes the Minkowski sum? I only know how to calculate the Minkowski sum of two convex hulls:)

I compute the Minkowski sum with D&C.209634929

The difference array of the minkowski sum of two convex polygon starting from the bottomost leftmost point going counterclockwise is equivalent to the sorted concatenation of the difference arrays sorted by counterclockwise order starting from the negative y axis ((0, -1) would be last).

of those two convex polygons, so you can just maintain the differences and the bottommost point after adding every pair of points.

ie. (0, 0), (1, 0), (0, 1) has a difference array of (1, 0), (-1, 1), (0, -1)

(0, 0), (1, 1) has a difference array of (1, 1), (-1, -1)

Their minkowski sum is (0, 0), (1, 0), (2, 1), (1, 2), (0, 1) which has a difference array of (1, 0), (1, 1), (-1, 1), (-1, -1), (0, -1)

Since for each pair of points being added to the polygon there is only (0, 0) and (a - b, c - d), you can just add (a - b, c - d) and (b - a, d - c) to the difference array and sort them all by counterclockwise order afterwards. You just have to maintain the current bottommost leftmost point which is (sx, sy) as well.

I got it! Thank you very much.

kondasujay2

+30

Another way to do problem E is with a stack in O(n). Because you are essentially given a histogram, we can use a stack to maintain the heights of the rectangles and length of the rectangles, while trying to maximize the length of the rectangle. Then whenever we pop from the stack we add to a count of a specific size of a segment.

More details are in this submission: 209610350

tyagsa

For Problem E, I maintained the empty spaces in each column .. then solving for some range from {l,r} find the minimum empty space in that range .. and add {(r-l+1), minV} to a set, subtract minV from all elements in the range {l,r} as that much space is utilized now, then we can then solve it recursively for range {l, minIdx-1} and {minIdx + 1, r}.

Submission — https://codeforces.net/contest/1841/submission/209625055

Video Solution — https://www.youtube.com/watch?v=N0_QB3hPP_8

Nihad_Nabelsi

+29

Simple approach for D with complexity o(n*log).

So2c

15 months ago, # ^ |

Maintaining the set is also not required just a variable is enough that stores the right end of the segment which does not intersect with the previous pair. Solution

I just wanted to mention this, I know you would already know this.

That is true, thank you for your mention.

-10

In problem D, is there a graph based solution where we the graph has edges between intersecting intervals?

NuclearMint

I tried to think of this but I am stuck In the graph solution I think you have to find the maximum k such that there exists k edges which are disjoint and donot have edges between them but I am not able to find out which property of graphs can be exploited further to arrive at the solution.

This is binary-searchable

I am sorry but I didn't uderstand what you meant by binary searchable ??

If you can make 4 pairs then you can make 3 pairs of course. What remains is the check function though which is hard to find

skinnyasiandude

In problem C, it states that

$$$dp_{i,j,k}$$$ is the maximum value of the number if we considered $$$i$$$ first characters, applied $$$k$$$ changes to them ($$$k$$$ is either 0 or 1), and the maximum character we encountered so far was $$$j$$$ ($$$j$$$ can have 5 possible values).

But why we only need size of 2 for $$$i$$$ in int dp[2][5][2]; here?

musashi

when calculating the value of dp [i][][], just the value of dp[i — 1][][] is needed. Therefor you only need dp [2][][], where dp [0][][] is dp[i — 1] and dp[1][][] is dp [i][][] .Remember to swap them after each for loop

aniketabhiraj2004

can anybody please find what is an error in my code for problem D it gives WA in test case 5

for _ in range(int(input())): n = int(input()) p = [] for i in range(n): u,v = map(int,input().split()) p.append((u,v)) p.sort() st = [] en = [] for i in p: st.append(i[0]) en.append(i[1]) dp = [0 for i in range(n+1)] for i in range(n-1,-1,-1): u = bisect(st,en[i]) for j in range(i+1,u): p1 = bisect(st,en[j]) dp[i] = max(dp[p1] + 2,dp[i+1],dp[i]) dp[i] = max(dp[i],dp[i+1])
print(n-dp[0])
Your text to link here...

variety-jones

Take a look at Ticket 16891 from CF Stress for a counter example.

thanks

BuzzyBeez

I have a different and quite interesting approach for problem C.

Wanted to use $$$1-n$$$ loops so $$$s$$$ = " " + $$$s$$$

First, if we modify the $$$i-th$$$ character of string $$$s$$$, the result when calculating all characters of $$$s$$$ to the right of $$$i$$$ does not change. Therefore it can be precalculated (for briefness, I assume we store these in an array called $$$sfsum$$$). $$$(1)$$$

We can also precalculate the max character of every suffix of string s in an array (for briefness, I call it $$$sfmax$$$). In calculation, the $$$i-th$$$ character will have a negative sign if $$$i$$$ < $$$sfmax[i + 1]$$$ ($$$sfmax[n + 1]$$$ = $$$0$$$), otherwise it will have a positive sign. $$$(2)$$$

Let $$$cnt$$$ be an array such that $$$cnt[c][i]$$$ is the number of times (char)($$$c$$$ + 'A') appears in $$$s.substr(1, i)$$$. Defining the "practical" value of character $$$c$$$ in string $$$s$$$: Consider the calculating process of $$$s$$$; for every negative sign of c, -1 from that value and for every positive sign we add 1. Let $$$value$$$ be an array such that $$$value[c][i]$$$ is the "practical" value of (char)($$$c$$$ + 'A') in $$$s.substr(1, i)$$$. $$$(c: 0-4)$$$ $$$(3)$$$

From (3) we can see that the ranom value of string $$$s$$$ of length $$$x$$$ (using its $$$value$$$ array) is $$$value[0][x] + value[1][x]*10 + value[2][x]*1e2 + value[3][x]*1e3 + value[4][x]*1e4$$$. $$$(4)$$$

$$$(1)(2)(3)(4)$$$

Let $$$ans$$$ be the answer. For every $$$i-th$$$ character of $$$s$$$, we can quickly calculate the ranom value of the new string if we modify it:

Let $$$c: 0-4$$$ be the new value of that character, then let $$$tmp$$$ be the new ranom value.

If $$$(c >= sfmax[i + 1])$$$, $$$tmp$$$ = 10^$$$c$$$; else $$$tmp$$$ = -(10^$$$c$$$). $$$tmp$$$ += $$$sfsum[i + 1]$$$ (not affected part)

For $$$ch: 0-4$$$ (considering every character $$$'A' - 'E'$$$)

If ($$$ch >= c$$$ and $$$ch >= sfmax[i + 1]$$$) $$$tmp$$$ += $$$value[ch][i - 1]$$$ (this character is >= every character to $$$s[i]$$$'s right so its practical value for $$$s$$$ = its practical value for $$$s.substr(1, i)$$$)
Else $$$tmp$$$ -= $$$cnt[ch][i - 1]$$$ (there is a larger character than this to the right of $$$s[i]$$$ in $$$s$$$)

Then we just update $$$ans = max(ans, tmp)$$$

Implementation: My Code

Pls tell me if im wrong :D

Edit: How to precalculate $$$value$$$:

For every $$$c: 0 - 4$$$:

For $$$i: 1 - n$$$:

If ($$$s[i] - 'A' == c$$$) $$$value[c][i] = value[c][i - 1] + 1$$$ ($$$s[i]$$$ is last character of current substring so +1)
If ($$$s[i] - 'A' > c$$$) $$$value[c][i] = -cnt[c][i]$$$ (last character of current substring >= $$$c$$$ so every time $$$c$$$ appears, $$$value[c][i]$$$--)
Else $$$value[c][i] = value[c][i - 1]$$$ (nothing happened)

transfermarket

The gap between B and C are too big, make the round speedforces for people < expert.

Ahmed_Solyman

In problem C, my solution is segment tree, but there isn't data structures tag, Can anyone add it ? this is my solution : 209477665

dzhi

The time limit of 1 second is too tight for problem F, at least for Java language.

Math.atan2(y,x) is convenient to get the angle of (x,y) in polar coordinate yet it is too expensive to be used for n = 300000 test case.
BigInteger is convenient to represent the square sum precisely yet it is too expensive to be used for n = 300000 test case, so double is used instead.
Precompute y/x ratio for points in each quadrant is necessary to sort them in angle order (compute each ratio long(n) times lead to TLE).
The tight limit also forbit other variants of solutions that are essentially the same idea and complexity.

The main risk to have a very tight time limit is it rejects otherwise reasonable solutions that deviates from the tutorial one in some perspective, or code that are otherwise more intuitive and readable, which are important in software development.

Reference: https://codeforces.net/contest/1841/submission/209905657

NotShek

D can be solved in O(nlog) using rmq

sort segment by right border
keep the maximum left border of range [i, i + 2^j) in an array
update dp (dp[i] means minimum answer with fixing i-th segment)

code

MickeyIsAwesome

There is O(nlogn) solution for 1841D - Пары отрезков, without using any RMQ or DP.

Basically just sort the segments by right end increasing order, and then left end decreasing.

Now iterate over these segments, and keep track of two end points. First is the end point of rightmost segment, that is not intersecting with any other ( one_end in my code). Second is the end point of rightmost intersecting segment ( r_end in my code).

Whenever any segment's left end is intersecting the r_end, we can discard it. Or, if we find a segment that is not intersecting even with one_end, then we can update one_end and discard this segment, as we only allow pairs of intersecting segments.

After exiting loop, if one_end remains, then add that segment also to discarded.

Just print no. of discarded segments.

My solution -> 210253422

Jetri

I am unable to understand solution of D. Why do we need to sort the vector of unions based on second element of pair?? Can't we do it by general method of sorting.

saturnbored

Greedy: Taking the current segment if it doesn't intersect with the last segment which we picked.

When the segments are sorted by their endpoints, we can be sure that this greedy will work, because as we traverse through the array of segments (from left to right), we can say that leaving the current segment and picking any subsequent one will never be better. (Why? because the endpoint of any subsequent segment will be greater than the current segment, and hence it would possibly intersect with more segments than the current segment). Thus every time we encounter a segment that doesn't intersect with the last picked one, we can simply select it and get the correct answer.

Now, to answer your question: You can sort the points by the general method (by their starting points) as well, but then, you would have to traverse the array from right to left, (Why? reason similar to the above explanation). This works. Accepted Submission

GreenKitty

I writed N * logN solution for problem 1841D instead of N^2 * logN :)

esr6vqa

Without knowing about Minkowski sums, F can be solved using a sliding (or rotating) window:

One can show that the optimal vector sum has positive dot product to all its terms, and negative dot product to every vector not in the sum. Thus the optimal sum induces a half-space on the plane from which the component vectors can be recovered. Then the problem reduces to finding this half-space, or at least the vectors that lie inside it. This can be accomplished (after sorting vectors by angle) by sweeping out the plane.

Submission: https://codeforces.net/contest/1841/submission/210833986

luicosas

Thanks so much for the code! Finally succeeded after debugging for 2 days.

Some more information for others wanting to write the sliding window solution:

There's one tricky edge case when expanding the window to cover half of the plane. If the code is written by expanding the window [i, j) by comparing if j is 180 degree from i we might accidentally pick up vectors with same direction as i. But when we increase i, those vectors will not be in the same half plane as the new i.

submission

jophyyjh

Can anyone help check out what's wrong with my submission to problem D? It feels like a quite straightforward problem, but I'm unable to find what's wrong... https://codeforces.net/contest/1841/submission/210784413

shashankag

Can anyone tell what's wrong with this submission — https://codeforces.net/contest/1841/submission/211982826

I have use simple dp approach where dp[I][j] is the answer when ith char is replaced with j..

Hridoy23

16 months ago, # |

Problem D can be solve with O(nlogn) time. Solution

harryb17

Problem D — Pair of Segment: Nlog(N) solution.

concise and straightforward solution using Segment Tree, UpperBound on a sorted array, and Dynamic Programming. Used segment tree to find the minimum element in a range and the central concept is only based on 1D dynamic programming.

Problem D solution

the concept involves only 2 states you delete the current element and save the answer as dp[i+1] + 1 or, keep the current element, and then choose the most optimal intersecting element, and delete the rest the state will be j-i-2 + dp[j], where j is the index of closest element not intersecting both the current element, and the chosen optimal element, which will pair with the current element. Note: the chosen optimal element will be the intersecting element with the least [Ri]. cause this provides the least chance of it intersecting other elements.

xxxodarap

15 months ago, # |

I adapted the sample solution for F and replaced the __int128 and pairs of ll with (long) double. However, now i always get TLE in test case 18.

Here is my code: https://codeforces.net/contest/1841/submission/217939111

The original solution (which gets accepted perfectly fine) is this: https://codeforces.net/contest/1841/submission/217939364

The problem is the sorting step. But it should be possible to solve this task with floating point values, right?

So does anyone have an idea?

This submission here works perfectly fine: https://codeforces.net/contest/1841/submission/217941363

This new solution does not use cmp_ang() for sorting, but cmp_ang2(). The Problem is really the call to arg() (which also just calls atan2()). I replaced it with another ... more complex way of comparing the angles and afterwards rotating it (probably the rotation can be eliminated with a slight variation as compare function).

However what remains to be answered is: why is atan2 so slow???

abhaasaggarwal

In question D I think I have also done something similar but my solution: https://codeforces.net/contest/1841/submission/218822785 is showing wrong answer on test 5.... could someone point out the faulty logic? I am basically sorting all given pairs in ascending order and then checking each element to see if a union can be taken with the next one... if so I am considering that pair and since its sorted vector I'm indirectly also making sure that the same pair doesn't get included in more than at max 1 pair of pairs by setting the current check (l) to max of upper limits of a chosen pair.

AlokKT105

Someone please tell me what is wrong in my code for problem C — code

I have written my approach inside the code. And my code should be easily understandable. I am stuck on this problem till now. It would be great if anyone of you could help me debug it.

Nevermind, found the mistake.

yusuf12360

14 months ago, # |

i have the [problem:1841D] i have the O(n log n) solution : 226512501

for problem 1841D - Пары отрезков your complexity is too long time man, i have the O(n log n) solution : 226512501

tr1ten

Problem D should be O(nlogn) using dp, right? code

aks_332

10 months ago, # |

MyCode

#include "bits/stdc++.h"
using namespace std;
#define int long long
map<int,int> m2;
int dp[200001][5][2];
int solve(int i, char maxi, int count,string &s){
    if(i<0) return 0;
    if(dp[i][(int)maxi-65][count]!=-1){
        return dp[i][(int)maxi-65][count];
    }
    if(count!=0){
        int ans=0;
        for(char ch='A';ch<='E';ch++){
            int a,b,c=0;
            a=b=c=0;
            if(ch==s[i]){
                if(ch<maxi){
                    a=-1LL*m2[ch]+solve(i-1,maxi,count,s);
                }
                else{
                    a=m2[ch]+solve(i-1,max(s[i],maxi),count,s);
                }
            }
            else if(ch<maxi){
                a=-1LL*m2[ch]+solve(i-1,maxi,count-1,s);
            }
            else{
                a=m2[ch]+solve(i-1,ch,count-1,s);
            }
            // cout<<i<<" "<<a<<" "<<b<<" "<<c<<" "<<endl;
            ans=max(a,ans);
        }
        return ans;
    }
    else{
        int ans=0;
        if(s[i]>=maxi){
            ans=m2[s[i]]+solve(i-1,max(s[i],maxi),count,s);
        }
        else{
            ans=-1LL*m2[s[i]]+solve(i-1,maxi,count,s);
        }
        return ans;
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        
        m2['A']=1;
        m2['B']=10;
        m2['C']=100;
        m2['D']=1000;
        m2['E']=10000;
        for(int i=0;i<s.size();i++){
            for(int j=0;j<5;j++){
                for(int k=0;k<2;k++){
                    dp[i][j][k]=-1;
                }
            }
        }
        cout<<solve(s.size()-1,'A',1,s)<<endl;
       
        
    }
}

This is my code for question C I got WA on test case 3. I tried it to debug but coudn't find any error. Can anyone help me to bebug it.

brave-kid

6 months ago, # |

I solved $$$D$$$ with dp $$$O(N^2)$$$ solution — submission

unknown_7

5 months ago, # |

can someone please help me in E?

https://codeforces.net/contest/1841/submission/264751745

I am getting wrong answer of 6320th case in test case 2.

captainburkinafaso

I have a much faster solution for question D. While the tutorial solution took 186 ms in the worst test case, my solution only took 46 ms. Solution To Question D

kinitic013

4 months ago, # |

Hey can anyone figure out what's wrong in the trasition equation for this problem C

Code

    vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(5,vector<ll>(2,-1e18)));
    dp[0][arr[0]-'A'][0] = f[arr[0] - 'A'];
    // REP(i,0,5)
    // {
    //     dp[0][i][1] = f[i];
    // }
    REP(i,0,n)
    {
        REP(k,0,2)
        {
            REP(j,0,5)
            {
                ll not_choosen = -1e18;
                {
                    if(arr[i] - 'A' == j)
                    {
                        REP(l,0,j+1)
                        {
                            ll val = 0;
                            if(i-1>=0)
                            val = dp[i-1][l][k];

                            not_choosen = max<ll>(not_choosen , val + f[j]);
                        }
                    }
                    else
                    {
                        ll val = 0;
                        if(i-1>=0)
                        val = dp[i-1][j][k];

                        not_choosen = max<ll>(not_choosen , val - f[arr[i]-'A']);
                    }
                }
                dp[i][j][k] = max<ll>(dp[i][j][k] , not_choosen);
                ll choosen = -1e18;
                if(k>=1)
                {
                    {
                        REP(l,0,j+1)
                        {
                            ll val = 0;
                            if(i-1>=0 && k-1>=0)
                            val = dp[i-1][l][k-1];

                            choosen = max<ll>(choosen , val + f[j]);
                        }
                    }
                }
                dp[i][j][k] = max<ll>(dp[i][j][k],choosen);
                debug(i,j,k,dp[i][j][k],not_choosen,choosen);
            }
        }
    }
    debug(dp);

    ll ans = -1e18;
    REP(i,0,5)
    {
        ans = max(ans,max(dp[n-1][i][0],dp[n-1][i][1]));
    }
    cout<<ans;
}

WA testcase

1
DEEDAADCABDCCCBBADBAAADDDADDADABEBB

Optimal : 29560
MyAnswer : 29580

vasuganesha1

3 months ago, # |

Solution to problem D Link

awoo's blog