Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
s = input()
ans = True
n = len(s)
for j in range(n):
if (j == 0 or s[j] != s[j - 1]) and (j == n - 1 or s[j] != s[j + 1]):
ans = False
print('YES' if ans else 'NO')
1671B - Consecutive Points Segment
Idea: vovuh
Tutorial
Tutorial is loading...
Solution (vovuh)
for i in range(int(input())):
n = int(input())
x = list(map(int, input().split()))
print('YES' if x[-1] - x[0] - n + 1 <= 2 else 'NO')
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, x) = readLine()!!.split(' ').map { it.toInt() }
val a = readLine()!!.split(' ').map { it.toInt() }.sorted()
var sum = a.sumOf { it.toLong() }
var prevDay = -1L
var ans = 0L
for (i in n - 1 downTo 0) {
val curDay = if (x - sum >= 0) (x - sum) / (i + 1) else -1
ans += (i + 1) * (curDay - prevDay)
prevDay = curDay
sum -= a[i]
}
println(ans)
}
}
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n, x;
scanf("%d%d", &n, &x);
vector<int> a(n);
forn(i, n) scanf("%d", &a[i]);
long long ans = 1e18;
long long cur = 0;
forn(i, n - 1){
cur += abs(a[i] - a[i + 1]);
}
forn(_, 2){
long long mn = abs(a[0] - 1);
ans = min(ans, cur + abs(a[0] - x) + (x - 1));
forn(i, n - 1){
ans = min(ans, cur + mn - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - x));
ans = min(ans, cur - abs(a[i] - a[i + 1]) + abs(a[i] - x) + abs(a[i + 1] - 1) + (x - 1));
mn = min(mn, 0ll - abs(a[i] - a[i + 1]) + abs(a[i] - 1) + abs(a[i + 1] - 1));
}
ans = min(ans, cur + mn + abs(a.back() - x));
reverse(a.begin(), a.end());
}
printf("%lld\n", ans);
}
return 0;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(42);
const int MOD = 998244353;
const int K = 3;
int add(int x, int y, int mod = MOD)
{
x += y;
while(x >= mod) x -= mod;
while(x < 0) x += mod;
return x;
}
int sub(int x, int y, int mod = MOD)
{
return add(x, -y, mod);
}
int mul(int x, int y, int mod = MOD)
{
return (x * 1ll * y) % mod;
}
int binpow(int x, int y, int mod = MOD)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x, mod);
y /= 2;
x = mul(x, x, mod);
}
return z;
}
bool prime(int x)
{
for(int i = 2; i * 1ll * i <= x; i++)
if(x % i == 0)
return false;
return true;
}
int get_base()
{
int x = rnd() % 10000 + 4444;
while(!prime(x)) x++;
return x;
}
int get_modulo()
{
int x = rnd() % int(1e9) + int(1e8);
while(!prime(x)) x++;
return x;
}
typedef array<int, K> hs;
hs base, modulo;
void generate_hs()
{
for(int i = 0; i < K; i++)
{
base[i] = get_base();
modulo[i] = get_modulo();
}
}
hs operator+(const hs& a, const hs& b)
{
hs c;
for(int i = 0; i < K; i++)
{
c[i] = add(a[i], b[i], modulo[i]);
}
return c;
}
hs operator-(const hs& a, const hs& b)
{
hs c;
for(int i = 0; i < K; i++)
{
c[i] = sub(a[i], b[i], modulo[i]);
}
return c;
}
hs operator*(const hs& a, const hs& b)
{
hs c;
for(int i = 0; i < K; i++)
{
c[i] = mul(a[i], b[i], modulo[i]);
}
return c;
}
hs operator^(const hs& a, const hs& b)
{
hs c;
for(int i = 0; i < K; i++)
{
c[i] = binpow(a[i], b[i], modulo[i]);
}
return c;
}
hs char_hash(char c)
{
hs res;
for(int i = 0; i < K; i++)
res[i] = c - 'A' + 1;
return res;
}
const int N = 18;
const int V = 1 << N;
string s;
char buf[V + 43];
int n;
int ans[V + 43];
hs vertex_hash[V + 43];
bool is_leaf(int x)
{
return (x * 2 + 1) >= ((1 << n) - 1);
}
void rec(int x)
{
vertex_hash[x] = char_hash(s[x]);
ans[x] = 1;
if(is_leaf(x))
{
return;
}
rec(x * 2 + 1);
rec(x * 2 + 2);
vertex_hash[x] = vertex_hash[x] + (base ^ vertex_hash[2 * x + 1]) + (base ^ vertex_hash[2 * x + 2]);
ans[x] = mul(ans[2 * x + 1], ans[2 * x + 2]);
if(vertex_hash[2 * x + 1] != vertex_hash[2 * x + 2])
ans[x] = mul(ans[x], 2);
}
int main()
{
generate_hs();
scanf("%d", &n);
scanf("%s", buf);
s = buf;
rec(0);
cout << ans[0] << endl;
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int K = 13;
const int MOD = 998244353;
int n, k, x;
int cnt[K][K][K];
int dp[K][2 * K][K][K];
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
y /= 2;
x = mul(x, x);
}
return z;
}
void precalc()
{
cnt[2][1][1] = 1;
cnt[3][1][2] = 2;
cnt[3][2][3] = 1;
cnt[4][1][3] = 3;
cnt[4][1][4] = 1;
cnt[4][2][3] = 1;
cnt[4][2][4] = 4;
cnt[4][2][5] = 3;
cnt[4][3][6] = 1;
cnt[5][1][4] = 4;
cnt[5][1][5] = 2;
cnt[5][1][6] = 2;
cnt[5][2][4] = 4;
cnt[5][2][5] = 12;
cnt[5][2][6] = 12;
cnt[5][2][7] = 9;
cnt[5][2][8] = 3;
cnt[5][3][5] = 2;
cnt[5][3][6] = 4;
cnt[5][3][7] = 6;
cnt[5][3][8] = 6;
cnt[5][3][9] = 4;
cnt[5][4][10] = 1;
cnt[6][1][5] = 5;
cnt[6][1][6] = 3;
cnt[6][1][7] = 4;
cnt[6][1][8] = 3;
cnt[6][1][9] = 1;
cnt[6][2][5] = 10;
cnt[6][2][6] = 28;
cnt[6][2][7] = 35;
cnt[6][2][8] = 35;
cnt[6][2][9] = 30;
cnt[6][2][10] = 17;
cnt[6][2][11] = 8;
cnt[6][3][5] = 1;
cnt[6][3][6] = 13;
cnt[6][3][7] = 29;
cnt[6][3][8] = 41;
cnt[6][3][9] = 44;
cnt[6][3][10] = 45;
cnt[6][3][11] = 30;
cnt[6][4][7] = 1;
cnt[6][4][8] = 4;
cnt[6][4][9] = 7;
cnt[6][4][10] = 7;
cnt[6][4][11] = 11;
cnt[7][1][6] = 6;
cnt[7][1][7] = 4;
cnt[7][1][8] = 6;
cnt[7][1][9] = 6;
cnt[7][1][10] = 6;
cnt[7][1][11] = 2;
cnt[7][2][6] = 20;
cnt[7][2][7] = 55;
cnt[7][2][8] = 80;
cnt[7][2][9] = 95;
cnt[7][2][10] = 101;
cnt[7][2][11] = 94;
cnt[7][3][6] = 6;
cnt[7][3][7] = 50;
cnt[7][3][8] = 118;
cnt[7][3][9] = 186;
cnt[7][3][10] = 230;
cnt[7][3][11] = 260;
cnt[7][4][7] = 3;
cnt[7][4][8] = 18;
cnt[7][4][9] = 48;
cnt[7][4][10] = 85;
cnt[7][4][11] = 113;
cnt[7][5][10] = 2;
cnt[7][5][11] = 4;
cnt[8][1][7] = 7;
cnt[8][1][8] = 5;
cnt[8][1][9] = 8;
cnt[8][1][10] = 9;
cnt[8][1][11] = 11;
cnt[8][2][7] = 35;
cnt[8][2][8] = 96;
cnt[8][2][9] = 155;
cnt[8][2][10] = 207;
cnt[8][2][11] = 250;
cnt[8][3][7] = 21;
cnt[8][3][8] = 145;
cnt[8][3][9] = 358;
cnt[8][3][10] = 616;
cnt[8][3][11] = 859;
cnt[8][4][7] = 1;
cnt[8][4][8] = 26;
cnt[8][4][9] = 124;
cnt[8][4][10] = 313;
cnt[8][4][11] = 567;
cnt[8][5][9] = 3;
cnt[8][5][10] = 16;
cnt[8][5][11] = 53;
cnt[9][1][8] = 8;
cnt[9][1][9] = 6;
cnt[9][1][10] = 10;
cnt[9][1][11] = 12;
cnt[9][2][8] = 56;
cnt[9][2][9] = 154;
cnt[9][2][10] = 268;
cnt[9][2][11] = 389;
cnt[9][3][8] = 56;
cnt[9][3][9] = 350;
cnt[9][3][10] = 898;
cnt[9][3][11] = 1654;
cnt[9][4][8] = 8;
cnt[9][4][9] = 126;
cnt[9][4][10] = 552;
cnt[9][4][11] = 1404;
cnt[9][5][9] = 4;
cnt[9][5][10] = 48;
cnt[9][5][11] = 204;
cnt[9][6][11] = 1;
cnt[10][1][9] = 9;
cnt[10][1][10] = 7;
cnt[10][1][11] = 12;
cnt[10][2][9] = 84;
cnt[10][2][10] = 232;
cnt[10][2][11] = 427;
cnt[10][3][9] = 126;
cnt[10][3][10] = 742;
cnt[10][3][11] = 1967;
cnt[10][4][9] = 36;
cnt[10][4][10] = 448;
cnt[10][4][11] = 1887;
cnt[10][5][9] = 1;
cnt[10][5][10] = 43;
cnt[10][5][11] = 357;
cnt[10][6][11] = 6;
cnt[11][1][10] = 10;
cnt[11][1][11] = 8;
cnt[11][2][10] = 120;
cnt[11][2][11] = 333;
cnt[11][3][10] = 252;
cnt[11][3][11] = 1428;
cnt[11][4][10] = 120;
cnt[11][4][11] = 1302;
cnt[11][5][10] = 10;
cnt[11][5][11] = 252;
cnt[11][6][11] = 5;
cnt[12][1][11] = 11;
cnt[12][2][11] = 165;
cnt[12][3][11] = 462;
cnt[12][4][11] = 330;
cnt[12][5][11] = 55;
cnt[12][6][11] = 1;
}
int inv[K];
int C(int n, int k)
{
if(n < 0 || n < k || k < 0) return 0;
int res = 1;
for(int i = n; i > n - k; i--)
res = mul(res, i);
for(int i = 1; i <= k; i++)
res = mul(res, inv[i]);
return res;
}
void prepare()
{
for(int i = 1; i < K; i++)
inv[i] = binpow(i, MOD - 2);
precalc();
dp[0][0][0][0] = 1;
for(int i = 0; i < K; i++)
for(int j = 0; j < 2 * K; j++)
for(int a = 0; a < K - 2; a++)
for(int b = 0; b < K - 2; b++)
{
if(dp[i][j][a][b] == 0) continue;
for(int add_cnt = 2; add_cnt < K; add_cnt++)
for(int add_desc = 1; add_desc <= K - 2; add_desc++)
for(int add_inv = 1; add_inv <= K - 2; add_inv++)
{
if(j + add_cnt >= 2 * K || a + add_desc > K - 2 || b + add_inv > K - 2) continue;
int& nw = dp[i + 1][j + add_cnt][a + add_desc][b + add_inv];
nw = add(nw, mul(dp[i][j][a][b], cnt[add_cnt][add_desc][add_inv]));
}
}
}
void solve()
{
scanf("%d %d %d", &n, &k, &x);
if(k == 0 && x == 0)
{
puts("1");
return;
}
int ans = 0;
for(int i = 1; i < K; i++)
for(int j = 1; j < 2 * K; j++)
if(dp[i][j][x][k] != 0)
{
ans = add(ans, mul(dp[i][j][x][k], C(n - j + i, i)));
}
printf("%d\n", ans);
}
int main()
{
prepare();
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
solve();
}
I've known that F needed precalc,but I didn't solve it.qwq
In fact, when $$$n > k^2$$$ holds, the answer is a $$$O(k)$$$-degree polynomial. So you can use lagrange interpolation to solve this problem without precalc.
I see,probably.
Could I see your code to understand further?
You can see A-SOUL_Diana's Code. 154556037
thanks!
An interesting thing about problem b I found, the difference between the first element and the last element cannot exceed $$$n + 1$$$. as long as the difference is less than or equal to $$$n + 1$$$ the answer is always yes. I'm not the best at proofs, but I think this is because the greatest difference between a series of $$$n$$$ consecutive integers is always $$$n - 1$$$, and our operations can increase the first element by one and decrease the last element by one, thereby shrinking the maximum difference between elements by two at most. So if the maximum difference is greater than $$$n - 1 + 2$$$ then the answer is no. What I can't figure out is why the ones in the middle can always seem to fix themselves if this is true. Still, this solution works in $$$O(1)$$$.
my code
Basically you are describing the same equation as the one in the solution: x[n-1]-x[0]-n+1 <= 2 <=> x[n-1]-x[0] <= n+1
I actually solved this like a dumb person by shifting x[0] to the right or keeping it where it is and checking if everyone of the next elements can be shifted to the proper position according to where x[0] is fixed. So my complexity is O(2n) = O(n). Still works since reading the input is also O(n), but my solution is roughly 3 times slower than necessary.
From my understanding, the solution described by the creator of the problem refers only to how many gaps there are between the first and last elements. If there are 0 gaps we're done, if there's one we can just shift one side and connect it with the other and if there are 2 gaps we shift 2 "chunks" so that everything is connected. On the other hand, if there are 3 or more gaps (which will make the inequality you referred to become false), then if one thinks about it, he will realize that there is no way to shift those 3 or more "chunks" in a way that they can be consecutive.
The O(1) solution blew my mind on how simple it was. This problem caused me to overthink :D
How to come up with alternative solution of F?
[deleted]
It's not that contest
Can someone explain the hashing solution for E?
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Can someone send code for precalculation in 1671F - Permutation Counting ?
It seems that problem F can be solves with dp, but without precalc. But how to do that?
I was thinking that as well,and had a original idea.
Can someone help me see where my B problem is going wrong,This caused my crash and lower rate my code
This happens because if the answer is
NO
your code goes to end and doesn't input remaining numbers. So they will be in the next test case and all numeration of the input numbers breaks so your code gots WA. To fix it your need to input ALL numbers even if the answer isNO
now.Thank you very much! ! ! It was a stupid mistake T_T
I modified it, but it still seems to have a problem code
This happens because your solution can print two
NO
instead one. You must append the wordcontinue;
after the first check in cycle to not run the second check if the first check is alreadyNO
. And you will get AC then.So, I have managed to create a test that hacks the hashes in the model solution for problem E. Now, my curiosity is: when hacking a solution, what does the checker use to find out what the correct answer to that given test is? Since if it would use the model solution, using a test like this, on which the model solution gives a wrong answer, could hack every solution, even the correct ones, and also make the problem impossible to solve if added to the testcases.
I've changed the model solution so that it is deterministic now, so the checker will compare the answer to the deterministic solution. Most likely the outcome will be something like "unexpected verdict" on hack since one of presumably correct solutions in Polygon is challenged.
By the way, how do you hack the model solution? I thought this way of hashing subtrees worked well.
What I have done is:
try random trees with n=5 until two give the same first hash (takes about 60k tries on average)
try trees with n=11 constructed as follows: first 6 layers are all 'A', and each of the subtrees under the 7th layer is a random one between the 2 found in step 1, this guarantees that the first hash will still give the same value to all the trees generated like so. And try until two trees give the same second hash (about 60k tries as well).
same as step 2, but this time with n=17, and the subtrees under the 7th layer being a random one out of the 2 found before, until two trees give the same third hash (also around 60k tries)
Do you mean that you've hacked the hashes with seed $$$42$$$? awoo always replaces generator seeds to $$$42$$$ when posting randomized solutions in editorials. You can try uphacking the solution, but most likely it won't work since the random generator seed in the actual solution is not $$$42$$$. Instead, it's time-dependent.
oh, yeah, I have hacked the one with seed 42, it makes sense for the actual solution to be time dependent.
Can someone explain why https://codeforces.net/contest/1671/submission/155171162 is failing on test case 5? Cannot find the bug...
Can someone explain the part of editorial on problem D which says "you can insert 1 somewhere, then insert x somewhere. The rest of insertions will be free." Why will be the rest of the insertions be free?
If you have 1, x somewhere or x, 1 somewhere than you can insert arbitrarily any element between 1 to x in between them for 0 cost , I will discuss 1, x case you can do x, 1 similarly , Now suppose you insert 1<c<x between 1 and x , cost will be (x — c) + (c — 1) = x — 1, so it's free now we know if 2 are adjacent it holds true imagine there are some elements already in between 1 and x
1 C1 C2 x, it won't matter what order C1, C2 are in you can insert 1 < c < x between 1, C1 or C1, C2 or C2, x depending on which range it lies in, it will definitely be between more than one of the 3 ranges So cost of insertion will again be 0
In problem E, can anyone explain how are we checking the equality of equivalence classes using just the lexicographically smallest string in preorder?
(ans) variable is the sum of the differences of the initial value, and (mn) refers to min element of the initial array and (mx) refer to max element of initial array
My Submission
here's the solution to E (without hashing)
can somebody please tell what is the problem with my sumission https://codeforces.net/contest/1671/submission/281132373 its passing test case 3 but failing in 4 and i cannot understand why or if somebody can just tell what is test case 4 checking so i can work on that aspect of my code