Codeforces Round #666 — Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

We hoped you find our problems interesting. We apologize for the late editorial. Hopefully you were still able to enjoy our contest.

Anyway, here are the tutorials for each of the problems:

1397A - Juggling Letters

If the total number of occurrences of some character $$$c$$$ is not a multiple of $$$n$$$, then it is impossible to make all $$$n$$$ strings equal — because then it is impossible for all $$$n$$$ strings to have the same number of $$$c$$$.

On the other hand, if the total number of occurrences of every character $$$c$$$ is a multiple of $$$n$$$, then it is always possible to make all $$$n$$$ strings equal. To achieve this, for every character $$$c$$$ we move exactly ((the total number of occurrences of $$$c$$$) $$$/$$$ $$$n$$$) characters $$$c$$$ to the end of each string, and by the end we will have all $$$n$$$ strings equal each other.

We can easily check if the condition satisfies by counting the total number of occurrences of each character $$$c$$$ and check its divisibility by $$$n$$$. The final complexity is $$$O(S \cdot 26)$$$ or $$$O(S)$$$ where $$$S$$$ is the sum of lengths of all strings.

C++ solution


#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int tests;
	cin >> tests;
	while (tests--) {
		int n;
		cin >> n;

		vector<int> cnt(26);
		for (int i = 0; i < n; ++i) {
			string s;
			cin >> s;
			for (char ch : s) {
				++cnt[ch - 'a'];
			}
		}

		bool ans = true;
		for (int i = 0; i < 26; ++i) {
			if (cnt[i] % n != 0) {
				ans = false;
				break;
			}
		}

		cout << (ans ? "YES" : "NO") << endl;
	}
}

Python solution

numTests = int(input())
for testNo in range(numTests):
	n = int(input())
	cnt = [0 for i in range(26)]
	for _ in range(n):
	    s = input()
	    for i in s:
	        cnt[ord(i) - 97] += 1

	ans = True
	for i in range(26):
	    if cnt[i] % n != 0:
	        ans = False
	        break

	if ans:
	    print('YES')
	else:
	    print('NO')

1397B - Power Sequence

First of all, the optimal way to reorder is to sort $$$a$$$ in non-decreasing order.

Proof

From now on, we assume $$$a$$$ is sorted in non-decreasing order.

Denote $$$a_{max} = a_{n - 1}$$$ as the maximum value in $$$a$$$, $$$f(x) = \sum{\lvert a_i - x^i \rvert}$$$ as the minimum cost to transform $$$a$$$ into $$${x^0, x^1, \cdots, x^{n-1}}$$$, and $$$c$$$ as the value where $$$f(c)$$$ is minimum.

Note that $$$c^{n - 1} - a_{max} \le f(c) \le f(1)$$$, which implies $$$c^{n - 1} \le f(1) + a_{max}$$$.

We enumerate $$$x$$$ from $$$1, 2, 3, \dots$$$ until $$$x^{n - 1}$$$ exceeds $$$f(1) + a_{max}$$$, calculate $$$f(x)$$$ in $$$O(n)$$$, and the final answer is the minimum among all calculated values. The final complexity is $$$O(n \cdot max(x))$$$.

But why doesn't this get TLE? Because $$$f(1) = \sum{(a_i - 1)} < a_{max} \cdot n \le 10^9 \cdot n$$$, thus $$$x^{n - 1} \le f(1) + a_{max} \le 10^9 \cdot (n + 1)$$$. When $$$n = 3, 4, 5, 6$$$, $$$max(x)$$$ does not exceed $$$63245, 1709, 278, 93$$$ respectively; so we can see that $$$O(n \cdot max(x))$$$ comfortably fits in the time limit.

C++ solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

const int64_t INF = 1e17;
inline int64_t mul(int64_t a, int64_t b)
{
	return (INF / a > b ? a * b : INF);
}

inline int64_t add(int64_t a, int64_t b)
{
	return (a + b >= INF ? INF : a + b);
}

int main()
{
	int n;
	cin >> n;

	vector<int> a(n);
	for (int &x : a) cin >> x;
	sort(a.begin(), a.end());

	if (n <= 2) {
		cout << a[0] - 1 << endl;
	} else {
		int64_t ans = accumulate(a.begin(), a.end(), 0ll) - n;

		for (int x = 1; ; ++x) {
			int64_t curPow = 1, curCost = 0;
			for (int i = 0; i < n; ++i) {
				curCost = add(curCost, abs(a[i] - curPow));
				curPow = mul(curPow, x);
			}

			if (curPow == INF || curPow / x > ans + a[n - 1]) break;
			ans = min(ans, curCost);
		}

		cout << ans << endl;
	}
}

Python solution

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
inf = 10**18

if n <= 2:
    print(a[0] - 1)
else:
    ans = sum(a) - n

    for x in range(1, 10**9):
        curPow = 1
        curCost = 0
        for i in range(n):
            curCost += abs(a[i] - curPow)
            curPow *= x
            if curPow > inf:
                break

        if curPow > inf:
            break
        if curPow / x > ans + a[n - 1]:
            break

        ans = min(ans, curCost)

    print(ans)

1396A - Multiples of Length

In this problem, the answer is rather simple. Here is one possible solution to this task.

Solution for n = 1

Solution for n != 1

C++ solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N;
   cin >> N;
   vector<ll> A(N);
   for (int i = 0; i < N; ++i) cin >> A[i];
   if (N == 1) {
      for (int z = 0; z < 3; ++z) {
         cout << "1 1\n";
         cout << -A[0] << "\n";
         A[0] = 0;
      }
      return 0;
   }
   cout << "1 " << N << "\n";
   for (int i = 0; i + 1 < N; ++i) cout << -A[i] * N << " "; cout << "0\n";
   cout << "1 " << N - 1 << "\n";
   for (int i = 0; i + 1 < N; ++i) cout << A[i] * (N - 1) << " "; cout << "\n";
   cout << N << " " << N << "\n";
   cout << -A[N - 1] << "\n";
   return 0;
}

Python solution

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print('1 1', -a[0], '1 1', '0', '1 1', '0', sep='\n')
    exit(0)

print(1, n)
for i in range(n):
    print(-a[i] * n, end = ' ')
    a[i] -= a[i] * n
print()

print(1, n - 1)
for i in range(n - 1):
    print(-a[i], end = ' ')
    a[i] = 0
print()

print(2, n)
for i in range(1, n):
    print(-a[i], end = ' ')
    a[i] = 0
print()

1396B - Stoned Game

Let us denote $$$S$$$ as the current total number of stones.

Consider the following cases:

Case A: There is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones.

The first player (T) can always choose from this pile, thus he (T) is the winner.

Case B: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is even.

It can be proven that the second player (HL) always wins.

Proof 1

Proof 2

Case C: Every pile has at most $$$\lfloor \frac{S}{2} \rfloor$$$ stones, and $$$S$$$ is odd.

The first player (T) can choose from any pile, and we arrive back at case B where the next player to move loses.

So the first player (T) wins if and only if there is a pile that has more than $$$\lfloor \frac{S}{2} \rfloor$$$ stones or $$$S$$$ is odd. This can be easily checked in $$$O(n)$$$.

C++ solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

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 maxPile = *max_element(a.begin(), a.end());
		int numStones = accumulate(a.begin(), a.end(), 0);

		if (maxPile * 2 > numStones || (numStones & 1)) cout << "T" << endl;
		else cout << "HL" << endl;
	}
}

Python solution

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]

    maxPile = max(a)
    numStones = sum(a)

    if maxPile * 2 > numStones or (numStones & 1):
        print('T')
    else:
        print('HL')

1396C - Monster Invaders

In this problem, it is useful to note that when the boss only has $$$1$$$ hp left, just use the pistol because it has the least reloading time. So there are 3 strategies we will use when playing at stage $$$i$$$ $$$(1 \le i \le n)$$$:

Take $$$a_i$$$ pistol shots to kill first $$$a_i$$$ monsters and shoot the boss with the AWP.
Take $$$a_i + 1$$$ pistol shots and move back to this stage later to take another pistol shot to finish the boss.
Use the laser gun and move back to this stage later to kill the boss with a pistol shot.

Observation: We will always finish the game at stage $$$n$$$ or $$$n - 1$$$. Considering we are at stage $$$i$$$ $$$(i \le n - 1)$$$ and the boss at both stage $$$i$$$ stage $$$i - 1$$$ has $$$1$$$ hp left, we can spend $$$2 * d$$$ time to finish both these stages instead of going back later, which costs us exactly the same.

Therefore, we will calculate $$$dp(i,0/1)$$$ as the minimum time to finish first $$$i - 1$$$ stages and 0/1 is the remaining hp of the boss at stage $$$i$$$. The transitions are easy to figure out by using 3 strategies as above. The only thing we should note is that we can actually finish the game at stage $$$n - 1$$$ by instantly kill the boss at stage $$$n$$$ with the AWP so we don't have to go back to this level later.

Answer to the problem is $$$dp(n, 0)$$$. Time complexity: $$$O(n)$$$.

C++ solution

/*input
4 2 4 4 1
4 5 1 2
*/
#include <bits/stdc++.h>
using namespace std;

int read() {
	int x = 0, c = getchar();
	for(; !(c > 47 && c < 58); c = getchar());
	for(; (c > 47 && c < 58); c = getchar()) x = x * 10 + c - 48;
	return x;
}

void upd(long long &a, long long b) {
	a = (a < b) ? a : b;
}

const int N = 1e6 + 5;

long long f[N][2];
int n, r1, r2, r3, d, a[N];

int main(){ 
	n = read(), r1 = read(), r2 = read(), r3 = read(), d = read();
	for(int i = 1; i <= n; a[i ++] = read());

	for(int i = 2; i <= n; ++ i) f[i][0] = f[i][1] = 1e18;

	f[1][0] = 1ll * r1 * a[1] + r3;
	f[1][1] = min(0ll + r2, 1ll * r1 * a[1] + r1);
	for(int i = 1; i < n; ++ i) {
		// 0 -> 0
		// so we clear this one and the next one as well
		upd(f[i + 1][0], f[i][0] + d + 1ll * r1 * a[i + 1] + r3);

		// 0 -> 1
		// this one is cleared, but next one isnt
		upd(f[i + 1][1], f[i][0] + d + min(0ll + r2, 1ll * r1 * a[i + 1] + r1));
		
		// 1 -> 0
		upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + 2 * d + r1);
		upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d + r1);
		upd(f[i + 1][0], f[i][1] + d + r2 + d + r1 + d + r1);

		// 1 -> 1
		upd(f[i + 1][1], f[i][1] + d + r2 + d + r1 + d);
		upd(f[i + 1][1], f[i][1] + d + 1ll * r1 * a[i + 1] + r1 + d + r1 + d);

		if(i == n - 1) {
			upd(f[i + 1][0], f[i][1] + d + 1ll * r1 * a[i + 1] + r3 + d + r1);
		}
	}
	cout << f[n][0] << endl;
}

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int MOD = 1000000007;

int L;
ll sum[8040];
int len[8040];
int last[8040];
int lazy[8040];

void init(int v, int l, int r, const vector<int> &xs) {
   len[v] = xs[r] - xs[l - 1];
   if (l < r) {
      int md = (l + r) >> 1;
      init(v << 1, l, md, xs);
      init(v << 1 | 1, md + 1, r, xs);
   }
}

void reset(int v, int l, int r, const vector<int> &go) {
   lazy[v] = -1;
   if (l == r) {
      sum[v] = ll(len[v]) * (L - go[l]);
      last[v] = go[l];
      return;
   }
   int md = (l + r) >> 1;
   reset(v << 1, l, md, go);
   reset(v << 1 | 1, md + 1, r, go);
   sum[v] = sum[v << 1] + sum[v << 1 | 1];
   last[v] = last[v << 1 | 1];
}

void push(int v, int l, int r) {
   if (lazy[v] != -1) {
      last[v] = lazy[v];
      sum[v] = ll(len[v]) * (L - lazy[v]);
      if (l < r) {
         lazy[v << 1] = lazy[v];
         lazy[v << 1 | 1] = lazy[v];
      }
      lazy[v] = -1;
   }
}

void modify(int v, int l, int r, int L, int R, int qv) {
   push(v, l, r);
   if (L > r || R < l) return;
   if (L <= l && r <= R) {
      lazy[v] = qv;
      push(v, l, r);
      return;
   }
   int md = (l + r) >> 1;
   modify(v << 1, l, md, L, R, qv);
   modify(v << 1 | 1, md + 1, r, L, R, qv);
   sum[v] = sum[v << 1] + sum[v << 1 | 1];
   last[v] = last[v << 1 | 1];
}

int walk(int v, int l, int r, int qv) {
   push(v, l, r);
   if (last[v] <= qv) return -1;
   if (l == r) return l;
   int md = (l + r) >> 1;
   int ans = walk(v << 1, l, md, qv);
   if (ans == -1) ans = walk(v << 1 | 1, md + 1, r, qv);
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N, K; cin >> N >> K >> L;
   vector<int> X(N), Y(N), C(N);
   vector<int> xs = {-1, L};
   vector<int> ys = {-1, L};
   for (int i = 0; i < N; ++i) {
      cin >> X[i] >> Y[i] >> C[i];
      --C[i];
      xs.emplace_back(X[i]);
      ys.emplace_back(Y[i]);
   }
   sort(xs.begin(), xs.end());
   xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
   sort(ys.begin(), ys.end());
   ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
   int NX = xs.size();
   int NY = ys.size();
   {
      vector<int> order(N);
      iota(order.begin(), order.end(), 0);
      sort(order.begin(), order.end(), [&](int i, int j) {
         return make_pair(Y[i], -X[i]) > make_pair(Y[j], -X[j]);
      });
      vector<int> newX(N), newY(N), newC(N);
      for (int i = 0; i < N; ++i) {
         newX[i] = X[order[i]];
         newY[i] = Y[order[i]];
         newC[i] = C[order[i]];
      }
      X.swap(newX), Y.swap(newY), C.swap(newC);
   }
   init(1, 1, NX - 2, xs);
   int ans = 0;
   for (int yr = 1; yr + 1 < NY; ++yr) {
      vector<vector<int>> addAt(NX);
      for (int i = 0; i < N; ++i) {
         if (Y[i] <= ys[yr]) {
            int xi = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
            addAt[xi].emplace_back(C[i]);
         }
      }
      int bad = K;
      vector<int> cnts(K);
      auto inc = [&](int z) {
         if (++cnts[z] == 1) --bad;
      };
      auto dec = [&](int z) {
         if (--cnts[z] == 0) ++bad;
      };
      vector<int> go(NX);
      int ptr = 0;
      for (int i = 1; i + 1 < NX; ++i) {
         while (bad && ptr + 2 < NX) {
            ptr++;
            for (int z : addAt[ptr]) inc(z);
         }
         if (bad) go[i] = L;
         else go[i] = xs[ptr];
         for (int z : addAt[i]) dec(z);
      }
      reset(1, 1, NX - 2, go);
      vector<int> prv(N);
      vector<int> nxt(N);
      vector<map<int, int>> mp(K);
      for (int i = 0; i < N; ++i) {
         if (Y[i] <= ys[yr]) {
            auto it = mp[C[i]].lower_bound(X[i]);
            if (it == mp[C[i]].end()) {
               nxt[i] = -1;
            } else {
               nxt[i] = it->second;
            }
            it = mp[C[i]].upper_bound(X[i]);
            if (it == mp[C[i]].begin()) {
               prv[i] = -1;
            } else {
               prv[i] = prev(it)->second;
            }
            mp[C[i]][X[i]] = i;
         }
      }
      auto remove = [&](int i) {
         int xprv = (prv[i] == -1 ? -1 : X[prv[i]]);
         int xcur = X[i];
         int xnxt = (nxt[i] == -1 ? L : X[nxt[i]]);
         int l =  lower_bound(xs.begin(), xs.end(), xprv) - xs.begin() + 1;
         int r = walk(1, 1, NX - 2, xnxt);
         if (r == -1) r = NX - 1; --r;
         r = min(r, int(lower_bound(xs.begin(), xs.end(), xcur) - xs.begin()));
         if (l <= r) modify(1, 1, NX - 2, l, r, xnxt);
      };
      ptr = N - 1;
      for (int yl = 1; yl <= yr; ++yl) {
         ll add = sum[1] % MOD * (ys[yr + 1] - ys[yr]) % MOD * (ys[yl] - ys[yl - 1]) % MOD;
         ans = (ans + add) % MOD;
         while (ptr >= 0 && Y[ptr] == ys[yl]) remove(ptr--);
      }
      assert(sum[1] == 0);
   }
   cout << ans << "\n";
   return 0;
}

Tutorial is loading...

C++ solution

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N; ll K;
   cin >> N >> K;
   vector<vector<int>> adj(N);
   for (int i = 0; i < N - 1; ++i) {
      int v, u;
      cin >> v >> u;
      adj[--v].emplace_back(--u);
      adj[u].emplace_back(v);
   }
   vector<int> sz(N);
   function<void(int, int)> dfs1 = [&](int v, int p) {
      sz[v] = 1;
      for (int u : adj[v]) if (u != p) {
         dfs1(u, v);
         sz[v] += sz[u];
      }
   };
   dfs1(0, -1);
   int root = 0;
   for (int i = 1; i < N; ++i) {
      if (sz[i] >= N / 2 && sz[i] < sz[root]) root = i;
   }
   vector<int> dist(N);
   vector<int> top(N, -1);
   vector<int> par(N, -1);
   ll low = 0, high = 0;
   function<void(int, int, int)> dfs2 = [&](int v, int p, int r) {
      dist[v] = dist[p] + 1;
      top[v] = r;
      par[v] = p;
      {
         auto it = find(adj[v].begin(), adj[v].end(), p);
         assert(it != adj[v].end());
         adj[v].erase(it);
      }
      sz[v] = 1;
      for (int u : adj[v]) {
         dfs2(u, v, r);
         sz[v] += sz[u];
      }
      low += (sz[v] & 1);
      high += sz[v];
   };
   for (int v : adj[root]) {
      dfs2(v, root, v);
   }
   if (low > K || high < K || (high - K) % 2) {
      cout << "NO\n";
      return 0;
   }
   set<pair<int, int>> sizes;
   for (int v : adj[root]) {
      sizes.emplace(sz[v], v);
   }
   vector<set<pair<int, int>>> lcas(N);
   vector<int> deg(N);
   for (int v = 0; v < N; ++v) deg[v] = adj[v].size();
   for (int v = 0; v < N; ++v) if (v != root) {
      if (deg[v] == 0) {
      } else {
         lcas[top[v]].emplace(dist[v], v);
      }
   }
   vector<bool> matched(N);
   function<void(int)> kill = [&](int v) {
      assert(deg[v] == 0);
      if (--deg[par[v]] == 0) {
         v = par[v];
         lcas[top[v]].erase(pair<int, int>(dist[v], v));
      }
   };
   cout << "YES\n";
   while (high > K) {
      assert(sizes.size());
      int v = (--sizes.end())->second;
      sizes.erase(pair<int, int>(sz[v], v));
      assert(lcas[v].size());
      int mdist = (--lcas[v].end())->first;
      if (high - 2 * mdist <= K) {
         int x = lcas[v].lower_bound(pair<int, int>((high - K) / 2, -1))->second;
         int y = -1;
         for (int z : adj[x]) if (!matched[z]) {
            y = z;
            break;
         }
         high = K;
         cout << x + 1 << " " << y + 1 << "\n";
         matched[x] = true;
         matched[y] = true;
         break;
      } else {
         high -= 2 * mdist;
         assert(lcas[v].size());
         int u = (--lcas[v].end())->second;
         vector<int> nxts;
         while (nxts.size() < 2 && adj[u].size()) {
            int w = adj[u].back();
            adj[u].pop_back();
            if (!matched[w]) {
               nxts.emplace_back(w);
            }
         }
         if (nxts.size() < 2) nxts.emplace_back(u);
         assert(nxts.size() == 2);
         cout << nxts[0] + 1 << " " << nxts[1] + 1 << "\n";
         matched[nxts[0]] = true;
         matched[nxts[1]] = true;
         kill(nxts[0]);
         kill(nxts[1]);
         sz[v] -= 2;
         if (sz[v]) sizes.emplace(sz[v], v);
      }
   }
   vector<int> seq;
   function<void(int)> dfs3 = [&](int v) {
      if (!matched[v]) seq.emplace_back(v);
      for (int u : adj[v]) dfs3(u);
   };
   dfs3(root);
   int h = seq.size() / 2;
   for (int i = 0; i < h; ++i) {
      cout << seq[i] + 1 << " " << seq[i + h] + 1 << "\n";
   }
}

Comments (53)

Show archived | Write comment?

DatVu

4 years ago, # |

Auto comment: topic has been updated by DatVu (previous revision, new revision, compare).

→ Reply

Celloboy

← Rev. 2 →

+12

Awesome contest and nice problems! The pretests on Div 2 B were a bit weak.

connorwang38

4 years ago, # ^ |

Good or bad thing? I think it's interesting because some people prefer weak pretests for hacking potential, while others prefer strong pretests to have the peace of mind that their submissions are right or wrong.

atoiz

+14

Sorry for that. I tried to create strong pretests, but couldn't do much with only 5 pretests allowed.

decoder__

-17

I've updated the editorial for B. Hope it clears things up for you.

Thanks !!

sharath101

+22

About time

kesh4281

What happens if in Stoned Game we are allowed to remove non-empty pile of any size?

← Rev. 3 →

Whatever i said was incorrect. The rule that a person cannot choose from the same pile as the previous turn invalidates whatever i said

Merripium

+15

It will be equivalent to nim because in nim game, strategy to win always doesn't contain any move that remove stones from the piles in the immediate previous turn.

neko_nyaaaaaaaaaaaaaaaaa

+135

Thank you for lightning fast editorial

ThinkAgain

+27

Stoned game problem is very much similar to CF round 577 div 2 B. If you submit that problem solution just changing YES->HL and NO->T, you will get AC on this problem which is D type of Div2.

Mr.Doap

+18

In that problem the solution might be same but there we are the ones who select both i and j right but in this case both persons try to counter each other. So if you are able to observe that it does not matter much here. Then yeah both are same problems

Yeah right, Both are exactly same problems for those who can observe the intuition behind the problem.

temp_sec

One more thing that I found different, was that the player can't choose piles from the immediate previous turn. Why this fact doesn't affect the solutions to the problems?

One turn of selecting i and j in that problem is equivalent to two moves in the game where one person selecting pile i and the other pile j.

I hope this is what you were trying to ask

beroul

Great observation ! It shows that how you think of a problem drastically changes the way you try to solve it..

bhushanbaby

+13

Why is the code for Div 1. C so complicated? There are 2 dp recurrences, one from dp[i] to dp[i+1], and one from dp[i] to dp[i+2].

$$$upd(dp[i+1],dp[i]+d+r1*arr[i]+r3);$$$

$$$upd(dp[i+2],dp[i]+4*d+min(r1*(arr[i]+1),r2)+r1+min({r1*(arr[i+1]+2),r1*(arr[i+1])+r3,r2+r1}));$$$

mango_lassi

They store the remaining HP of the boss of the previous stage. The recursion is still overcomplicated, as this suffices:

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
 
const int N = (int)1e6;
ll dp[N + 1][2]; // Min cost, odd number of current twos
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	ll n, r1, r2, r3, d; // r1, r2, r3: Weak, AOE, Strong
	cin >> n >> r1 >> r2 >> r3 >> d;
 
	vector<ll> as(n);
	for (ll& a : as) cin >> a;

	dp[0][1] = INF;
	for (int i = 0; i < n; ++i) {
		ll add = (i+1 < n ? d : 0); // Cost for odd-length sequence of twos
		ll c1 = r1 * as[i] + r3; // Kill the boss in one attack
		ll c2 = min(r1 + r2, r1 * (as[i]+2)) + d; // Kill the boss in two attacks
		dp[i+1][0] = min(c2 + dp[i][1], c1 + min(dp[i][0], dp[i][1] + add));
		dp[i+1][1] = c2 + dp[i][0];
	}
	cout << (min(dp[n][0], dp[n][1] + d) + d*(n-1)) << '\n';
}

ninetyone

I cannot understand why we need the case with odd-length sequence. Since when we have the odd length sequence we should convert it to an even length sequence based on the fact that the cost of one attack >= 2 attack and if we have an odd sequence then we are going to spend 2*d anyway so why not just make it an even length sequence?

Good observation, though you still need to handle the case where you attack once at $$$n$$$ and turn around. 91777714

Thanks for the help! Actually I was missing the case

(dp[n][1] + d) + d*(n-1))

when outputting the final answer which I think is required if we have an odd number of levels and we end up taking attack 2 on all of them. This was giving me wrong answer.

_dobby_

Div1C: 'We will always finish the game at stage n or n−1.'

Why is that so? Why is something like, let's say (for n = 5)

1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2, not possible?

-6

It is possible, but isn't optimal.

+61

It can be optimal. What we know is that there always exists an optimal solution that finishes at $$$n$$$ or $$$n-1$$$.

+20

It's just that there is an equivalent solution that finishes at n or n-1

In your case it would be

1-->2-->3-->2-->3-->4-->5-->4

And this comes from the obersvation that if you have unfinished business at position X (so you have to come back at X), then you don't face the same issue for X+1 (because from X+1 you go back to X then to X+1)...

wireless

The editorial doesn't include intuition for Div2C/Div1A.

Here is my intuition: First I started thinking about how many operations an element needs.

(1) With one operation it is possible if the len divides the element.

(2) With two coprime operations it is always possible.

Ok, so (2) seems like the most viable method. Now how do we do two coprime operations on each element? We can do two operations of length n, but we need them to be coprime. Okay, so how about one operation with length n and one with length n-1. Now we can use the third operation with length 1 on the remaining element.

Shameek

i got what you meant

inksamurai

+11

i solved B using ternary search

Falcon__

Good tutorial,but the div2E's solution is really vague,"why We will always finish the game at stage n or n−1"? The explaination can never be understood,let's think we have n = 5,1->2->3->4->5->4->3->2->1 must be some data set's optimal solution.I am silly,and you guys can downvote me for my rudeness, but I really hope the offical can explain this clearly!!!

+19

Your strategy can also be optimal, but actually you can finish the game at stage n or n — 1 with exactly same moving cost. In your example, instead of following the path 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1, you can move like this: 1 -> 2 -> 1 -> 2 -> 3 -> 4 -> 3 -> 4 -> 5. By moving like this, it's so much easier for us to transit between DP states.

Firstly,really thank you for your forgiveness on my rudeness and your deeper explaination. I somehow understand what you have said,and I will have a try.Thanks for your explaintion and patientenss again!(sorry for my poor English....)

Auto comment: topic has been updated by atoiz (previous revision, new revision, compare).

scameeer

How to solve Div 1B/2D if the player can't choose a pile that he/she has chosen in his/her previous turn.

ketan_07

In Power Sequence, I tried to find the sum of first n terms of GP such that the first term is always 1 and the common difference keeps incrementing in a loop until it exceeds the limit as specified in the editorial above and inside that loop I'm storing the minimum of the difference of the sum of n terms of GP and the total sum of the array but this logic is not passing the test cases, can someone help me find fault in this logic.

Sn = 1*(pow(i, n) / (i — n)), res = min(res, Sn — arr_sum)

The difference between the sum of n terms and the total sum of the array isn't necessarily the sum of absolute difference between $$$a_j$$$ and $$$i^j$$$ for all $$$0 \le j \le n - 1$$$. You can check it for yourself.

pranav_18

In B problem, if the input is suppose 1,13,4 is this not already power sequence but according to the solution provided the cost will come as 3, as first we will sort and then increment 13 to 16 so the array becomes 1,4,16. Can somebody please tell me, am i getting something wrong from the quetion is'nt the cost supposed to be zero?

I think you should reread the statement for further information. Remember the common base c must be a positive integer.

LeoPro

In the div1 D editorial: "It can be proven that $$$f_x$$$ is non-decreasing, i.e. if $$$x<y$$$, then $$$f_x<f_y$$$." There is a minor typo — $$$f_x \le f_y$$$

Fixed. Thanh you!

hrishabh314

I might be wrong, but the problems (B, C, D) should've been cyclically rotated. D felt easier than B and C to me.

17je35541

in problem stones game , what happend if the stones are 2,2,2 . according editorial HL is winner but according to sample problem T is winner, so it is wrong solution

I don't see [2,2,2] in the sample problem...You may have misread something...

AcF-_-FcA

-8

Thank you for the fastest tutorial!

Lolboyyyy

In div 1 C editorial there is a small typo: "Therefore, we will calculate $$$dp(i,0/1)$$$ as the minimum time to finish first $$$a_i−1$$$ stages.."

It should be "the minimum time to finish first $$$i-1$$$ stages.."

It was fixed, thank you!

hardy_9795

Can someone give a simpler proof for Stoned Game.I am not able to understand that when each pile has atmost sum/2 stones then how can we find the solution.Why it does not depends on the order of moves and only on the parity of total stones.

It'll be helpful to break the question into smaller parts and analyse it. Firstly, it is easy to see that if there is an element greater than $$$\lfloor \frac{sum}{2} \rfloor$$$, T can keep picking from it and win. Secondly, if we ignore the rule that one cannot choose a pile that has been chosen in the previous turn, it is easy to see that the solution depends on the parity of $$$sum$$$.

Now the interesting part — if initially there is no element greater than $$$\lfloor \frac{sum}{2} \rfloor$$$, either of the players can ensure that this condition will never hold on the other player's turn, i.e. there will never be an element greater than $$$\lfloor \frac{sum}{2} \rfloor$$$ on the other player's turn (think about how this can be done). Who will want to ensure this condition will not hold? Simple, it will be the player who would win if there was no restriction on the pile to be chosen, so if parity of $$$sum$$$ is $$$1$$$ it will be T else it would be HL.

mystery__coder

I am sorry for asking late but I am not able to understand div1 C/div2. E. The boss can move to adjacent stages , does it mean the boss can move to adjacent only one time then return to its original state?

In editorial, it is said that return to this stage later to kill the boss. I didn't get how will we always find the boss in this stage and will it always be optimal.

Thanks in advance:)

piaoy

in stone game, greedily choose the pile with most stones (for both players) seems to be able to AC.. 109435178

lior5654

3 years ago, # |

1C is bashable even if you don't notice the observation in the editorial and the fact that r1 <= r2 <= r3. submission: https://codeforces.net/contest/1396/submission/122626784

arpitkus

7 months ago, # |

← Rev. 5 →

Div 2 D, 5 2 3 4 2 3 1 --> with 7 piles 5 5 5 4 1 --> With 3 piles, the sum of stones is the same in both game setups! Can we convert one setup into another keeping the maximum element same?

DatVu's blog

1397A - Juggling Letters

1397B - Power Sequence

1396A - Multiples of Length

1396B - Stoned Game

1396C - Monster Invaders