Educational Codeforces Round 138 Editorial

#	User	Rating
1	tourist	3751
2	Benq	3727
3	cnnfls_csy	3691
4	Radewoosh	3651
5	jiangly	3632
6	orzdevinwang	3559
7	-0.5	3545
8	inaFSTream	3478
9	fantasy	3468
10	Rebelz	3415

#	User	Contrib.
1	adamant	178
2	awoo	167
3	BledDest	165
4	Um_nik	164
5	maroonrk	163
6	SecondThread	160
7	nor	157
8	-is-this-fft-	154
9	kostka	146
10	Geothermal	144

Tutorial

Solution 1 (awoo)

for _ in range(int(input())):
    n, m = map(int, input().split())
    for _ in range(m):
        input()
    print("NO" if n == m else "YES")

Solution 2 (awoo)

#include <bits/stdc++.h>

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

using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    forn(_, t){
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, int>> a(m);
        forn(i, m){
            scanf("%d%d", &a[i].first, &a[i].second);
            --a[i].first, --a[i].second;
        }
        bool ans = false;
        forn(i, m) forn(x, n) forn(y, n) if ((x == a[i].first) ^ (y == a[i].second)){
            bool ok = true;
            forn(j, m) if (i != j){
                ok &= x != a[j].first && y != a[j].second;
            }
            ans |= ok;
        }
        puts(ans ? "YES" : "NO");
    }
}

1749B - Death's Blessing

Idea: BledDest

Tutorial

Solution (adedalic)

fun main() {
    repeat(readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val a = readLine()!!.split(' ').map { it.toLong() }
        val b = readLine()!!.split(' ').map { it.toLong() }

        println(a.sum() + b.sum() - b.maxOrNull()!!)
    }
}

1749C - Number Game

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int ans = 0;
    for (int k = 1; k <= n; ++k) {
      multiset<int> s(a.begin(), a.end());
      for (int i = 0; i < k; ++i) {
        auto it = s.upper_bound(k - i);
        if (it == s.begin()) break;
        s.erase(--it);
        if (!s.empty()) {
          int x = *s.begin();
          s.erase(s.begin());
          s.insert(x + k - i);
        }
      }
      if (s.size() + k == n) ans = k;
    }
    cout << ans << '\n';
  }
}

1749D - Counting Arrays

Idea: BledDest

Tutorial

Solution (BledDest)

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

const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}   

int sub(int x, int y)
{
    return add(x, -y);
}   

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

bool prime(int x)
{
    for(int i = 2; i * 1ll * i <= x; i++)
        if(x % i == 0)
            return false;
    return true;    
}

int main()
{
    int n;
    long long m;
    cin >> n >> m;
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans = add(ans, binpow(m % MOD, i));
    long long cur = 1;
    int cnt = 1;
    for(int i = 1; i <= n; i++)
    {
        if(cur > m) continue;
        if(prime(i)) cur *= i;
        cnt = mul(cnt, (m / cur) % MOD);
        ans = sub(ans, cnt);
    }
    cout << ans << endl;
}

1749E - Cactus Wall

Idea: BledDest

Tutorial

Solution (Neon)

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, -1, 1, -1, 1};

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<string> s(n);
    for (auto &it : s) cin >> it;
    
    auto in = [&](int x, int y) {
      return 0 <= x && x < n && 0 <= y && y < m;
    };
    
    auto can = [&](int x, int y) {
      if (!in(x, y)) return false;
      for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (in(nx, ny) && s[nx][ny] == '#')
          return false;
      }
      return true;
    };
    
    vector<vector<int>> d(n, vector<int>(m, INF)), p(n, vector<int>(m));
    deque<pair<int, int>> q;
    for (int i = 0; i < n; ++i) {
        if (s[i][0] == '#') {
          d[i][0] = 0;
          q.push_front({i, 0});
        } else if (can(i, 0)) {
          d[i][0] = 1;
          q.push_back({i, 0});
        }
    }
    
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop_front();
      for (int i = 4; i < 8; ++i) {
        int nx = x + dx[i], ny = y + dy[i];
        if (!can(nx, ny)) continue;
        int w = (s[nx][ny] != '#');
        if (d[nx][ny] > d[x][y] + w) {
          d[nx][ny] = d[x][y] + w;
          p[nx][ny] = i;
          if (w) q.push_back({nx, ny});
          else q.push_front({nx, ny});
        }
      }
    }
    
    int x = 0, y = m - 1;
    for (int i = 0; i < n; ++i) if (d[x][y] > d[i][y])
      x = i;
    if (d[x][y] == INF) {
      cout << "NO\n";
      continue;
    }
    while (true) {
      s[x][y] = '#';
      int i = p[x][y];
      if (!i) break;
      x -= dx[i];
      y -= dy[i];
    }
    cout << "YES\n";
    for (auto it : s) cout << it << '\n';
  }
}

1749F - Distance to the Path

Idea: BledDest и adedalic

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())

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

const int INF = int(1e9);
const li INF64 = li(1e18);

const int N = int(2e5) + 55;
const int LOG = 18;

int n;
vector<int> g[N];

inline bool read() {
    if(!(cin >> n))
        return false;
    fore (i, 0, n - 1) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        
        g[u].push_back(v);
        g[v].push_back(u);
    }
    return true;
}

int p[LOG][N];
int tin[N], tout[N], T = 0;

void build(int v, int pr) {
    tin[v] = T++;
    p[0][v] = pr;
    fore (pw, 1, LOG)
        p[pw][v] = p[pw - 1][p[pw - 1][v]];
    
    for (int to : g[v]) {
        if (to == pr)
            continue;
        build(to, v);
    }
    tout[v] = T;
}

bool inside(int l, int v) {
    return tin[l] <= tin[v] && tout[v] <= tout[l];
}

int lca(int u, int v) {
    if (inside(u, v))
        return u;
    if (inside(v, u))
        return v;
    
    for (int pw = LOG - 1; pw >= 0; pw--) {
        if (!inside(p[pw][u], v))
            u = p[pw][u];
    }
    return p[0][u];
}

const int D = 21;
struct Fenwick {
    int n;
    vector<int> F;
    void init(int nn) {
        n = nn;
        F.assign(n, 0);
    }
    
    void add(int pos, int val) {
        for (; pos < n; pos |= pos + 1)
            F[pos] += val;
    }
    int sum(int pos) {
        int ans = 0;
        for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
            ans += F[pos];
        return ans;
    }
    int getSum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
};

struct DS {
    Fenwick f;
    void init(int n) {
        f.init(n);
    }
    
    void addPath(int v, int l, int k) {
        f.add(tin[v], +k);
        f.add(tin[l], -k);
    }
    int getVertex(int v) {
        return f.getSum(tin[v], tout[v]);
    }
    
    void addVertex(int v, int k) {
        f.add(tin[v], +k);
        if (p[0][v] != v)
            f.add(tin[p[0][v]], -k);
    }
};

DS t[D];

inline void solve() {
    fore (i, 0, D) {
        g[n - 1 + i].push_back(n + i);
        g[n + i].push_back(n - 1 + i);
    }
    int root = n + D - 1;
    
    build(root, root);
    fore (i, 0, D)
        t[i].init(root + 1);
    
    int m; cin >> m;
    fore(_, 0, m) {
        int tp; cin >> tp;
        if (tp == 1) {
            int v; cin >> v;
            v--;
            
            int ans = 0;
            for (int i = 0, cur = v; i < D; i++, cur = p[0][cur])
                ans += t[i].getVertex(cur);
            cout << ans << endl;
        } 
        else {
            assert(tp == 2);

            int u, v, k, d;
            cin >> u >> v >> k >> d;
            u--, v--;
            
            int l = lca(u, v);
            
            if (u != l)
                t[d].addPath(u, l, k);
            if (v != l)
                t[d].addPath(v, l, k);
            
            for (int i = 0; i <= d; i++, l = p[0][l]) {
                t[d - i].addVertex(l, k);
                if (d - i > 0)
                    t[d - i - 1].addVertex(l, k);
            }
        }
    }
}

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;
}

bool doesKWork(vector<int> &lEq,int k) { int j = 0; for (int i = 1; i <= k; i++) { if(lEq[i] >= k+i-1) { continue; } else { return false; } } return true; }

//binary search on k //lesserThanOrEqualTo is a vector calculated before, check submission for details int l = 1, r = n; int ans = 1; bool setAns = false; while(l <= r) { int mid = (l+r)/2; if(doesKWork(lesserThanOrEqualTo,mid)) { //then we check the ahead segment l = mid+1; continue; } else { //then we check the segment before mid r = mid-1; continue; } } cout << l-1 << endl;

// O(k log^2(n)) bool is_possible(multiset<int>& A, int k){ multiset<int> was_removed; multiset<int> was_added; for(int max_v = k; max_v >= 1; max_v--){ { if(A.size() == 0){ return false; } // what is the maximum value less than or equal to k? auto it = A.upper_bound(max_v); // O(log^2(n)) finds first element strictly greater than k; if(it == A.begin()) { // there is no value less than or equal to k for(int b : was_removed){ A.insert(b); } for(int c : was_added){ auto it = A.find(c); A.erase(it); } return false; } it--; // iterator to maximum value <= k was_removed.insert(*it); A.erase(it); } { if(A.size() == 0){ continue; } // add to the minimum auto it = A.begin(); int v = *it; A.erase(it); was_removed.insert(v); A.insert(v+max_v); was_added.insert(v+max_v); } } for(int b : was_removed){ A.insert(b); } for(int c : was_added){ auto it = A.find(c); A.erase(it); } return true; }

void solve() { int n; cin >> n; multiset<int> A; for(int i = 0; i < n; i++){ int a; cin >> a; A.insert(a); } int max_k = 0; // O(n^2 log(n)) for(int k = 0; k <= n; k++){ // O(k log(n)) if(is_possible(A, k)){ max_k = max(max_k, k); } } cout << max_k << '\n'; }

void solve2() { int n; cin >> n; multiset<int> A; for(int i = 0; i < n; i++){ int a; cin >> a; A.insert(a); } // binary search the maximum k (0 <= k <= n), such that is_possible(A, k) is true int lo = 0; int hi = n; while(lo < hi){ int mid = (lo + hi + 1) / 2; if(is_possible(A, mid)){ lo = mid; } else { hi = mid - 1; } } cout << lo << '\n'; }

Comments (30)

Write comment?

bhanu.kode5

11 months ago, # |

Thank you!

→ Reply

coolboy_22

Top 3 reason for depression

1)breakup

2)Substance Abuse

2)WA in div2 C

tox1c_kid

Can you somehow solve F using centroid decomposition?

llll.aditya.llll

← Rev. 6 →

My Solution for the problem 1749D — Counting Arrays. (Python)

Simple

Commented One

arthurg

I was trying to solve problem E using BFS + backpointer table for tracing steps. I have been debugging for an hour, but can't figure out why my solution is not optimal — is there a bug somewhere? Can someone pls help?

https://codeforces.com/contest/1749/submission/177375163

variety-jones

11 months ago, # ^ |

-10

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

rukashi

Great problems !

n1cknamezz

← Rev. 4 →

In D, I understand that if the i-th element is not "bad"(it can be removed only if it is at position 1), it's factors must contain all primes from 1 to i.

My question is: Why the number of good(not bad) elements is $$$\dfrac{m}{p_1p_2...p_k}$$$, where $$$p_k$$$ is mentioned in the editorial. Could somebody enlighten me why it is obvious :(

For position i if you call an element not bad if it can only be removed at the first position, then the element must be divisible by all the prime numbers present in [1,i]. Let's say there are k prime numbers in [1,i] : p1, p2, p3...pk.

Now, what is the smallest valid not bad element for the position i could be?

It would be: L.C.M(p1,p2,...pk) = p1.p2.p3....pk

What are the other valid not bad elements possible for the position i?

It would the Multiples of L.C.M(p1,p2,...pk) = p1.p2.p3....pk

How many valid not bad elements possible for the position i in [1,m]

m/L.C.M(p1,p2...pk)

You mentioned multiples, now I can see why. Thanks very much!

cocomos

Can someone tell me why this code for problem E is always wrong?

I have debuged it for 3 hours TAT

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

OH!THANKS!

antsparrow3

Nice round

← Rev. 3 →

Can anyone explain why the problem 1749E — Cactus Wall the path carved out by 0-1 DFS would always satisfy cacti cannot grow on cells adjacent to each other by side as we are not storing the cacti in the current path(only checking the initial cacti)?

General_Relativity

← Rev. 2 →

Note that we do BFS traversal in an order that satisfy the initial constraints as well as we maintain the constraints by traversing diagonally. It suffices to check this, since only one of the path will be our answer (which will obviously satisfy the constraints as it has been constructed that way).

TLDR : Since we only traverse diagonally to construct the path, the constraint is maintained for all paths (individually). This is necessary and sufficient.

TsReaper

The key observation of problem E is very interesting. I'm wondering if we can generalize this problem.

Say you're given a map consisting of '.', '#', 'A' and 'B'. You need to grow cactus so that one cannot go from an 'A' cell to a 'B' cell. In this case how can we find the starting and the ending point of the shortest path?

For example for the following map:

.#.#.
..#..
.AAA.
..A..
...BB
.BBB.

one must grow cactus like this:

.#.#.
..#..
#AAA#
.#A#.
..#BB
.BBB.

We can't just start from an arbitrary cell in the first column and ends at another arbitrary cell in the last column. There seems to be more restrictions.

smurf_acc

For problem C. Number Game Can someone explain why this solution with int is getting a TLE but same solution with long got accepted as n<=100 and a<=n .

TLE : https://codeforces.com/contest/1749/submission/177201608
AC : https://codeforces.com/contest/1749/submission/177222982

GTR.3910

In C, Obviously, it is more profitable for Bob to "prohibit" the smallest element of the array

Not to me. What about the case when Bob, using this tactics, takes the same integer multiple times? What if during her turn, Alice couldn't have taken all of them anyways? So that Bob wasted some moves and could rather take some other elements that Alice already took?

Could you show the proof that such situation never happens? It really puzzled me during the contest and still does. Any help is appreciated.

xsanchez

Not sure of your example. But i can try to explain the first line.

Let's suppose there are some elements and each time Alice can remove element <= k-i+1 and bob can add the same amount to any element after Alice's turn. So if you see k-i+1 is decreasing and after Alice chance, if bob is going to add any k-i+1 to any element it will surely go beyond the scope of Alice next chance no matter how small or big number bob added it on(take any example and verify it). So bob will always try to take the smallest number as it will decrease Alice's chance to select element with k-i+1 condition in next turn. whereas if bob had selected any other number there is possibility Alice might use smallest in next turn.

You can think of this problem as Alice remove one element and then Bob is also removing one element by increasing it byeond the Alice's scope.

whereas if bob had selected any other number there is possibility Alice might use smallest in next turn.

This is what I was looking for! Mystery solved, thanks!

tsvk

I had taken the contest which was attempted by over 10k+ people , out of which my code coincidently matched with one of the persons wherein I was the one who had submitted before. It can be a complete coincidence as I had not given my code to anyone nor do I know that person by any means. Also , no one keeps any evidences as one does not know this error is gonna come . I generally write my contest code very differently but I could not do it this time as I started an hour late. The question has an easy logic and it van be same for many people that does not mean it is a case of plag . It is just that the same approach struck to us and we coded it Please look into it and reflect back my ratings as these things can happen once in a many time . Writing this in response to :

"Attention! Your solution 177196148 for the problem 1749C significantly coincides with solutions tsvk/177196148, introvert_coder1/177204459. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."

Also please open your eyes and see that I have used dequeue and he has used multiset and although our solution is slightly similar , it is not the same. And if you think that out of 10000+ people even 2 of them can't think of and code "similar" solutions , man what kind of system is it . It's a request man , please look into it and do not decrease my ratings.

And talking about the multiset part in my code , that code was sent to me by my roommate to test during the contest to test as he was getting some error in that and you can clearly see that it is a comment not a code. I just debugged it and sent it back to him and commented it out. I do not know where the hell he got the code from but the approach that I have used to solve the problem is entirely different of what has been found in the plag check . Please look into it and do not take any actions on my account . Review our code , their is absolutely no match in the logics that we have used to solve the questions.

towrist

I can't prove the following lemma used in Problem E

There exists no path from top row to bottom row only if there is a zigzag path consisting of $$$#$$$ from a cell in the leftmost column to a cell in the rightmost column.

It is very intuitive to see it by drawing some pictures, but I just can't get around proving it formally. I tried induction on $$$n•m$$$, greedy proof strategies etc. But nothing seems to work. Any help? BledDest

Awesomeness._.

For C: Number game, I had a solution that is O(nlogn), although I understand the constraints didn't require it. the idea was binary search for k.

I devised a function "doesKWork" that takes inputs as the k to check and also an array where a[i] stores the number of elements lesser than or equal to i present in the original array.

for k to be a valid number such that Alice wins in optimal play by bob, this must be the condition satisfied. each lEq[i] >= k+i-1. then its just simple binary search for k.

You can check my submission for reference 177187641

ukranian_spy

Hi :)

I can't figure out why my O(n^2 log^2(n)) solution for problem C gets TLE. I have a function, to check if its possible to win. I think it runs O(k log(n)) (please correct me if I am wrong)

If I try to search through all k's, I get TLE

I did binary search and got AC. But I'm still curious why does the previous solution not run fast enough.

VigneshwaranMahadevan

4 months ago, # |

In problem D, why isn't the total number of arrays just $$$m^n$$$ ? Why should we take $$$m^1 + m^2 + ...+m^n$$$ ?

vgtcross

4 months ago, # ^ |

"You have to calculate the number of ambiguous arrays $$$a$$$ such that the length of $$$a$$$ is from $$$1$$$ to $$$n$$$"

B_Consistent

2 months ago, # |

For Problem C Why does Bob has to always choose min element ?

Isnt it more profitable to choose an minimum element,such that after bob adds the score, the minimum becomes safe element ? Suppose if it doesnt become safe, alice can simply negate the move by deleting the unsafe element in next round.There by Bob wasting his move ?

awoo's blog