CF R767 C. Meximum Array

Problem.

https://codeforces.com/contest/1629/problem/C

Idea.

Find mex for all suffix a[i:n-1]
Split the array greedily.

Source.

 void solve()  
 {  
      int t; cin >> t;  
      while (t--) {  
           int n; cin >> n;  
           vector<int> a(n);  
           REP(i, n) cin >> a[i];  
           // find all suffix mex a[i:n-1]  
           vector<int> mex(n);  
           vector<int> cnt(n + 10, 0);  
           int now = 0;  
           for (int i = n - 1; i >= 0; i--) {  
                cnt[a[i]]++;  
                if (a[i] == now) {  
                     while (cnt[now]) now++;  
                }  
                mex[i] = now;  
           }  
           // split the array  
           vector<int> ret;  
           int cur = 0;  
           while (cur < n) {  
                ret.push_back(mex[cur]);  
                int i = cur;  
                set<int> st;  
                while (i < n) {  
                     if (a[i] < mex[cur]) st.insert(a[i]);  
                     if (st.size() == mex[cur]) break;  
                     i++;  
                }  
                cur = i + 1;  
           }  
           cout << ret.size() << endl;  
           for (int x : ret) cout << x << " "; cout << endl;  
      }  
 }  

CF Educational Round 11. C. Hard Process

1.Problem

Problem - C - Codeforces

2.Idea

Standard two pointers method

3.Source

 void solve()  
 {  
      int n, k;  
      cin >> n >> k;  
      vector<int> a(n);  
      REP(i, n) cin >> a[i];  
      pi res(0, 0);  
      int right = 0;  
      int cnt = 0;  
      for (int left = 0; left < n; ++left) {  
           while (right < n && cnt + (!a[right]) <= k) {  
                cnt += (!a[right]);  
                right++;  
           }  
           if (res.first < right - left) {  
                res.first = right - left;  
                res.second = left;  
           }  
           if (left == right) right++;  
           else cnt -= (!a[left]);  
      }  
      cout << res.first << endl;  
      REP(i, n) {  
           if (i >= res.second && i < res.second + res.first) cout << 1 << " ";  
           else cout << a[i] << " ";  
      }  
      cout << endl;  
 }  

Codeforces ITMO Academy: pilot course » Segment Tree

<<Point Update/Range Query>>

[PART:1, STEP:1]

 A. Segment Tree for the Sum (Point Set Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A

B. Segment Tree for the Minimum (Point Set Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/B

C. Number of Minimums on a Segment (Point Set Update/Range Min&Count Query)

https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C

[PART:1, STEP:2]

A. Segment with the Maximum Sum (Point Set Update/Range Max Sum Query)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/A

B. K-th one (Point Set Update/Range Sum Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/B

C. First element at least X (Point Set Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/C

D. First element at least X-2 (Point Set Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/4/2/practice/contest/273278/problem/D

[PART:1, STEP:3]

A. Inversions (Point Set Update/Range Sum Query/Inversion)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/A

B. Inversions 2 (Point Set Update/Range Sum Query/Binary Search/Kth from right)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/B

C. Nested Segments (Point Set Update/Range Sum Query/Nested)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/C

D. Intersecting Segments  (Point Set Update/Range Sum Query/Intersection)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/D

E. Addition to Segment (Point Add Update/Range Sum Query/imos)

https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/E

[PART:1, STEP:4]

A. Sign alternation (Point Set Update/Range Sum Query/Alternate Sign)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/A

B. Cryptography (Point Set Update/Range Matrix Multi Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/B

C. Number of Inversions on Segment (Point Set Update/Range Inverse Number Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/C

D. Number of Different on Segment (Point Set Update/Range Bitwise OR Query)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/D

E. Earthquakes (Point Set Update/Range Min Query with Range Update)

https://codeforces.com/edu/course/2/lesson/4/4/practice/contest/274684/problem/E

<<Range Update/Point Query>>

[PART:2, STEP:1]

A. Addition to Segment (Range Add Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/A

B. Applying MAX to Segment (Range Max Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/B

C. Assignment to Segment (Range Set Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/C

[PART:2, STEP:4]

B. Add Arithmetic Progression On Segment (Range Add-Multi Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/B

E. Wall (Range MinMax Update/Point Get Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E

<<Range Update/Range Query>>

[PART:2, STEP:2]

A. Addition and Minimum (Range Add Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/A

B. Multiplication and Sum (Range Multi Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/B

C. Bitwise OR and AND (Range OR Update/Range AND Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/C

D. Addition and Sum (Range Add Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D

E. Assignment and Minimum (Range Set Update/Range Min Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/E

F. Assignment and Sum (Range Set Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/F

[PART:2, STEP:3]

A. Assignment and Maximal Segment (Range Set Update/Range MaxSumSeg Query)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/A

B. Inverse and K-th one (Range Inverse Update/Range Sum Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/B

C. Addition and First element at least X (Range Add Update/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/C


[PART:2, STEP:4]

A. Assignment, Addition, and Sum (Range Set Update/Range Add Update/Range Sum Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/A

C. Painter (Range ColorSegment Update/Range CountSegment Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/C

D. Problem About Weighted Sum (Range Add Update/Range Weighted Sum Query)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/D

F. Mountain (Range Set Update/Range Sum Query/Range Max Query/Binary Search)

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/F

Codeforces.1359E Modular Stability

1.Problem
https://codeforces.com/contest/1359/problem/E

2.Idea
a1 must be a divisor of a2..aN.

3.Source

 Int fact[N], invfact[N], inv[N];  
 void init()  
 {  
      fact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           fact[i] = fact[i - 1] * i % MOD;  
      }  
      inv[1] = 1;  
      for (int i = 2; i < N; i++) {  
           inv[i] = -inv[MOD%i] * (MOD / i) % MOD;  
           if (inv[i] < 0) inv[i] += MOD;  
      }  
      invfact[0] = 1;  
      for (int i = 1; i < N; i++) {  
           invfact[i] = invfact[i - 1] * inv[i] % MOD;  
      }  
 }  
 Int nCk(Int n, Int k)  
 {  
      return fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;  
 }  
 Int nPk(Int n, Int k)  
 {  
      return fact[n] * invfact[n - k] % MOD;  
 }  
 Int n, k;  
 int main()  
 {  
      cin >> n >> k;  
      init();  
      Int ans = 0;  
      for (int i = 1; i <= n; i++) {  
           int num = (n / i);  
           if (num >= k) {  
                ans = (ans + nCk(num - 1, k - 1)) % MOD;  
           }  
      }  
      cout << ans << endl;  
      return 0;  
 }  

Codeforces.1349B Orac and Medians

1.Problem
https://codeforces.com/problemset/problem/1349/B

2.Idea
Prime Factorization

3.Source

 int n;  
 ll a[N];  
 map<ll, vector<int>> mp;  
 void pFac(ll H)  
 {  
      for (ll i = 2; i*i <= H; i++) {  
           int cnt = 0;  
           while (H%i == 0) {  
                cnt++;  
                H /= i;  
           }  
           if (cnt > 0) {  
                mp[i].push_back(cnt);  
           }  
      }  
      if (H > 1) {  
           mp[H].push_back(1);  
      }  
 }  
 ll gcd(const ll a, const ll b)  
 {  
      if (b == 0) return a;  
      return gcd(b, a%b);  
 }  
 int main() {  
      scanf("%d\n", &n);  
      for (int i = 0; i < n; i++) {  
           scanf("%d", &a[i]);  
           pFac(a[i]);  
      }  
      if (n == 2) {  
           cout << a[0] * a[1] / gcd(a[0] , a[1]) << endl;  
           return 0;  
      }  
      ll ans = 1;  
      for (auto itr = mp.begin(); itr != mp.end(); itr++) {  
           int p = itr->first;  
           vector<int> v = itr->second;  
           int k = 0;  
           if (v.size() + 2 <= n) continue;  
           sort(v.begin(), v.end());  
           if (v.size() + 1 == n) {  
                k = v[0];  
           }  
           else {  
                k = v[1];  
           }  
           int t = (int)pow(1.0 * p, 1.0 * k);  
           ans = ans * (ll)t;  
      }  
      printf("%d\n", ans);  
      return 0;  
 }  

Codeforces. 1336B Xenia and Colorful Gems

1.Problem
https://codeforces.com/contest/1336/problem/B

2.Idea
Assuming x <= y <=z.
Enumerating middle value, and find smallest and biggest value by binary_search.

3.Source

 int nr, ng, nb;  
 ll ans = 1LL << 60;  
 ll calc(ll x, ll y, ll z)  
 {  
      return (x - y)*(x - y) + (y - z)*(y - z) + (x - z)*(x - z);  
 }  
 void solve(vector<int> a, vector<int> b, vector<int> c) {  
      for (auto x : a) {  
           auto y = lower_bound(b.begin(), b.end(), x);  
           auto z = upper_bound(c.begin(), c.end(), x);  
           if (y == b.end() || z == c.begin()) { continue; }  
           z--;   
           ans = min(ans, calc(x, *y, *z));  
      }  
 }  
 int main()  
 {  
      int t; cin >> t;  
      while (t--) {  
           ans = 1LL << 62;  
           cin >> nr >> ng >> nb;  
           vector<int> r(nr), g(ng), b(nb);  
           for (int i = 0; i < nr; i++) {  
                cin >> r[i];  
           }  
           for (int i = 0; i < ng; i++) {  
                cin >> g[i];  
           }  
           for (int i = 0; i < nb; i++) {  
                cin >> b[i];  
           }  
           sort(r.begin(), r.end());  
           sort(g.begin(), g.end());  
           sort(b.begin(), b.end());  
           solve(r, g, b);  
           solve(r, b, g);  
           solve(g, r, b);  
           solve(g, b, r);  
           solve(b, g, r);  
           solve(b, r, g);  
           cout << ans << endl;  
      }  
      return 0;  
 }  

CodeForces. 1337C Linova and Kingdom

1.Problem
https://codeforces.com/contest/1337/problem/C

2.Idea
Sort by {Depth - Child Number}, and pick k vertices.

3.Source

 int n, k;  
 vector<int> adj[N];  
 int dist[N];  
 bool visited[N];  
 int child[N];  
 bool col[N];  
 int dist2[N];  
 struct City {  
      int num, child, dist;  
      bool operator < (const City &a)const {  
           return dist - child < a.dist - a.child;  
      }  
 } Cities[N];  
 void getChild(int k)  
 {  
      //cout << k << endl;  
      visited[k] = true;  
      for (int i = 0; i < adj[k].size(); i++) {  
           int u = adj[k][i];  
           if (visited[u] == 0) {  
                getChild(u);  
                child[k] += (1 + child[u]);  
           }  
      }  
 }  
 void colorCities()  
 {  
      for (int i = 0; i < n; i++) {  
           Cities[i].num = i;  
           Cities[i].child = child[i];  
           Cities[i].dist = dist[i];  
      }  
      sort(Cities, Cities + n);  
      for (int i = 0; i < n - k; i++) {  
           int t = Cities[i].num;  
           col[t] = true;  
      }  
 }  
 int main()  
 {  
      cin >> n >> k;  
      for (int i = 0; i < n - 1; i++) {  
           int u, v;  
           cin >> u >> v;  
           u--; v--;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      // get dist  
      memset(visited, 0, sizeof visited);  
      queue<P> q;  
      q.push(P(0, 0));  
      while (!q.empty()) {  
           int v = q.front().first;  
           int d = q.front().second;  
           q.pop();  
           visited[v] = 1;  
           dist[v] = d;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0 && dist[u] == 0) {  
                     q.push(P(u, d + 1));  
                }  
           }  
      }  
      //get child  
      memset(visited, 0, sizeof visited);  
      getChild(0);  
      //color  
      colorCities();  
      //count  
      memset(visited, 0, sizeof visited);  
      queue<P> q1;  
      q1.push(P(0, 0));  
      while (!q1.empty()) {  
           int v = q1.front().first;  
           int d = q1.front().second;  
           q1.pop();  
           visited[v] = 1;  
           dist2[v] = d;  
           if (col[v]) d++;  
           for (int i = 0; i < adj[v].size(); i++) {  
                int u = adj[v][i];  
                if (visited[u] == 0) {  
                     q1.push(P(u, d));  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = 0; i < n; i++) {  
           if (col[i] == 0) ans += dist2[i];  
      }  
      cout << ans << endl;  
      return 0;  
 }  

CodeForces. 1339D Edge Weight Assignment

1.Problem.
https://codeforces.com/contest/1339/problem/D

2.Idea
Here

3.Source

 vector<int> adj[N];  
 int d[N];  
 set<int> st;  
 // calc dist from root  
 void dfs(int v, int p)  
 {  
      for (auto& x : adj[v]) {  
           if (x == p) continue;  
           d[x] = d[v] + 1;  
           dfs(x, v);  
      }  
 }  
 int main()  
 {  
      int n;  
      cin >> n;  
      for (int i = 1; i < n; i++) {  
           int v, u;  
           cin >> v >> u;  
           adj[u].push_back(v);  
           adj[v].push_back(u);  
      }  
      int root = 0;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                root = i;  
                break;  
           }  
      }  
      dfs(root, 0);  
      int mn = 1, mx = n - 1;  
      for (int i = 1; i <= n; i++) {  
           if (adj[i].size() == 1) {  
                if (d[i] % 2 != 0) {  
                     mn = 3;  
                }  
                st.insert(adj[i][0]);  
                --mx;  
           }  
      }  
      mx += st.size();  
      cout << mn << " " << mx << endl;  
      return 0;  
 }  

Codeforces.1334C Circle of Monsters

1.Problem
https://codeforces.com/contest/1334/problem/C

2.Idea
Only start point takes a[i] shoots, and other places a[i] - b[i-1]. Check every places as start point.

3.Source

 int n, t;  
 ll a[300005], b[300005], ac[300005];  
 void solve()  
 {  
      ll sum = 0;  
      for (int i = 0; i < n; i++) {  
           ac[i] = max(0ll, a[i] - b[(i + n - 1) % n]);  
           sum += ac[i];  
      }  
      ll ans = 1ll << 60;  
      for (int i = 0; i < n; i++) {  
           ans = min(ans, sum - ac[i] + a[i]);  
      }  
      //cout << ans << endl;  
      printf("%lld\n", ans);  
 }  
 int main()  
 {  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%d", &n);  
           for (int i = 0; i < n; i++) {  
                scanf("%lld%lld", &a[i], &b[i]);  
           }  
           solve();  
      }  
      return 0;  
 }  

CodeForces. 1333C Eugene and an array

1.Problem
https://codeforces.com/problemset/problem/1333/C

2.Idea
Keep tracking right most sum zero segment. 

3.Source

 int n;  
 map<ll, int> mp;  
 ll ans, sum;  
 int x, q;  
 int main()  
 {  
      cin >> n;  
      q = -1;  
      mp[0] = 0;  
      for (int i = 1; i <= n; i++)  
      {  
           cin >> x;  
           sum += x;  
           if (mp.count(sum)) {  
                q = max(q, mp[sum]);  
           }  
           ans += (i - q - 1);  
           mp[sum] = i;  
      }  
      cout << ans << endl;  
      return 0;  
 }  

CodeForces.1326D2 Prefix-Suffix Palindrome (Hard version)

1.Problem
https://codeforces.com/contest/1326/problem/D2

2.Idea
KMP algorithm

3.Source

 string s;  
 int n;  
 //kmp algorithm: returns len of the longest pre==suf   
 int longest_palindrome_prefix(const string s)  
 {  
      string kmprev = s;  
      reverse(kmprev.begin(), kmprev.end());  
      string kmp = s + "#" + kmprev;  
      vector<int> lps(kmp.size(), 0);  
      for (int i = 1; i < (int)lps.size(); ++i)  
      {  
           int prev_idx = lps[i - 1];  
           while (prev_idx > 0 && kmp[i] != kmp[prev_idx])  
           {  
                prev_idx = lps[prev_idx - 1];  
           }  
           lps[i] = prev_idx + (kmp[i] == kmp[prev_idx] ? 1 : 0);  
      }  
      return lps[lps.size() - 1];  
 }  
 int32_t main()  
 {  
      int t;  
      cin >> t;  
      while(t--)  
      {  
           cin >> s;  
           n = s.length();  
           int ln = 0;  
           for (int i = 0, j = n - 1; i < j; ++i, --j)  
                if (s[i] == s[j])  
                     ln++;  
                else  
                     break;  
           int rem = n - 2 * ln;  
           string ans;  
           if (ln)     ans = s.substr(0, ln);  
           if (rem > 0)  
           {  
                string st = s.substr(ln, rem);  
                int pre = longest_palindrome_prefix(st);  
                reverse(st.begin(), st.end());  
                int suf = longest_palindrome_prefix(st);  
                if (pre > suf) {  
                     reverse(st.begin(), st.end());  
                     ans += st.substr(0, pre);  
                }  
                else {  
                     ans += st.substr(0, suf);  
                }  
           }  
           if (ln) ans += s.substr(n - ln, ln);  
           std::cout << ans << '\n';  
      }  
      return 0;  
 }