All themes written by AkiLotus (I am the only one in the team playing Cytus II anyway :D).
1293A - ConneR and the A.R.C. Markland-N
Author: xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: xuanquang1999, AkiLotus
Tutorial
Tutorial is loading...
Solution (Akikaze, C++)
Submission link: 69149995
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, s, k;
vector<int> a;
void Input() {
cin >> n >> s >> k; a.clear(); a.resize(k);
for (auto &z: a) cin >> z;
}
void Solve() {
for (int i=0; i<=k; i++) {
if (s-i >= 1 && find(a.begin(), a.end(), s-i) == a.end()) {cout << i << endl; return;}
if (s+i <= n && find(a.begin(), a.end(), s+i) == a.end()) {cout << i << endl; return;}
}
assert(false); // if reached this line, the solution failed to find a free floor
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int T; cin >> T; while (T--) {Input(); Solve();} return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69150848
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static PrintWriter out = new PrintWriter(System.out, true);
public static int n, s, k;
public static int[] a;
public static boolean exist(int[] arr, int x) {
for (int i=0; i<arr.length; i++) {
if (arr[i] == x) return true;
}
return false;
}
public static void Input() {
n = sc.nextInt(); s = sc.nextInt(); k = sc.nextInt();
a = new int[k];
for (int i=0; i<k; i++) a[i] = sc.nextInt();
}
public static void Solve() {
for (int i=0; i<=k; i++) {
if (s-i >= 1 && !exist(a, s-i)) {out.println(i); return;}
if (s+i <= n && !exist(a, s+i)) {out.println(i); return;}
}
assert false; // if reached this line, the solution failed to find a free floor
}
public static void main(String[] args) {
int t = sc.nextInt();
while (t-- > 0) {Input(); Solve();}
}
}
Solution (Akikaze, Python 3)
Submission link: 69150816
Source code in plain text
T = int(input())
for test_no in range(T):
n, s, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(0, k+1):
if s-i >= 1 and not s-i in a:
print(i); break
if s+i <= n and not s+i in a:
print(i); break
else: assert(False) # if reached this line, the solution failed to find a free floor
1293B - JOE is on TV!
Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus
Tutorial
Tutorial is loading...
Solution (Akikaze, C++)
Submission link: 69151243
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n;
void Input() {
cin >> n;
}
void Solve() {
double ans = 0;
for (int i=1; i<=n; i++) ans += 1.0 / i;
cout << fixed << setprecision(12) << ans << endl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
Input(); Solve(); return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69151737
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static PrintWriter out = new PrintWriter(System.out, true);
public static int n;
public static void Input() {
n = sc.nextInt();
}
public static void Solve() {
double ans = 0;
for (int i=1; i<=n; i++) ans += 1.0 / i;
out.printf("%.12f\n", ans);
}
public static void main(String[] args) {
Input(); Solve();
}
}
Solution (Akikaze, Python 3)
Submission link: 69151256
Source code in plain text
T = 1
for test_no in range(T):
n = int(input())
ans = sum([1.0 / i for i in range(1, n+1)])
print(ans)
1292A - NEKO's Maze Game
Author: xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: AkiLotus
Tutorial
Tutorial is loading...
Video editorial
Solution (Akikaze, C++)
Submission link: 69151594
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, q;
vector<vector<int>> lava;
void Input() {
cin >> n >> q;
lava.resize(2, vector<int>(n, 0));
}
void Solve() {
int blockedPair = 0;
while (q--) {
int x, y; cin >> x >> y; x--; y--;
int delta = (lava[x][y] == 0) ? +1 : -1;
lava[x][y] = 1 - lava[x][y];
for (int dy=-1; dy<=1; dy++) {
if (y+dy < 0 || y+dy >= n) continue;
if (lava[1-x][y+dy] == 1) blockedPair += delta;
}
cout << ((blockedPair == 0) ? "Yes\n" : "No\n");
}
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
Input(); Solve(); return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69151628
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static PrintWriter out = new PrintWriter(System.out, true);
public static int n, q;
public static int[][] lava;
public static void Input() {
n = sc.nextInt(); q = sc.nextInt();
lava = new int[2][n];
}
public static void Solve() {
int blockedPair = 0;
while (q-- > 0) {
int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
int delta = (lava[x][y] == 0) ? +1 : -1;
lava[x][y] = 1 - lava[x][y];
for (int dy=-1; dy<=1; dy++) {
if (y+dy < 0 || y+dy >= n) continue;
if (lava[1-x][y+dy] == 1) blockedPair += delta;
}
if (blockedPair == 0) out.println("Yes");
else out.println("No");
}
}
public static void main(String[] args) {
Input(); Solve();
}
}
Solution (Akikaze, Python 3)
Submission link: 69151636
Source code in plain text
T = 1
for test_no in range(T):
n, q = map(int, input().split())
lava = [[0 for j in range(n)] for i in range(2)]
blockedPair = 0
while q > 0:
q -= 1
x, y = map(lambda s: int(s)-1, input().split())
delta = +1 if lava[x][y] == 0 else -1
lava[x][y] = 1 - lava[x][y]
for dy in range(-1, 2):
if y + dy >= 0 and y + dy < n and lava[1-x][y+dy] == 1:
blockedPair += delta
if blockedPair == 0: print('Yes')
else: print('No')
1292B - Aroma's Search
Author: AkiLotus feat. xuanquang1999
Development: xuanquang1999, AkiLotus
Editorialist: AkiLotus
Tutorial
Tutorial is loading...
Solution (Akikaze, C++)
Submission link: 69152149
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
long long x0, y0, ax, ay, bx, by, xs, ys, t;
void Input() {
cin >> x0 >> y0 >> ax >> ay >> bx >> by;
cin >> xs >> ys >> t;
}
void Solve() {
vector<long long> x(1, x0), y(1, y0);
long long LIMIT = (1LL << 62) - 1;
while ((LIMIT - bx) / ax >= x.back() && (LIMIT - by) / ay >= y.back()) {
x.push_back(ax * x.back() + bx); y.push_back(ay * y.back() + by);
}
int n = x.size();
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
long long length = x[j] - x[i] + y[j] - y[i];
long long dist2Left = abs(xs - x[i]) + abs(ys - y[i]);
long long dist2Right = abs(xs - x[j]) + abs(ys - y[j]);
if (length <= t - dist2Left || length <= t - dist2Right) ans = max(ans, j-i+1);
}
}
cout << ans << endl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
Input(); Solve(); return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69152154
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static PrintWriter out = new PrintWriter(System.out, true);
public static long x0, y0, ax, ay, bx, by, xs, ys, t;
public static long abs(long x) {return ((x > 0) ? x : -x);}
public static void Input() {
x0 = sc.nextLong(); y0 = sc.nextLong();
ax = sc.nextLong(); ay = sc.nextLong(); bx = sc.nextLong(); by = sc.nextLong();
xs = sc.nextLong(); ys = sc.nextLong(); t = sc.nextLong();
}
public static void Solve() {
ArrayList<Long> x = new ArrayList<>(), y = new ArrayList<>();
x.add(x0); y.add(y0);
long LIMIT = ((long)1 << 62) - 1;
int n = x.size();
while ((LIMIT - bx) / ax >= x.get(n - 1) && (LIMIT - by) / ay >= y.get(n - 1)) {
x.add(ax * x.get(n - 1) + bx); y.add(ay * y.get(n - 1) + by); n++;
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
long length = x.get(j) - x.get(i) + y.get(j) - y.get(i);
long dist2Left = abs(xs - x.get(i)) + abs(ys - y.get(i));
long dist2Right = abs(xs - x.get(j)) + abs(ys - y.get(j));
if (length <= t - dist2Left || length <= t - dist2Right) {
ans = (ans > j-i+1) ? ans : (j - i + 1);
}
}
}
out.println(ans);
}
public static void main(String[] args) {
Input(); Solve();
}
}
Solution (Akikaze, Python 3)
Submission link: 69152156
Source code in plain text
T = 1
for test_no in range(T):
x0, y0, ax, ay, bx, by = map(int, input().split())
xs, ys, t = map(int, input().split())
LIMIT = 2 ** 62 - 1
x, y = [x0], [y0]
while ((LIMIT - bx) / ax >= x[-1] and (LIMIT - by) / ay >= y[-1]):
x.append(ax * x[-1] + bx)
y.append(ay * y[-1] + by)
n = len(x)
ans = 0
for i in range(n):
for j in range(i, n):
length = x[j] - x[i] + y[j] - y[i]
dist2Left = abs(xs - x[i]) + abs(ys - y[i])
dist2Right = abs(xs - x[j]) + abs(ys - y[j])
if (length <= t - dist2Left or length <= t - dist2Right): ans = max(ans, j-i+1)
print(ans)
1292C - Xenon's Attack on the Gangs
Author: xuanquang1999
Development: xuanquang1999
Editorialist: xuanquang1999
Tutorial
Tutorial is loading...
Solution (xuanquang1999, C++)
Submission link: 69152556
Source code in plain text
#include <bits/stdc++.h>
using namespace std;
int n, root;
vector<vector<int>> tree, par, sub;
vector<vector<long long>> dp;
void dfs(int u) {
sub[root][u] = 1;
for(int v: tree[u]) {
if (v == par[root][u])
continue;
par[root][v] = u;
dfs(v);
sub[root][u] += sub[root][v];
}
}
long long getDP(int u, int v) {
if (u == v) return 0;
if (dp[u][v] != -1) return dp[u][v];
long long res = sub[u][v] * sub[v][u] + max(getDP(par[v][u], v), getDP(u, par[u][v]));
return dp[u][v] = res;
}
void input() {
scanf("%d", &n);
tree.assign(n, vector<int>());
for(int i = 0; i < n-1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
--u; --v;
tree[u].push_back(v); tree[v].push_back(u);
}
}
void solve() {
// Preprocessing
par.assign(n, vector<int>(n, -1));
sub.assign(n, vector<int>(n, -1));
for(int u = 0; u < n; ++u) {
root = u;
dfs(u);
}
// Calculating DP
dp.assign(n, vector<long long>(n, -1LL));
long long ans = 0;
for(int u = 0; u < n; ++u)
for(int v = 0; v < n; ++v)
ans = max(ans, getDP(u, v));
cout << ans << endl;
}
int main() {
input();
solve();
return 0;
}
Solution (xuanquang1999, Java 8)
Submission link: 69152568
Source code in plain text
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
private static Scanner in;
private static PrintWriter out;
private static int n, root;
private static ArrayList<Integer>[] tree;
private static int[][] par, sub;
private static long[][] dp;
private static long getDP(int u, int v) {
if (u == v) return 0;
if (dp[u][v] != -1) return dp[u][v];
long res = sub[u][v] * sub[v][u] + Math.max(getDP(par[v][u], v), getDP(u, par[u][v]));
return dp[u][v] = res;
}
private static void dfs(int u) {
sub[root][u] = 1;
for(int v: tree[u]) {
if (v == par[root][u])
continue;
par[root][v] = u;
dfs(v);
sub[root][u] += sub[root][v];
}
}
private static void input() {
n = in.nextInt();
tree = new ArrayList[n];
for(int u = 0; u < n; ++u)
tree[u] = new ArrayList<>();
for(int i = 0; i < n-1; ++i) {
int u = in.nextInt(), v = in.nextInt();
u -= 1; v -= 1;
tree[u].add(v); tree[v].add(u);
}
}
private static void solve() {
// Preprocessing
par = new int[n][n];
sub = new int[n][n];
for(int u = 0; u < n; ++u) {
par[u][u] = -1;
root = u;
dfs(u);
}
// Calculating DP
dp = new long[n][n];
for(int u = 0; u < n; ++u)
for(int v = 0; v < n; ++v)
dp[u][v] = -1;
long ans = 0;
for(int u = 0; u < n; ++u)
for(int v = 0; v < n; ++v)
ans = Math.max(ans, getDP(u, v));
out.println(ans);
}
public static void main(String[] args) {
in = new Scanner(System.in);
out = new PrintWriter(System.out);
input();
solve();
out.close();
}
}
Solution (pajenegod, PyPy3)
Submission link: 72000655
Source code in plain text
import sys
# Read input and build the graph
inp = [int(x) for x in sys.stdin.buffer.read().split()]; ii = 0
n = inp[ii]; ii += 1
coupl = [[] for _ in range(n)]
for _ in range(n - 1):
u = inp[ii] - 1; ii += 1
v = inp[ii] - 1; ii += 1
coupl[u].append(v)
coupl[v].append(u)
# Relabel to speed up n^2 operations later on
bfs = [0]
found = [0]*n
found[0] = 1
for node in bfs:
for nei in coupl[node]:
if not found[nei]:
found[nei] = 1
bfs.append(nei)
new_label = [0]*n
for i in range(n):
new_label[bfs[i]] = i
coupl = [coupl[i] for i in bfs]
for c in coupl:
c[:] = [new_label[x] for x in c]
##### DP using multisource bfs
DP = [0] * (n * n)
size = [1] * (n * n)
P = [-1] * (n * n)
# Create the bfs ordering
bfs = [root * n + root for root in range(n)]
for ind in bfs:
P[ind] = ind
for ind in bfs:
node, root = divmod(ind, n)
for nei in coupl[node]:
ind2 = nei * n + root
if P[ind2] == -1:
bfs.append(ind2)
P[ind2] = ind
del bfs[:n]
# Do the DP
for ind in reversed(bfs):
node, root = divmod(ind, n)
ind2 = root * n + node
pind = P[ind]
parent = pind//n
# Update size of (root, parent)
size[pind] += size[ind]
# Update DP value of (root, parent)
DP[pind] = max(DP[pind], max(DP[ind], DP[ind2]) + size[ind] * size[ind2])
print(max(DP[root * n + root] for root in range(n)))
1292D - Chaotic V.
Author: AkiLotus
Development: AkiLotus
Editorialist: AkiLotus
Tutorial
Tutorial is loading...
Solution (Akikaze, C++)
Submission link: 69153064
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAXK = 5000;
int n; vector<int> cnt(MAXK + 1, 0);
vector<vector<int>> primeExponential(MAXK + 1, vector<int>(MAXK + 1, 0));
void Preprocess() {
for (int i=2; i<MAXK + 1; i++) {
for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
int tmp = i;
for (int x=2; x<=sqrt(tmp); x++) {
while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
}
if (tmp > 1) primeExponential[i][tmp]++;
}
}
void Input() {
cin >> n;
for (int i=0; i<n; i++) {
int k; cin >> k; cnt[k]++;
}
}
void Solve() {
Preprocess();
vector<int> bestPD(MAXK + 1, 1);
long long ans = 0, cur = 0;
for (int i=1; i<MAXK + 1; i++) {
if (!cnt[i]) {bestPD[i] = 1; continue;}
for (int j=1; j<MAXK + 1; j++) {
ans += 1LL * primeExponential[i][j] * cnt[i];
cur += 1LL * primeExponential[i][j] * cnt[i];
if (primeExponential[i][j]) bestPD[i] = j;
}
}
while (*max_element(bestPD.begin(), bestPD.end()) > 1) {
vector<int> frequency(MAXK + 1, 0);
for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];
int bestPrime = max_element(frequency.begin(), frequency.end()) - frequency.begin();
int bestGroup = frequency[bestPrime];
if (bestGroup * 2 <= n) break;
if (bestPrime == 1) break;
cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);
for (int i=0; i<MAXK + 1; i++) {
if (bestPD[i] != bestPrime) bestPD[i] = 1;
if (bestPD[i] == 1) continue;
primeExponential[i][bestPD[i]] -= 1;
while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
}
}
cout << ans << endl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
Input(); Solve(); return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69153077
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static PrintWriter out = new PrintWriter(System.out, true);
public static final int MAXK = 5000;
public static int n;
public static int[] cnt = new int[MAXK + 1];
public static int[][] primeExponential = new int[MAXK + 1][MAXK + 1];
public static long min(long a, long b) {return ((a < b) ? a : b);}
public static int max_element(int[] arr) {
int res = -1000000000;
for (int i=0; i<arr.length; i++) {
if (arr[i] > res) res = arr[i];
}
return res;
}
public static int max_id(int[] arr) {
int res = -1000000000, id = -1;
for (int i=0; i<arr.length; i++) {
if (arr[i] > res) {
res = arr[i];
id = i;
}
}
return id;
}
public static void Preprocess() {
for (int i=2; i<MAXK + 1; i++) {
for (int j=0; j<MAXK + 1; j++) primeExponential[i][j] += primeExponential[i-1][j];
int tmp = i;
for (int x=2; x<=Math.sqrt(tmp); x++) {
while (tmp % x == 0) {primeExponential[i][x]++; tmp /= x;}
}
if (tmp > 1) primeExponential[i][tmp]++;
}
}
public static void Input() {
n = sc.nextInt();
for (int i=0; i<n; i++) {
int k = sc.nextInt();
cnt[k] += 1;
}
}
public static void Solve() {
Preprocess();
int[] bestPD = new int[MAXK + 1];
for (int i=0; i<MAXK + 1; i++) bestPD[i] = 1;
long ans = 0, cur = 0;
for (int i=1; i<MAXK + 1; i++) {
if (cnt[i] == 0) {bestPD[i] = 1; continue;}
for (int j=1; j<MAXK + 1; j++) {
ans += (long)primeExponential[i][j] * cnt[i];
cur += (long)primeExponential[i][j] * cnt[i];
if (primeExponential[i][j] != 0) bestPD[i] = j;
}
}
while (max_element(bestPD) > 1) {
int[] frequency = new int[MAXK + 1];
for (int i=0; i<MAXK + 1; i++) frequency[bestPD[i]] += cnt[i];
int bestPrime = max_id(frequency);
int bestGroup = frequency[bestPrime];
if (bestGroup * 2 <= n) break;
if (bestPrime == 1) break;
cur -= bestGroup; cur += (n - bestGroup); ans = min(ans, cur);
for (int i=0; i<MAXK + 1; i++) {
if (bestPD[i] != bestPrime) bestPD[i] = 1;
if (bestPD[i] == 1) continue;
primeExponential[i][bestPD[i]] -= 1;
while (bestPD[i] > 1 && primeExponential[i][bestPD[i]] == 0) bestPD[i]--;
}
}
out.println(ans);
}
public static void main(String[] args) {
Input(); Solve();
}
}
Solution (Akikaze, PyPy 3)
Submission link: 69153090
Source code in plain text
T = 1
for test_no in range(T):
MAXK = 5000
n = int(input())
cnt = [0] * (MAXK + 1)
primeExponential = [[0 for j in range(MAXK + 1)] for i in range(MAXK + 1)]
line, num = (input() + ' '), 0
for c in line:
if c != ' ': num = num * 10 + (ord(c) - 48)
else:
cnt[num] += 1
num = 0
for i in range(2, MAXK + 1):
for j in range(0, MAXK + 1): primeExponential[i][j] += primeExponential[i-1][j]
tmp, x = i, 2
while x * x <= tmp:
while tmp % x == 0:
primeExponential[i][x] += 1
tmp //= x
x += 1
if tmp > 1: primeExponential[i][tmp] += 1
bestPD = [1] * (MAXK + 1)
ans, cur = 0, 0
for i in range(1, MAXK + 1):
if cnt[i] == 0: continue
for j in range(1, MAXK + 1):
ans += primeExponential[i][j] * cnt[i]
cur += primeExponential[i][j] * cnt[i]
if primeExponential[i][j]: bestPD[i] = j
frequency = [0] * (MAXK + 1)
while max(bestPD) > 1:
for i in range(MAXK + 1): frequency[i] = 0
for i in range(MAXK + 1): frequency[bestPD[i]] += cnt[i]
bestGroup = max(frequency)
bestPrime = frequency.index(bestGroup)
if bestGroup * 2 <= n: break
if bestPrime == 1: break
cur -= bestGroup
cur += (n - bestGroup); ans = min(ans, cur)
for i in range(MAXK + 1):
if bestPD[i] != bestPrime: bestPD[i] = 1
if bestPD[i] == 1: continue
primeExponential[i][bestPD[i]] -= 1
while bestPD[i] > 1 and primeExponential[i][bestPD[i]] == 0: bestPD[i] -= 1
print(ans)
1292E - Rin and The Unknown Flower
Author: low_ (Sulfox Remix)
Development: low_, Sulfox, AkiLotus
Editorialist: low_
Tutorial
Tutorial is loading...
Solution (Akikaze, C++)
Submission link: 69153383
Source code in plain text
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
int n, L, minID;
string s;
void fill(int id, char c) {
L -= (s[id] == 'L'); s[id] = c;
minID = min(minID, id);
}
void query(char cmd, string str) {
cout << cmd << " " << str << endl; cout.flush();
if (cmd == '?') {
int k; cin >> k;
assert(k != -1);
vector<int> a(k);
for (auto &z: a) {
cin >> z; z--;
for (int i=0; i<str.size(); i++) {
assert(s[z+i] == 'L' || s[z+i] == str[i]);
fill(z+i, str[i]);
}
}
}
else if (cmd == '!') {
int correct; cin >> correct;
assert(correct);
}
}
void Input() {
cin >> n; s.clear();
L = n; minID = n; s.resize(n, 'L');
}
void Solve() {
query('?', "CH"); query('?', "CO");
query('?', "HC"); query('?', "HO");
if (L == n) {
// the string exists in form O...OX...X, with X=C or X=H
// or it's completely mono-character
query('?', "CCC");
if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
else {
query('?', "HHH");
if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
else {
query('?', "OOO");
if (minID == n) {
// obviously n=4
query('?', "OOCC");
if (minID == n) {fill(0, 'O'); fill(1, 'O'); fill(2, 'H'); fill(3, 'H');}
}
if (s[n-1] == 'L') {
string t = s; t[n-1] = 'C';
if (t[n-2] == 'L') t[n-2] = 'C';
query('?', t);
if (s[n-1] == 'L') {
fill(n-1, 'H');
if (s[n-2] == 'L') fill(n-2, 'H');
}
}
}
}
}
else {
int maxID = minID; while (maxID < n-1 && s[maxID+1] != 'L') maxID++;
for (int i=minID-1; i>=0; i--) {
query('?', s.substr(i+1, 1) + s.substr(minID, maxID-minID+1));
if (minID != i) {
for (int x=0; x<=i; x++) fill(x, 'O');
break;
}
}
int nextFilled;
for (int i=maxID+1; i<n; i++) {
if (s[i] != 'L') continue;
nextFilled = i;
while (nextFilled < n && s[nextFilled] == 'L') nextFilled++;
query('?', s.substr(0, i) + s[i-1]);
if (s[i] == 'L') {
if (s[i-1] != 'O') fill(i, 'O');
else {
if (nextFilled == n) {
query('?', s.substr(0, i) + 'C');
if (s[i] == 'L') fill(i, 'H');
for (int x=i+1; x<nextFilled; x++) fill(x, s[i]);
}
else for (int x=i; x<nextFilled; x++) fill(x, s[nextFilled]);
i = nextFilled - 1;
}
}
}
}
query('!', s);
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int T; cin >> T; while (T--) {Input(); Solve();} return 0;
}
Solution (Akikaze, Java 8)
Submission link: 69153556
Source code in plain text
import java.io.*;
import java.util.*;
public class Akisolution {
public static Scanner sc = new Scanner(System.in);
public static class CPPString {
// as the Java String is insanely cryptic to modify
public char[] arr;
public CPPString() {}
public CPPString(String str) {this.arr = str.toCharArray();}
public CPPString(char[] ca) {this.arr = ca;}
public CPPString(CPPString other) {
this.arr = new char[other.arr.length];
for (int i=0; i<other.arr.length; i++) this.arr[i] = other.arr[i];
}
public void resize(int length, char defaultChar) {
this.arr = new char[length];
for (int i=0; i<length; i++) this.arr[i] = defaultChar;
}
public int size() {return this.arr.length;}
public CPPString substr(int L, int len) {
// get substring [L, L+len)
char[] res = new char[len];
for (int i=0; i<len; i++) res[i] = this.arr[L+i];
return new CPPString(res);
}
public CPPString add(char ch) {
char[] new_ca = new char[this.arr.length + 1]; new_ca[this.arr.length] = ch;
for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
return new CPPString(new_ca);
}
public CPPString add(CPPString other) {
char[] new_ca = new char[this.arr.length + other.arr.length];
for (int i=0; i<this.arr.length; i++) new_ca[i] = this.arr[i];
for (int i=0; i<other.arr.length; i++) new_ca[this.arr.length + i] = other.arr[i];
return new CPPString(new_ca);
}
@Override
public String toString() {return new String(arr);}
}
public static int n, L, minID;
public static CPPString s;
public static void fill(int id, char c) {
if (s.arr[id] == 'L') L--;
s.arr[id] = c;
minID = (minID < id) ? minID : id;
}
public static void query(char cmd, CPPString str) {
System.out.println(cmd + " " + str); System.out.flush();
System.err.println(cmd + " " + str);
if (cmd == '?') {
int k = sc.nextInt();
assert (k != -1);
int[] a = new int[k];
for (int index = 0; index < k; index++) {
a[index] = sc.nextInt() - 1;
for (int i=0; i<str.size(); i++) {
assert (s.arr[a[index]+i] == 'L' || s.arr[a[index]+i] == str.arr[i]);
fill(a[index]+i, str.arr[i]);
}
}
}
else if (cmd == '!') {
int correct = sc.nextInt();
assert (correct == 1);
}
}
public static void query(char cmd, String str) {
query(cmd, new CPPString(str));
}
public static void Input() {
n = sc.nextInt(); s = new CPPString();
L = n; minID = n; s.resize(n, 'L');
}
public static void Solve() {
query('?', "CH"); query('?', "CO");
query('?', "HC"); query('?', "HO");
if (L == n) {
// the string exists in form O...OX...X, with X=C or X=H
// or it's completely mono-character
query('?', "CCC");
if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
else {
query('?', "HHH");
if (minID < n) {for (int x=minID-1; x>=0; x--) fill(x, 'O');}
else {
query('?', "OOO");
if (minID == n) {
// obviously n=4
query('?', "OOCC");
if (minID == n) {
fill(0, 'O'); fill(1, 'O');
fill(2, 'H'); fill(3, 'H');
}
}
if (s.arr[n-1] == 'L') {
CPPString t = new CPPString(s); t.arr[n-1] = 'C';
if (t.arr[n-2] == 'L') t.arr[n-2] = 'C';
query('?', t);
if (s.arr[n-1] == 'L') {
fill(n-1, 'H');
if (s.arr[n-2] == 'L') fill(n-2, 'H');
}
}
}
}
}
else {
int maxID = minID; while (maxID < n-1 && s.arr[maxID+1] != 'L') maxID++;
for (int i=minID-1; i>=0; i--) {
query('?', s.substr(i+1, 1).add(s.substr(minID, maxID-minID+1)));
if (minID != i) {
for (int x=0; x<=i; x++) fill(x, 'O');
break;
}
}
int nextFilled;
for (int i=maxID+1; i<n; i++) {
if (s.arr[i] != 'L') continue;
nextFilled = i;
while (nextFilled < n && s.arr[nextFilled] == 'L') nextFilled++;
query('?', s.substr(0, i).add(s.arr[i-1]));
if (s.arr[i] == 'L') {
if (s.arr[i-1] != 'O') fill(i, 'O');
else {
if (nextFilled == n) {
query('?', s.substr(0, i).add('C'));
if (s.arr[i] == 'L') fill(i, 'H');
for (int x=i+1; x<nextFilled; x++) fill(x, s.arr[i]);
}
else for (int x=i; x<nextFilled; x++) fill(x, s.arr[nextFilled]);
i = nextFilled - 1;
}
}
}
}
query('!', s);
}
public static void main(String[] args) {
int T = sc.nextInt();
while (T-- > 0) {Input(); Solve();}
}
}
Solution (Akikaze, Python 3)
Submission link: 69153398
Source code in plain text
import sys
n, L, minID = None, None, None
s = []
def fill(id, c):
global n, L, s, minID
L -= (s[id] == 'L')
s = s[0:id] + c + s[id+1:]
minID = min(minID, id)
def query(cmd, str):
global n, L, s, minID
print(cmd, ''.join(str))
print(cmd, ''.join(str), file=sys.stderr)
sys.stdout.flush()
if (cmd == '?'):
result = list(map(int, input().split()))
assert(result[0] != -1)
for z in result[1:]:
z -= 1
for i in range(len(str)):
assert(s[z+i] == 'L' or s[z+i] == str[i])
fill(z+i, str[i])
elif (cmd == '!'):
correct = int(input())
assert(correct == 1)
T = int(input())
for test_no in range(T):
n = int(input())
L, minID = n, n
s = 'L' * n
query('?', "CH")
query('?', "CO")
query('?', "HC")
query('?', "HO")
if (L == n):
# the string exists in form O...OX...X, with X=C or X=H
# or it's completely mono-character
query('?', "CCC")
if (minID < n):
for x in range(minID-1, -1, -1): fill(x, 'O')
else:
query('?', "HHH")
if (minID < n):
for x in range(minID-1, -1, -1): fill(x, 'O')
else:
query('?', "OOO")
if (minID == n):
# obviously n=4
query('?', "OOCC")
if (minID == n):
fill(0, 'O')
fill(1, 'O')
fill(2, 'H')
fill(3, 'H')
if (s[n-1] == 'L'):
t = s[0:n-1] + 'C'
if (t[n-2] == 'L'): t = t[0:n-2] + 'C' + t[n-1:]
query('?', t)
if (s[n-1] == 'L'):
fill(n-1, 'H')
if (s[n-2] == 'L'): fill(n-2, 'H')
else:
maxID = minID
while (maxID < n-1 and s[maxID+1] != 'L'): maxID += 1
for i in range(minID-1, -1, -1):
query('?', s[i+1:i+2] + s[minID:maxID+1])
if (minID != i):
for x in range(i+1): fill(x, 'O')
break
nextFilled = None
i = maxID + 1
while i < n:
if (s[i] != 'L'):
i += 1
continue
nextFilled = i
while (nextFilled < n and s[nextFilled] == 'L'): nextFilled += 1
query('?', s[0:i] + s[i-1])
if (s[i] == 'L'):
if (s[i-1] != 'O'): fill(i, 'O')
else:
if (nextFilled == n):
query('?', s[0:i] + 'C')
if (s[i] == 'L'): fill(i, 'H')
for x in range(i+1, nextFilled): fill(x, s[i])
else:
for x in range(i, nextFilled): fill(x, s[nextFilled])
i = nextFilled - 1
i += 1
query('!', s)
1292F - Nora's Toy Boxes
Author: xuanquang1999 × MofK
Development: xuanquang1999
Editorialist: xuanquang1999
Tutorial
Tutorial is loading...
Solution (xuanquang1999, C++)
Submission link: 69153931
Source code in plain text
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
bool isSubset(int a, int b) {
return (a & b) == a;
}
bool isIntersect(int a, int b) {
return (a & b) != 0;
}
void add(int &a, long long b) {
a = (a + b) % MOD;
}
// Solve for each weakly connected component (WCC)
int cntOrder(vector<int> s, vector<int> t) {
int p = s.size(), m = t.size();
vector<int> inMask(m, 0);
for(int x = 0; x < p; ++x)
for(int i = 0; i < m; ++i)
if (t[i] % s[x] == 0)
inMask[i] |= 1 << x;
vector<int> cnt(1<<p, 0);
for(int mask = 0; mask < (1<<p); ++mask)
for(int i = 0; i < m; ++i)
if (isSubset(inMask[i], mask))
++cnt[mask];
vector<vector<int>> dp(m+1, vector<int>(1<<p, 0));
for(int i = 0; i < m; ++i)
dp[1][inMask[i]] += 1;
for(int k = 1; k < m; ++k) {
for(int mask = 0; mask < (1<<p); ++mask) {
for(int i = 0; i < m; ++i)
if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
add(dp[k+1][mask | inMask[i]], dp[k][mask]);
add(dp[k+1][mask], 1LL * dp[k][mask] * (cnt[mask] - k));
}
}
return dp[m][(1<<p)-1];
}
int n;
vector<int> a, degIn, s, t;
vector<vector<int>> graph;
vector<bool> visited;
void dfs(int u) {
visited[u] = true;
if (degIn[u] == 0)
s.push_back(a[u]);
else
t.push_back(a[u]);
for(int v: graph[u])
if (!visited[v])
dfs(v);
}
void input() {
scanf("%d", &n);
a.resize(n);
for(int u = 0; u < n; ++u)
scanf("%d", &a[u]);
}
void solve() {
// Pre-calculate C(n, k)
vector<vector<int>> c(n, vector<int>(n, 0));
for(int i = 0; i < n; ++i) {
c[i][0] = 1;
for(int j = 1; j <= i; ++j)
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
// Building divisibility graph
degIn.assign(n, 0);
graph.assign(n, vector<int>());
for(int u = 0; u < n; ++u) {
for(int v = 0; v < n; ++v) {
if (u != v && a[v] % a[u] == 0) {
graph[u].push_back(v);
graph[v].push_back(u);
++degIn[v];
}
}
}
// Solve for each WCC of divisibility graph and combine result
int ans = 1;
int curLen = 0;
visited.assign(n, false);
for(int u = 0; u < n; ++u) {
if (!visited[u]) {
s.clear();
t.clear();
dfs(u);
if (!t.empty()) {
int sz = t.size() - 1;
int cnt = cntOrder(s, t);
// Number of orders for current WCC
ans = (1LL * ans * cnt) % MOD;
// Number of ways to insert <sz> number to array of <curLen> elements
ans = (1LL * ans * c[curLen + sz][sz]) % MOD;
curLen += sz;
}
}
}
printf("%d\n", ans);
}
int main() {
input();
solve();
return 0;
}
Solution (xuanquang1999, Java 8)
Submission link: 69153932
Source code in plain text
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
private static Scanner in;
private static PrintWriter out;
private static final int MOD = (int)1e9 + 7;
private static int n;
private static int[] a, degIn;
private static ArrayList<Integer> s, t;
private static boolean[] visited;
private static ArrayList<Integer>[] graph;
private static boolean isSubset(int a, int b) {
return (a & b) == a;
}
private static boolean isIntersect(int a, int b) {
return (a & b) != 0;
}
// Solve for each weakly connected component (WCC)
private static int cntOrder(ArrayList<Integer> s, ArrayList<Integer> t) {
int p = s.size(), m = t.size();
int[] inMask = new int[m];
for(int x = 0; x < p; ++x)
for(int i = 0; i < m; ++i)
if (t.get(i) % s.get(x) == 0)
inMask[i] |= 1 << x;
int[] cnt = new int[1<<p];
for(int mask = 0; mask < (1<<p); ++mask)
for(int i = 0; i < m; ++i)
if (isSubset(inMask[i], mask))
++cnt[mask];
int[][] dp = new int[m+1][1<<p];
for(int i = 0; i < m; ++i)
dp[1][inMask[i]] += 1;
for(int k = 1; k < m; ++k) {
for(int mask = 0; mask < (1<<p); ++mask) {
for(int i = 0; i < m; ++i)
if (!isSubset(inMask[i], mask) && isIntersect(inMask[i], mask))
dp[k+1][mask | inMask[i]] = (int)((dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD);
dp[k+1][mask] = (int)((dp[k+1][mask] + (long)dp[k][mask] * (cnt[mask] - k)) % MOD);
}
}
return dp[m][(1<<p)-1];
}
private static void dfs(int u) {
visited[u] = true;
if (degIn[u] == 0)
s.add(a[u]);
else
t.add(a[u]);
for(int v: graph[u])
if (!visited[v])
dfs(v);
}
private static void input() {
n = in.nextInt();
a = new int[n];
for(int u = 0; u < n; ++u)
a[u] = in.nextInt();
}
private static void solve() {
// Pre-calculate C(n, k)
int[][] c = new int[n][n];
for(int i = 0; i < n; ++i) {
c[i][0] = 1;
for(int j = 1; j <= i; ++j)
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
}
// Building divisibility graph
degIn = new int[n];
graph = new ArrayList[n];
for(int u = 0; u < n; ++u)
graph[u] = new ArrayList<>();
for(int u = 0; u < n; ++u) {
for(int v = 0; v < n; ++v) {
if (u != v && a[v] % a[u] == 0) {
graph[u].add(v);
graph[v].add(u);
++degIn[v];
}
}
}
// Solve for each WCC of divisibility graph and combine result
int ans = 1;
int curLen = 0;
visited = new boolean[n];
for(int u = 0; u < n; ++u) {
if (!visited[u]) {
s = new ArrayList<>();
t = new ArrayList<>();
dfs(u);
if (!t.isEmpty()) {
int sz = t.size() - 1;
int cnt = cntOrder(s, t);
// Number of orders for current WCC
ans = (int)(((long)ans * cnt) % MOD);
// Number of ways to insert <sz> number to array of <curLen> elements
ans = (int)(((long)ans * c[curLen + sz][sz]) % MOD);
curLen += sz;
}
}
}
out.println(ans);
}
public static void main(String[] args) {
in = new Scanner(System.in);
out = new PrintWriter(System.out);
input();
solve();
out.close();
}
}
Solution (xuanquang1999, PyPy 3)
Submission link: 69153968
Source code in plain text
MOD = 1000000007
def isSubset(a, b):
return (a & b) == a
def isIntersect(a, b):
return (a & b) != 0
# Solve for each weakly connected component (WCC)
def cntOrder(s, t):
p = len(s)
m = len(t)
inMask = [0 for i in range(m)]
for x in range(p):
for i in range(m):
if t[i] % s[x] == 0:
inMask[i] |= 1 << x
cnt = [0 for mask in range(1<<p)]
for mask in range(1<<p):
for i in range(m):
if isSubset(inMask[i], mask):
cnt[mask] += 1
dp = [[0 for mask in range(1<<p)] for k in range(m+1)]
for i in range(m):
dp[1][inMask[i]] += 1
for k in range(m):
for mask in range(1<<p):
for i in range(m):
if not isSubset(inMask[i], mask) and isIntersect(inMask[i], mask):
dp[k+1][mask | inMask[i]] = (dp[k+1][mask | inMask[i]] + dp[k][mask]) % MOD
dp[k+1][mask] = (dp[k+1][mask] + dp[k][mask] * (cnt[mask] - k)) % MOD
return dp[m][(1<<p)-1]
def dfs(u):
global a, graph, degIn, visited, s, t
visited[u] = True
if degIn[u] == 0:
s.append(a[u])
else:
t.append(a[u])
for v in graph[u]:
if not visited[v]:
dfs(v)
def main():
global a, graph, degIn, visited, s, t
# Reading input
n = int(input())
a = list(map(int, input().split()))
# Pre-calculate C(n, k)
c = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
c[i][0] = 1
for j in range(1, i+1):
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD
# Building divisibility graph
degIn = [0 for u in range(n)]
graph = [[] for u in range(n)]
for u in range(n):
for v in range(n):
if u != v and a[v] % a[u] == 0:
graph[u].append(v)
graph[v].append(u)
degIn[v] += 1
# Solve for each WCC of divisibility graph and combine result
ans = 1
curLen = 0
visited = [False for u in range(n)]
for u in range(n):
if not visited[u]:
s = []
t = []
dfs(u)
if len(t) > 0:
sz = len(t) - 1
cnt = cntOrder(s, t)
# Number of orders for current WCC
ans = (ans * cnt) % MOD
# Number of ways to insert <sz> number to array of <curLen> elements
ans = (ans * c[curLen + sz][sz]) % MOD
curLen += sz
print(ans)
if __name__ == "__main__":
main()
When the codes will be available for tutorials?
After system testing. I want to be sure the solutions worked correctly (even though I tested them quite thoroughly on Polygon).
If you play Music Game well, you must have quick hands.
If you have quick hands, maybe you'll publish the fastest editorial!
Thanks for the fast editorial!
You already knew how fast the editorial of #538 was out right? :D
Can someone explain C for div2 ?
There are two cases in which it will not be possible to reach from 1,1 to 2,n, it will be if a diagonal or a straight vertical line is all lava, so keep track of current lava, and each time you get a new query chech if it creates or removes any diagonals. Maintain a count variable that will keep a track of such diagonals and vertical blockages.
Here is my solution https://codeforces.com/contest/1293/submission/69125834
In problem D, I run my code and the result on test 1 is 3 but codeforces gives my result is 34 Can someone help me? Sorry for my bad english
maybe you define a variable and have not set it to zero and it takes a random value from memory and memory of your system and codeforces are different !
Thanks a lots
Thanks for the fast tutorials and the music games!
As a rhythm game enthusiast, I was happy to see a round having rhythm game concept. Thanks for the round and fast editorial too!
*angry cyan sounds*
Sidenotes: For problem D1E, the key to solve this problem was to write a lot on scratch paper and try everything that comes to your mind possible, even if it sounds stupid. That's the key for most constructive problems xD
My initial idea was that the limit for all queries is 5/3, Sulfox said that it can be lowered to 3/2, but then in the middle of the night (6 months ago), I came up with a solutions that works for 1.4! But then we had to scrap the initial limit for n, which is [3, 100].
There is a simple, elegant solution for Div1E when n is at least 5. Unfortunately, I could not find a way to make it work when n = 4.
First ask CC, CH, and CO. This way, all C's are revealed except for (possibly) a C as the last letter.
Then ask OH and HH. Combined with the information we get from the CH query, this allows us to identify the locations of all H's except for (possibly) a H as the first letter.
We have now found all C's and H's in the interval [2, n-1]. Everything else in the interval is an O. Now we have to find the first and last letters.
At this point, if the first letter is still unknown, it can only be a H or an O; if the last letter is still unknown, it can only be a C or an O. Therefore there are up to 4 possibilities for these 2 letters (first and last). We ask any arbitrary 3 of these possibilities using queries of length n. If we still do not find the answer after these 3 queries, the answer has to be the remaining possibility that we did not ask.
The total energy used is 5/4 + 3/n^2, which is acceptable when n is at least 5.
UPDATE: Solved the n=4 case. The approach I used was to query CH, CC, CO, OH, HHH, OOO, then whenever we find some characters that match (or finish these 6 queries without finding any), we switch to brute force, searching for strings that are consistent with the results of previous queries. The energy usage analysis is too complex for me to provide in full here.
My submission: https://codeforces.com/contest/1292/submission/69161739
$$$N=4$$$ can be solved by bruteforcing decision trees, maybe with pruning branches that obviously don't work if it's too slow.
I have a solution that works for $$$N \ge 5$$$ too:
Can anyone tell me why my solution is giving TLE for problem A https://codeforces.com/contest/1293/submission/69109563
Copied from your code. Find out what's wrong here.
got it..thnx
For Div. 1 D — Chaotic V., I have a better solution:
Consider find the branch with most occurences once, from node $$$1$$$.
Because we have $$$\max p [p | x!] = \text{the biggest prime number less than or equal to } x$$$ for $$$x \ge 2$$$, so two number $$$a, b$$$ are in the same branch iff their previous primes(including itself) are the same.
That is, $$$a$$$ and $$$b$$$ are in the same prime gap.
So we pre-work $$$\mathrm{last}[x] = \text{previous prime of } x$$$, and find the most occurences prime gap. Let's say, $$$[p_x, p_{x + 1})$$$, then the distinct numbers are reduced to $$$p_{x + 1} - p_x$$$.
Then we only use $$$k_i \in [p_x, p_{x + 1})$$$ to construct the tree structure, which is relatively small.
So we have the complexity of $$$\mathcal O (MAXK \ln \ln MAXK \cdot \text{largest prime gap in } MAXK)$$$.
Then according to A005250 and A002386, we can solve the problem even if $$$MAXK \le {10}^5$$$.
Possible optimization: use virtual trees, maybe can reduce the number of nodes.
But how do you construct the tree structure for the reduced set without factorizing all numbers below $$$k_i$$$ anyway?
It would certainly be nice to have access to persistent maps/multisets...
My alternative solution using a virtual tree.
(To avoid confusion, I'll use $$$K$$$ to denote $$$MAXK$$$ in what follows.)
Note that $$$1!,2!,\dots,k!$$$ is a dfs-order(a.k.a Eulerian order) of the tree. Thus, computing the LCA of $$$k!$$$ and $$$(k+1)!$$$ can be done by finding the number of $$$k!$$$'s prime factors that are not less than $$$(k + 1)$$$'s largest prime factor, where a BIT works. After factorizing $$$1$$$ ~ $$$K$$$ and maintaining the BIT, we can build the virtual tree in $$$O(K)$$$, since the virtual tree has at most $$$2K$$$ nodes.
Then we just add weights to the nodes according to the input. The weighted centroid of the virtual tree is the proper node $$$P$$$.
The bottleneck is factorizing $$$1$$$ ~ $$$K$$$. In worst case it takes $$$O(K\sqrt{K})$$$ time, but in practice it runs rather fast.
Can anybody prove whether the complexity of factorizing $$$1$$$ ~ $$$K$$$ is less than $$$O(K\sqrt{K})$$$? I test locally and find my whole program of this problem finishes in 1s even if $$$K=500000$$$.
Very good solution! I think you can offline factorize $$$1 \sim K$$$ in $$$\mathcal O (K \log \log K)$$$?
Oh I see! Using Eratosthenes's Sieve works, I suppose.
(I must be a fool this morning...
Update : After carefully reading the standard program, I realized my solution is just a tiny optimization of the official solution, but it indeed optimized.
Combining 1.618's solution (virtual trees) and my "prime gap" observation, I think we can get an $$$\mathcal O (N + K \log \log K)$$$ solution? ($$$\log \log$$$ comes from Eratosthenes's Sieve, and the number of prime factors of $$$k!$$$(factorial of $$$k$$$), check Wikipedia : Prime omega function for more information)
Thanks for the useful editorial
My solution for E (passed in upsolving):
First of all, once we know that $$$t$$$ is a substring of $$$s$$$ from position $$$pos$$$, we can find the entire string for $$$2\sum_{i=|t|+1}^{n}\frac{1}{i^2}$$$ just by trying to add all letters one by one to the left or to the right and checking if the resulting string occurs in the required position. If $$$|t| = 2$$$ then this value is approximately $$$0.7502654672430585$$$.
Let's ask about
COandCH. If at least one of these strings is present in $$$s$$$ as a substring, then we apply the algorithm above, using only $$$\approx 1.25$$$. Otherwise our string is of type[OH]*C*.Let's find all occurrences of
OHandHO(cost $$$1$$$ so far). If there are none then our string is(O*|H*)C*. We use that $$$n\geq 4$$$ and ask aboutCCC, if there is none then aboutOOCandHHC, if there is none then aboutHHH...HandOOO...O, otherwise we know the string. If there isCCCthen we ask aboutOCCCandHCCCand find the string.If there are
OHorHOthen we find the whole string before the last block of non-Cletter. Then we just iterate over all possible counts ofCin the end and each time ask about the whole string.small doubt: (consider s-x is zero here) if i write my cpp code like
then the compiler does not go into the for loop but it if it is like:
and x is zero, the compiler goes into the if statement. anybody know why this is happening?
the compiler will calculate
1<=(s-x)first and the result is either 1 or 0 and then calculate1<=nor0<=nso this condition is always true.Anyone noticed ? Blog was written 6 days ago.
Yes. I have a weird habit of preparing things early, then publishing at the right moment.
Very nice problems! (except too weak pretests in Div2 D)
The complete solution set has arrived (except xuanquang1999's Python solution in Div1C, guess he's slept already so I'll contact him later).
Again, thanks for your participation.
in Editorail of D how it is known that if u Move from point i to j it will cover all node from i to j?
For three arbitrary points on the same line, namely $$$p_1$$$, $$$p_2$$$, $$$p_3$$$, we can easily see that the Manhattan distance from $$$p_1$$$ to $$$p_3$$$ is the sum of distances from $$$p_1$$$ to $$$p_2$$$ and from $$$p_2$$$ to $$$p_3$$$.
Applying for a whole segment of points will result in the same outcome, i.e. the total distance to move from point $$$i$$$ to $$$i+1, \ldots, j$$$ will be the same as moving straight from $$$i$$$ to $$$j$$$.
can someone explain why long double cannot solve div2B,even cannot pass the sample.it's right on my computer,but wa when i submit.https://codeforces.com/contest/1293/submission/69115420,https://codeforces.com/contest/1293/submission/69113841
While adding t / i to s in your code, you should cast to long double first.
Should be
s += (long double) t / i;t is already long double,no need to cast it
But i isn't
Just do it the way I mentioned above and it will work.
OK I think I get your confusion, I'm casting the whole calculation and not just t.
Link to submission here
it cannot work,i tried cast t to long double and the whole calculation,both wa,you can submit it
I linked my submission above
For div2 B, Can someone please give a mathematical proof for why not defeating all (n-1) opponents at once would not produce better result?
Mathematically why, (n-1)/n +1 < (1/n + 1/(n-1) + ... + 1)
I tried but failed to prove it.
as i don't know how to write summation symbol so i'm giving a piece of code: sum = 0; for(i = 1; i <= n; i++) { sum += 1.0/(n-(n-i)); }
hope you got the answer ^_^
Thanks for replying, but I guess you didn't get my question.I wanted a mathematical proof for the inequality I have written above, not the code for it.
For every $$$i \leq n$$$, it is true that $$$1/i \geq 1/n$$$ Then,
$$$1/2 \geq 1/n$$$
$$$1/3 \geq 1/n$$$
$$$...$$$
$$$1/n \geq 1/n$$$
If you sum them, you have $$$1/2 + 1/3 + ... + 1/n \geq (n-1)/n$$$.
Finally, add one on each side $$$(n-1)/n + 1 \leq 1/n + 1/(n - 1) + ... + 1$$$
Thanks, I got it.
view it this way to get 1 we need for sure to output 1/1 so if n=4 I could do 4/4 from the first round but if I kept decreasing 4 to 3 then two then one I will find out that the best solution is to always decrease n and I will end up with 1/1 in the end that's of course not a very mathimatical prove but more of a greedy prove but if you think it in reverse you can some how recursivly prove it .
Thanks..this is quite intuitive.
I have a simpler solution for div1 E.
For n>=5, query "CC","OC","HC","HO" and "HH". After that, all 'C' except that in S[1] and all 'H' except that in S[n] will be discovered. So we know S[2..n-1], and S[1] and S[n] both only have two possible values. The total cost is no more than $$$5\cdot\frac14+\frac1{(n-1)^2}+\frac1{n^2}\leq1.3525$$$.
For n=4, at first query "CC","OC","HC" and "HO". If S[1] or S[4] is discovered, then do the remaining part of the above algorithm. The total cost is no more than $$$5\cdot\frac14+\frac1{16}\leq1.3125$$$. Otherwise, if S[2] and S[3] are both discovered, instead of querying "HH", we go to find S[n] and S[1] immediately. The total cost is no more than $$$4\cdot\frac14+\frac19+2\cdot\frac1{16}<1.2362$$$. Otherwise no positions are not discovered and we still query "HH". If we find "HH", S[4] must be discovered, so the total cost is still no more than $$$1.3125$$$. If not, S[2..3]="OO". Then we can determine both S[1] and S[4] by querying "OOO". The total cost is no more than $$$5\cdot\frac14+\frac19<1.3612$$$.
It's always nice to have editorials with multiple coding languages, really helps newbie's.
Can someone help me? my code for div. 2D is failing for test case 44. I am inserting first 55 nodes in an array and using binary search on it, for finding the element with lowest distance. code
My submission for D is failing system tests because of the upper limit I have set while calculating the co-ordinates of the points. It passed when I set the upper limit as 3e16 but failed when I set it as 1e16+10 or 1e17. Can anyone please help me in finding a possible reason for this? I am unable to figure out how to set an appropriate limit as per the given constraints.
3e16 : https://codeforces.com/contest/1293/submission/69174932
1e17 : https://codeforces.com/contest/1293/submission/69174475
1e17 fail because 1e17*200 exceeds long long limit
1e16 fail because you can get to points like (1e16,2e16) if t=1e16 and (x,y)=(1e16,1e16)
Ahh okay. Understood my stupidity. So an upper limit just above 2e16 works. Thanks for your help!
It's probably because $$$10^{17} \cdot 100$$$ would overflow a 64-bit integer.
Understood. Thanks!! :D
Really nice explanations and clean code, thanks for your effort! I've personally really enjoyed this round:D
Can someone tell me why i am receiving TLE veridict on C problem of Division 2.
My code is : https://codeforces.com/contest/1293/submission/69194019
My algo is also solving the problem in O(n+q).
Interesting enough, both my solution and yours run faster in Python 3 than in PyPy 3.
However, my advice would be ditching out the dict (since a frequency 2D array can be constructed, using dict might be an overkill and waste a few more resources than needed).
please someone explain approach of Div-2 E in easy language?
can someone explain to me div 2 D (i understand how we got all of our ax,ay only)
Here's the solution I thought of first:
Assume that we start on the $$$z$$$-th data node. It is always optimal to first collect nodes in decreasing order, then if we reach node $$$0$$$ and still have time, to backtrack and collect from node $$$z+1$$$ onward, because it can be proven that $$$2 \cdot dist(node_z, node_0) \leq dist(node_z, node_{z+1})$$$.
For the case where we don't start at a data node, we can brute force all reachable data nodes as the first node to collect, then proceed as above with $$$t$$$ reduced accordingly. Total complexity $$$O((\log t)^2)$$$, with the possibility of further reduction to $$$O(\log t \log \log t)$$$ via binary search, but that's overkill.
I also thought the same way as you did at first, but I am getting wrong answer on test 44 from that approach. Can you tell me why?69440793
Your linked submission says accepted, not wrong answer
I am really very sorry mate. I meant this submission: 69438965
Two potential issues:
If I'm reading this right, you're generating points as long as
x0is less thanxs+t, but I see no similar check for the y axis. Is it possible that the y-axis overflowed and produced bogus points?This one seems to pick the closest point to $$$(x_s, y_s)$$$ as the data node to collect first, however I am uncertain that this is optimal. Due to the small number of reachable nodes, I simply brute force all of them as the first collected node.
Who's Joe?
https://youtu.be/mhrvlor1qH0 — video editorial for 1292A - NEKO's Maze Game, including some incorrect solutions and mistakes.
Can anyone explain to me AROMA'S SEARCH problem I'm not getting the solution?
AROMA'S SEARCH approach : Just generate the list of points first from x0 and y0 and these points are very less around <=60. Now just from xs,ys go to certain xi,yi pt in list and keeping going left from i to 0 and for every i keep a j that goes from i+1 to list end ... in such way u will cover all possible answers.. so just maintain a maximum of every answer.. Here is my solution for reference https://codeforces.com/contest/1293/submission/79121522
In DIv1 B / Div2 D can you explain this line Since ax,ay≥2, there are no more than log2(t) important nodes (in other words, k≤log2(t)). ?Assume that there is $$$ceil(log2(t))+1$$$ important nodes, the distance between the first and last node will be at least $$$2^{ceil(log2(t))}$$$, which is higher than $$$t$$$ in almost every case, and thus, the last node is not an important one any more (proof by contradiction).
pls ignore i got it
In the A problem, the office is in floor s-th. The number of closed floors is k, k limit is 1000, so if we search from s-1000 to s+1000 the maximum complexity would be 2000000. Here is the for-function recipe:
for(int i = max(1, s-1000); i <= min(lim, s + min(n-s, 1000)); ++i) { if(restaurant_at_floor[i] == 1) continue; // map it first else minfloor = min(abs(s-i), minfloor); // set minfloor = 1e9 } cout << minfloor << endl;^^ hopefully oc idea
Isn't it completely identical to the tutorial shown above?
[Deleted.]
lol, am I only one who solved C Div 2 using map<pair<int,int>,set<pair<int,int>>>?)) https://codeforces.com/contest/1293/submission/69836530
Errichto himself used set in his tutorial video too.
People are more used to arrays tbh, and also they're usually quite keen on execution time (sometimes even a log).
I have an O(n) solution for 1293A. 69928477
Your sorting made it $$$\mathcal{O}(k \log k )$$$ unfortunately.
have someone solved D with trie?
I have a better solution for Div1F and It's time complexity is $$$O(2^{\frac{max a_i}{6}} * n)$$$
72566459
I would like to see proof of 1292C - Xenon's Attack on the Gangs that it should be valley sequence.
Can anyone tell me where did I get wrong in Div1-C ?
My idea is using greedy to select the best edge available.
Submission: 96498313