Educational Codeforces Round 156 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Tutorial

Solution (fcspartakm)

#include <bits/stdc++.h>

using namespace std;

int n;

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

inline void solve() {
	for (int x = 1; x <= 20; x++) {
	    for (int y = 1; y <= 20; y++) {
	        if (x + y >= n || x == y) continue;
	        int z = n - x - y;
	        if (z == x || z == y) continue;
	        if (x % 3 == 0 || y % 3 == 0 || z % 3 == 0) {
	            continue;
	        }
	        puts("YES");
	        cout << x << ' ' << y << ' ' << z << endl;
	        return;
	    }
	}
	puts("NO");
}

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

1886B - Fear of the Dark

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  auto dist = [](int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  };
 
  int t;
  cin >> t;
  while (t--) {
    int px, py, ax, ay, bx, by;
    cin >> px >> py >> ax >> ay >> bx >> by;
    double pa = dist(px, py, ax, ay), pb = dist(px, py, bx, by);
    double oa = dist(0, 0, ax, ay), ob = dist(0, 0, bx, by);
    double ab = dist(ax, ay, bx, by);
    double ans = 1e9;
    ans = min(ans, max(pa, oa));
    ans = min(ans, max(pb, ob));
    ans = min(ans, max({ab / 2, pa, ob}));
    ans = min(ans, max({ab / 2, pb, oa}));
    cout << setprecision(10) << fixed << ans << '\n';
  }
}

1886C - Decreasing String

Idea: Roms

Tutorial

Solution (Roms)

#include <bits/stdc++.h>

using namespace std;

const int N = 200000;

int t;

int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        string s;
        long long pos;
        cin >> s >> pos;
        --pos;
        
        int curLen = s.size();
        vector <char> st;
        bool ok = pos < curLen;
        s += '$';
        
        for (auto c : s) {
            while (!ok && st.size() > 0 && st.back() > c) {
                pos -= curLen;
                --curLen;
                st.pop_back();
                
                if(pos < curLen) 
                    ok = true;
            }
            st.push_back(c);
        }
        
        cout << st[pos];
    }
    return 0;
}

1886D - Monocarp and the Set

Idea: Roms

Tutorial

Solution (Roms)

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

const int N = 300009;

int bp(int a, int n) {
    int res = 1;
    while(n > 0) {
        if (n & 1)
            res = (res * 1LL * a) % MOD;
        a = (a * 1LL * a) % MOD;
        n >>= 1;
    }
    return res;
}

int n, m;
string s;
int inv[N];

void upd(int &res, int x) {
    res = (res * 1LL * x) % MOD;
}

int main() {
    inv[1] = 1;
    for (int i = 2; i < N; ++i){
	    inv[i] = bp(i, MOD - 2);
    }
    
    cin >> n >> m >> s;
    
    int res = 1, k = n;
    bool isZero = false;
    for (int i = 0; i < s.size(); ++i) 
        if (s[i] == '?') {
            if (i == 0) {
                isZero = true;
            } else {
                upd(res, i);
            }
        }
    
    cout << (isZero? 0 : res) << endl;
    
    for(int i = 0; i < m; ++i) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        
        if (s[pos] == '?' && (c == '<' || c == '>')) {
            if (pos == 0)
                isZero = false;
            else
                upd(res, inv[pos]);
        } else if ((s[pos] == '<' || s[pos] == '>') && c == '?') {
            if (pos == 0)
                isZero = true;
            else
                upd(res, pos);
        }
        
        s[pos] = c;
        cout << (isZero? 0 : res) << endl;
    }
    return 0;
}

1886E - I Wanna be the Team Leader

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> a(n), b(m);
	forn(i, n) scanf("%d", &a[i]);
	forn(i, m) scanf("%d", &b[i]);
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&a](int i, int j){
		return a[i] > a[j];
	});
	vector<vector<int>> mn(m, vector<int>(n + 2));
	forn(i, m){
		int r = 0;
		forn(l, n + 2){
			r = min(n + 1, max(r, l + 1));
			while (r <= n && a[ord[r - 1]] * (r - l) < b[i]) ++r;
			mn[i][l] = r;
		}
	}
	vector<int> dp(1 << m, n + 1);
	dp[0] = 0;
	vector<int> p(1 << m, -1);
	forn(mask, 1 << m) forn(i, m) if (!((mask >> i) & 1) && dp[mask | (1 << i)] > mn[i][dp[mask]]){
		dp[mask | (1 << i)] = mn[i][dp[mask]];
		p[mask | (1 << i)] = mask;
	}
	int mask = (1 << m) - 1;
	if (dp[mask] > n){
		puts("NO");
		return 0;
	}
	puts("YES");
	vector<vector<int>> ans(n);
	forn(_, m){
		int i = __builtin_ctz(mask ^ p[mask]);
		for (int j = dp[p[mask]]; j < dp[mask]; ++j)
			ans[i].push_back(ord[j]);
		mask = p[mask];
	}
	forn(i, m){
		printf("%d", int(ans[i].size()));
		for (int x : ans[i]) printf(" %d", x + 1);
		puts("");
	}
	return 0;
}

1886F - Diamond Theft

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3003;
 
int n;
int k[4];
vector<int> a[4];
 
struct segtree {
  int sz;
  int tot;
  vector<int> t, p;
  
  segtree(int sz) : sz(sz) {
    tot = 0;
    t = vector<int>(4 * sz);
    p = vector<int>(4 * sz);
    build(0, 0, sz);
  }
  
  void build(int v, int l, int r) {
    if (l + 1 == r) {
      t[v] = -l;
      return;
    }
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void push(int v) {
    if (p[v] == 0) return;
    if (v + 1 < 2 * sz) {
      t[v * 2 + 1] += p[v];
      p[v * 2 + 1] += p[v];
      t[v * 2 + 2] += p[v];
      p[v * 2 + 2] += p[v];
      p[v] = 0;
    }
  } 
  
  void upd(int v, int l, int r, int L, int R, int x) {
    if (L >= R) return;
    if (l == L && r == R) {
      t[v] += x;
      p[v] += x;
      return;
    }
    push(v);
    int m = (l + r) / 2;
    upd(v * 2 + 1, l, m, L, min(m, R), x);
    upd(v * 2 + 2, m, r, max(L, m), R, x);
    t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  }
  
  void upd(int pos, int x) { 
    tot += x;
    upd(0, 0, sz, max(0, pos), sz, x);
  }
  
  int get(int v, int l, int r, int L, int R) {
    if (L >= R) return -1e9;
    if (l == L && r == R) return t[v];
    push(v);
    int m = (l + r) / 2;
    return max(
      get(v * 2 + 1, l, m, L, min(m, R)),
      get(v * 2 + 2, m, r, max(L, m), R)
    );
  }
  
  int get(int L) {
    return get(0, 0, sz, max(0, L), sz);
  }
  
  int getBad(int v, int l, int r) {
    if (t[v] <= 0) return -1;
    if (l + 1 == r) return l;
    push(v);
    int m = (l + r) / 2;
    if (t[v * 2 + 1] > 0) {
      return getBad(v * 2 + 1, l, m);
    } else {
      return getBad(v * 2 + 2, m, r);
    }
  }
  
  int getBad() {
    return getBad(0, 0, sz);
  }
};  
 
int main() {
  cin >> n;
  int sz = 1;
  for (int i = 0; i < n; ++i) {
    int t, s;
    cin >> t >> s;
    a[t].push_back(s);
    sz = max(sz, s + 1);
  }
  for (int t = 1; t < 4; ++t) {
    sort(a[t].begin(), a[t].end());
    k[t] = a[t].size();
  }
  reverse(a[2].begin(), a[2].end());
  int ans = 1e4;
  for (int len = 1; len <= k[2] + k[3] + 1; ++len) {
    segtree L(sz), R(sz);
    multiset<int> used;
    for (int x : a[1]) L.upd(x, +1);
    for (int x : a[2]) R.upd(x, +1);
    for (int x : a[3]) {
      L.upd(x - len, +1);
      if (L.t[0] <= 0) {
        used.insert(x - len);
      } else {
        L.upd(x - len, -1);
        L.upd(x, +1);
        R.upd(x, +1);
      }
    }
    for (int i = 0; i <= k[2]; ++i) {
      if (L.t[0] <= 0 && R.t[0] <= 0 && R.tot + 1 <= len)
        ans = min(ans, n + (k[3] - (int)used.size()) + 2); 
      if (i == k[2]) break;
      R.upd(a[2][i], -1);
      L.upd(a[2][i] - len, +1);
      int pos;
      while ((pos = L.getBad()) != -1) {
        auto it = used.upper_bound(pos);
        if (it == used.begin()) break;
        --it;
        L.upd(*it, -1);
        L.upd(*it + len, +1);
        R.upd(*it + len, +1);
        used.erase(it);
      }
    }
  }
  if (ans == 1e4) ans = -1;
  cout << ans << '\n';
}

// checks if point is inside circle bool check(pair<float, float> circle, pair<float, float> point, float w){ return ((circle.first - point.first) * (circle.first - point.first) + (circle.second - point.second) * (circle.second - point.second)) <= w * w; } //checks if circles A and B are touching bool istouch(pair<double, double> a, pair<double, double> b, double w){ return w + w >= ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); } //checks if the radius is a valid answer bool isok(pair<float, float> b, pair<float, float> p, pair<float, float> o, pair<float, float> a, float w){ return (check(b,o,w) & check(b,p,w) | (check(a,o,w) & check(a,p,w))) | (check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w)); } double WORST = 3e3f; double EPS = 1e-6f; void solve(){ pair<float, float> p, a, b, o; cin >> p.first >> p.second; cin >> a.first >> a.second; cin >> b.first >> b.second; o = make_pair(0.0f, 0.0f); double l = 0.0f, r = WORST; double w = r; //binary searching the answer starts from here while(r - l > EPS){ double mid = (l + r)/2; if(isok(b,p,o,a,w)){ w = mid; r = mid; } else { l = mid; } // cout << l << " " << r << "\n"; } cout << w << "\n"; }

/* solve.cpp * solution to problem X */ #include <bits/stdc++.h> #include <iostream> using namespace std; int solver(string s, long long pos) { long long L = s.length(); // quadratic equation to find length of x. // x - the length of the substring of the solution. long long x = floor((1 + sqrt(1 + 4 * (pow(L, 2) + L - 2 * pos))) / 2); // xb - the index of the beginning of substring x long long xb = (pow(L, 2) + L - pow(x, 2) + x) / 2 - x; // xi - the index in the substring x of the solution. long long xi = pos - 1 - xb; // cout << "*** x: " << x << " xi : " << xi << "\n"; long long i = 0; long long erased = 0; while (L - erased > x) { // what to do before getting to the end of the string if (i + 1 <= L - erased) { char curr = s[i]; char next = s[i + 1]; if (curr > next) { s.erase(i, 1); erased++; if (i > 0) i--; } else { i++; } } // at the end of the string else { s.erase(i, 1); erased++; i--; } } // Print result. cout << s[xi]; return 0; } int main() { int numTests; cin >> numTests; while (numTests--) { string s; int pos; cin >> s >> pos; solver(s, pos); } return 0; }

Comments (47)

Show archived | Write comment?

Ramtin510

13 months ago, # |

amazing round loved it

→ Reply

sam86_b

Just become expert again Amazing contest

Mehrad2

13 months ago, # ^ |

← Rev. 2 →

-13

basiji good for you i hope goods

saman2221

oh my god is he basiji ?

yes

itachi__1406

What will be the expected difficulty for problem B it seems bit tough compared to other div 2 B Questions

a1abay

No it is pretty balanced. You need to know basic geometry and/or binary search

KOD_TiTAN

9 months ago, # ^ |

I thought of using binary search at first, on w but w is floating point number. so how can we apply binary search on it can you please elaborate.

-37

Thanks for slow editorial!

sidakbhatia

Div2 D Alternate explanation:

Consider ?<??>?>??

Observation : Last > will be n and last < be 1

This is always true. If 1 and n are always in the permutation could there be a > after n and < after 1? No. If there aren't any such symbols for either > or < they will be in 1st position .

However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent <s after last < also be 2,3,4.....?

The answer is No.

This is because we have ?s after last > and last < respectively. There we could put values So that we could form a decreasing sequence from n ( > > >) and an increasing sequence from 1 (< < <). There could be many such sequences clearly.

Now let's propose an algorithm,

?<??>?>??

Starting from the back we have n-2 choices where n is number of els in the set. This is because only the minimum(1) and maximum(N) is fixed. Now remove last element.

?<??>?>? again n-2 choices where n is number of els in the set.

?>??>?>

1 choice last > is fixed. Similarly last < is fixed.

?>??>? now last > is the max el in the set. We remove 2 els and N so far. Irrespective of our choices for the 2 els, there will be 1 unique maximum in the set which will take place of last >. So for ? we have n-2 choices again where n is number of els in the set.

Hope you get the solution.

elizabeth_zou_fanboi

"However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent <s after last < also be 2,3,4.....?

The answer is No."

I made this wrong assumption and was wondering why my solution is wrong! Thanks for this. I never would have realised why my solution is wrong( This happens a lot to me, I make wrong assumptions and get to a wrong solution but I never find that wrong assumption on my own, and usually some other person points it out for me. I need to work on this by embracing the Sherlock's quote : "When you have eliminated the impossible, whatever remains, however improbable, must be the truth"

amuse

I don't understand why my solution for C didn't work. It passed the first test case fine, and was very similar to the expected output for the second testcase, so I was wondering where I went wrong.

Banis

The fifth character is different.

DinarPerseus

Problem C. Decreasing String ***** In this problem test number 2 in test case 5. The string is given "pbdtm" and the POS=8 If I select s1=pbdtm s2=pbdm s3=bdm s4=bd s5=b The condition is still right. Because s1>s2>s3>s4>s5 And the POS value of 8 is 'd'.. But why this is wrong answer?

vgtcross

$$$s_2 = \tt{bdtm}$$$, not $$$\tt{pbdm}$$$

moghit_ad

i'm having same problem just wondering why ( s1= pbdtm -> s2 = pbdm )is not valid ???

The problem statement says that we always need to make the next string lexicographically minimal.

From $$$\tt{pbdtm}$$$ we could go to $$$\tt{pbdt}$$$, $$$\tt{pbdm}$$$, $$$\tt{pbtm}$$$, $$$\tt{pdtm}$$$ or $$$\tt{bdtm}$$$. The lexicographically smallest one of these is $$$\tt{bdtm}$$$.

We cannot go to $$$\tt{pbdm}$$$, since $$$\tt{bdtm}$$$ is lexicographically smaller.

Got it ! , thanks man

Siranticorz

Great idea for E, thanks a lot for the wonderful contest :)

FL_sleake

You can also solve problem B by binary search. By the way, problem c editorial is great,thanks:).

nikhilreddygudi

8 months ago, # ^ |

I tried to solve it using binary search 247760061, but getting a TLE though. can someone please help me figure out why?

Change while to for(int i=1;i<=200;i++) and set high to 1e9 and you'll pass this question!

Thanks. It worked 248056414.

So, was that because there will be so many real values between the extremes?

And we are can get to an approximate value in < 200 iterations?

I think it's possible that the way your code is written could have some precision issues causing it to get stuck in a dead loop. In fact, we would halve the search each time, and even 100 searches would be enough to achieve the precision needed for the question.

(I'm sorry my English is not good, the above is the result of using a translator, I hope you can read it:)

Yeah, got that man.

Thanks, I was able to read through.

deydhananjoy5

Nice editorial

palsatyam877

Awesome Editorial and Problem set.

ashueep

Can someone help me with understanding my solution to B more clearly? I tried using binary search by answer here. I felt it was a plausible solution since if a radius (say r) is an answer then all radiis > r are also the answer. I tried implementing some solution, didnt work, maybe my impl on binary searching for real answers suck. Help/Correction appreciated!

Soultaker

+10

In theory binary search should be possible here, even if I don't think it makes the problem easier to solve than the direct solution.

Problem 1: istouch() is wrong. You need to square the distance at the left-hand side (as you do in check()), or take the square root of the righthand side (hypot() is useful here).

Problem 2: isok() is wrong. You need to check four possible paths: O->A->P, O->B->P, O->A->B->P, and O->B->A->P. The first two subexpressions (check(a,o,w) & check(a,p,w) and check(b,o,w) & check(b,p,w)) cover the first two possibilities. The third expression doesn't really work. instead of check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w) you need something like (check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w)) & istouch(a,b,w) (note the different places of the parentheses!)

(Also, generally don't use & and | for Boolean logic. Use the proper Boolean operators && and || instead. But that's not causing any bugs in this case.)

can you please help me with my submission too 247760061

For problem E, I was able to squeeze in what I think is an $$$O(m \times 2^m \times \sqrt{n})$$$ solution that doesn't precompute the number of programmers needed to satisfy a project: 227729256

Not sure if this was intended to pass or not!

eatfood

For Problem F, the editorial states that when "when you move a camera of type 2 to the first block, it can force multiple cameras of type 3 into the second block". I'm unable to see why this is true.

It seems to me that from the way we pick the camera of type 3, after a single move, it will fix all the $$$x$$$ which have $$$d_x - x > 0$$$. Because after moving the camera of type 2 from block2 to block1, we might cause several indices to have $$$d_x - x = 1$$$ (and not any value higher than $$$1$$$), which can be fixed by a single camera move.

BledDest

← Rev. 4 →

+12

Good question, it was one of our main points of concern while designing the solution (we weren't sure if it is necessarily to change the positions of multiple cameras of type $$$3$$$). This is because, when you move a camera of type $$$2$$$, it increases $$$d_x$$$ by $$$1$$$ on some suffix of values. But when you "move" a camera of type $$$3$$$, it actually stays in the first block (we still have to hack it before stealing the first diamond). It just has a bigger range of possible positions. So, it decreases $$$d_x$$$ on some suffix, but increases $$$d_x$$$ back on some shorter suffix (i. e. it just decreases $$$d_x$$$ by $$$1$$$ on one subsegment, not on the whole suffix). If there are multiple points where $$$d_x - x$$$ became positive after we moved a camera of type $$$2$$$, some of them might be outside that affected segment.

Wmic.

In F why "if we skipped some camera which could be inserted into the first block, and chose some other camera for the same slot, they can be "swapped". " is right?

I think if we first insert the camera which $$$s_i$$$ is small and then insert the camera which $$$s_i$$$ is big,for the second block it is greater,but for the first block it is not greater than we first insert the bigger one.

← Rev. 3 →

+20

Suppose we already placed cameras of type $$$1$$$ and $$$2$$$, and try to place cameras of type $$$3$$$. Why is it always optimal to do it in non-descending order of $$$s_i$$$, and place a camera only in the first block (instead of placing it in both) whenever possible?

Suppose we fixed an optimal placement of cameras, and it differs from the one produced by that greedy algorithm. Let's fix the first (in sorted order) camera $$$i$$$ that would be placed in the first block by the greedy algorithm, but is not placed there by the optimal solution.

There should be a moment of time (some $$$x$$$ seconds before stealing the first diamond) where we would place that camera $$$i$$$ in the first block in the greedy solution. So, the condition $$$s_i \ge x + len$$$ must hold. If there's no camera of type $$$3$$$ occupying that moment, then we just place that camera $$$i$$$ there and remove it from the second block.

If there is such a camera, suppose its index is $$$j$$$. We can show that if we place the camera $$$j$$$ in both blocks, and the camera $$$i$$$ in the first block only, nothing will break: we can place the $$$j$$$-th camera in both moments of time occupied by the $$$i$$$-th camera, and the $$$i$$$-th camera in the slot of the $$$j$$$-th camera:

since $$$s_j \ge s_i$$$, the position for the $$$i$$$-th camera in the first block is suitable for the $$$j$$$-th camera;
since $$$s_j \ge s_i$$$, the position for the $$$i$$$-th camera in the second block is suitable for the $$$j$$$-th camera;
$$$s_i \ge s_j$$$ does not necessarily hold, so it might be possible that the slot occupied by the $$$j$$$-th camera is unsuitable for the $$$i$$$-th camera. But remember that the greedy algorithm would place the $$$i$$$-th camera in the time slot occupied by the $$$j$$$-th camera, so the condition $$$s_i \ge len + x$$$ holds. So, that slot is suitable for the $$$i$$$-th camera.

By repeating this process enough times, we can transform the optimal solution to the solution produced by the greedy approach, and nothing breaks.

Thanks very much!

ajCoder

Can anyone help me to find why is it wrong in th case 16 of the problem E: https://codeforces.net/contest/1886/submission/228496275

10000point

Obviously, the programmers that you finally choose are the biggest ones, so you should sort them decreasingly instead of increasingly before DP. Otherwise it means that you assumed choosing the smallest one, making it not optimal sometimes.

e.g.

2 1

1 3

Thank you so much!

Nandy255

Hi, can anyone explain for D, (TestCase 1, before all queries.)why the permutation 2, 1, 3, 5, 4, 6 is not possible ?

Maybe I am missing something, but the sequence is <?>?>

Vanjanja

when you add 3, it becomes maximum so it shouldn't be a question mark, but rather a '>'

Oh, I see now. Thank you Vanjanja.

jacoby149

11 months ago, # |

For C, I did an answer using the quadratic equation that avoids data structures, but it has a runtime error on test 8, don't know why :(

CoffeeMachine100

for question C you should put a hint (use a stack) as only knowing this information made me solve it

overall, good question and perfect tutorial thanks

wackyIndian

10 months ago, # |

In problem $$$C$$$, I was wondering what if we had some $$$Q$$$ queries, where each query is asking the character at queried position and length of string as ($$$N < 10^6$$$).

Any ideas on how we will go about it, like what information do we need to store ?
Or should the constraints be reduced ?
Like any approach for this so called Bonus problem ?

Roms

dux3t

8 months ago, # |

Another approach for problem A which is more concise 248334395

awoo's blog