Hello everyone, this is the editorial for Codeforces Round 558 (Div. 2). I hope you enjoy the problem as well as I did!
Author: ArguteOnAir
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
using namespace std;
int main ()
{
int n, m;
cin >> n >> m;
cout << (m ? min(m, n - m) : 1) << endl;
return 0;
}
1163B2 - Cat Party (Hard Edition)
Author: Shirone
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1e5 + 10;
int n, color, ans, mx, f[N], cnt[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &color);
cnt[f[color]]--;
f[color]++;
cnt[f[color]]++;
mx = max(mx, f[color]);
bool ok = false;
if (cnt[1] == i) // every color has occurence of 1
ok = true;
else if (cnt[i] == 1) // only one color has the maximum occurence and the occurence is i
ok = true;
else if (cnt[1] == 1 && cnt[mx] * mx == i - 1) // one color has occurence of 1 and other colors have the same occurence
ok = true;
else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1) // one color has the occurence 1 more than any other color
ok = true;
if (ok)
ans = i;
}
printf("%d", ans);
return 0;
}
1163C2 - Power Transmission (Hard Edition)
Author: GreymaneSilverfang
Tutorial
Tutorial is loading...
Implementation
#include <cstdio>
#include <map>
#include <set>
#include <utility>
const int N = 1001;
int x[N], y[N];
std::map<std::pair<int,int>,std::set<long long>> slope_map;
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &x[i], &y[i]);
long long total = 0, res = 0;
for (int i = 1; i <= n - 1; ++i)
for (int j = i + 1; j <= n; ++j)
{
int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
// construct a line passing through (x1, y1) and (x2, y2)
// line is expressed as equation ax - by = c with constant a, b, c
int a = y1 - y2, b = x1 - x2;
// simplify equation
int d = gcd(a, b); a /= d, b /= d;
if (a < 0 || (a == 0 && b < 0))
{
a = -a;
b = -b;
}
// lines with the same slope (same a, b) are stored in a map
std::pair<int,int> slope(a, b);
long long c = 1LL * a * x1 - 1LL * b * y1;
if (!slope_map[slope].count(c))
{
++total;
slope_map[slope].insert(c);
// if this line is new, it intersects every line with different slope
res += total - slope_map[slope].size();
}
}
printf("%lld\n", res);
}
Author: Kuroni
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int K = 1005, N = 55, M = 55, INF = 1E9 + 7;
int k, n, m;
int kmp_s[N], nxt_s[N][26], kmp_t[M], nxt_t[M][26];
int dp[K][N][M];
char code[K], s[N], t[M];
void init(char s[], int n, int kmp[], int nxt[][26])
{
kmp[1] = 0;
for (int i = 2; i <= n; i++)
{
int cur = kmp[i - 1];
while (cur > 0 && s[cur + 1] != s[i])
cur = kmp[cur];
if (s[cur + 1] == s[i])
++cur;
kmp[i] = cur;
}
for (int i = 0; i <= n; i++)
for (char c = 'a'; c <= 'z'; c++)
{
int cur = i;
while (cur > 0 && s[cur + 1] != c)
cur = kmp[cur];
if (s[cur + 1] == c)
++cur;
nxt[i][c - 'a'] = cur;
}
}
int main()
{
scanf("%s%s%s", code + 1, s + 1, t + 1);
k = strlen(code + 1); n = strlen(s + 1); m = strlen(t + 1);
init(s, n, kmp_s, nxt_s); init(t, m, kmp_t, nxt_t);
for (int i = 0; i <= k; i++)
for (int ks = 0; ks <= n; ks++)
for (int kt = 0; kt <= m; kt++)
dp[i][ks][kt] = -INF;
dp[0][0][0] = 0;
for (int i = 0; i < k; i++)
for (int ks = 0; ks <= n; ks++)
for (int kt = 0; kt <= m; kt++)
for (char c = 'a'; c <= 'z'; c++)
if (code[i + 1] == '*' || code[i + 1] == c) // we now add/replace the (i + 1)-th character
{
int ns = nxt_s[ks][c - 'a'], nt = nxt_t[kt][c - 'a'];
int tmp = dp[i][ks][kt] + (ns == n) - (nt == m); // add the new occurrences if any
dp[i + 1][ns][nt] = max(dp[i + 1][ns][nt], tmp);
}
int ma = -INF;
for (int ks = 0; ks <= n; ks++)
for (int kt = 0; kt <= m; kt++)
ma = max(ma, dp[k][ks][kt]);
printf("%d\n", ma);
}
Author: Kuroni
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200005;
int n, a[N];
vector<int> basis, vec;
void add(int u)
{
int tmp = u;
// we keep the basis sorted in decreasing order
for (int &v : basis)
u = min(u, u ^ v);
if (u > 0) // u is a new element in the basis
{
basis.push_back(u);
vec.push_back(tmp);
// now we move u up until the basis is decreasingly sorted again
for (int i = basis.size() - 1; i > 0; i--)
if (basis[i] > basis[i - 1])
swap(basis[i], basis[i - 1]);
else
break;
}
}
void gray_code(int size)
{
vector<int> ans = {0};
for (int i = 0; i < size; i++)
for (int j = (1 << i) - 1; j >= 0; j--)
ans.push_back(ans[j] ^ vec[i]);
for (int &v : ans)
printf("%d ", v);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", a + i);
sort(a, a + n);
int pt = 0, x = 0;
for (int i = 1; i < 20; i++)
{
for (; pt < n && a[pt] < (1 << i); pt++)
add(a[pt]);
if (basis.size() == i)
x = i;
}
basis.clear();
vec.clear();
for (int i = 0; i < n && a[i] < (1 << x); i++)
add(a[i]);
printf("%d\n", x);
gray_code(x);
}
Implementation with DFS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 200005, MX = 1E6 + 5;
int n, x = 0, a[N];
bool vis[MX];
vector<int> basis, vec, ans;
void add(int u)
{
int tmp = u;
for (int &v : basis)
u = min(u, u ^ v);
if (u > 0)
{
basis.push_back(u);
vec.push_back(tmp);
for (int i = basis.size() - 1; i > 0; i--)
if (basis[i] > basis[i - 1])
swap(basis[i], basis[i - 1]);
else
break;
}
}
void DFS(int u, int it = 0)
{
ans.push_back(u);
vis[u] = true;
if (it == (1 << x) - 1)
return;
for (int &v : vec)
if (!vis[u ^ v])
{
DFS(u ^ v, it + 1);
return;
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", a + i);
sort(a, a + n);
int pt = 0;
for (int i = 1; i < 20; i++)
{
for (; pt < n && a[pt] < (1 << i); pt++)
add(a[pt]);
if (basis.size() == i)
x = i;
}
basis.clear();
vec.clear();
for (int i = 0; i < n && a[i] < (1 << x); i++)
add(a[i]);
printf("%d\n", x);
DFS(0);
for (int &v : ans)
printf("%d ", v);
}
Author: Kuroni
Tutorial
Tutorial is loading...
Implementation
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 2E5 + 5, M = 2E5 + 5;
const long long INF = 1E18 + 7;
int n, m, q, ed, nw, mx, u[M], v[M], w[M], ind[M];
int tr[N], le[N], ri[N];
bool on_path[N];
long long dis[2][N];
struct TNode
{
int u;
long long val;
TNode(int _u, long long _val)
{
u = _u;
val = _val;
}
inline bool operator>(const TNode &oth) const
{
return val > oth.val;
}
};
priority_queue<TNode, vector<TNode>, greater<TNode>> pq;
struct TEdge
{
int v, w, ind;
TEdge(int _v, int _w, int _ind)
{
v = _v;
w = _w;
ind = _ind;
}
};
vector<TEdge> adj[N];
struct TTree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1
long long tr[4 * M];
void build(int l, int r, int i)
{
tr[i] = INF;
if (l == r)
return;
build(l, m, lc);
build(m + 1, r, rc);
}
void upd(int l, int r, int i, int L, int R, long long v)
{
if (l > R || r < L || L > R)
return;
if (L <= l && r <= R)
{
tr[i] = min(tr[i], v);
return;
}
upd(l, m, lc, L, R, v);
upd(m + 1, r, rc, L, R, v);
}
long long que(int l, int r, int i, int u)
{
if (l == r)
return tr[i];
return min(tr[i], u <= m ? que(l, m, lc, u) : que(m + 1, r, rc, u));
}
#undef m
#undef lc
#undef rc
} seg;
void dijkstra(int st, long long dis[], int get = 0)
{
fill(dis + 1, dis + n + 1, INF);
pq.push(TNode(st, dis[st] = 0));
while (!pq.empty())
{
TNode u = pq.top(); pq.pop();
if (u.val > dis[u.u])
continue;
for (TEdge &v : adj[u.u])
if (dis[v.v] > u.val + v.w)
{
tr[v.v] = v.ind;
if (get == 1 && !on_path[v.v])
le[v.v] = le[u.u];
else if (get == 2 && !on_path[v.v])
ri[v.v] = ri[u.u];
pq.push(TNode(v.v, dis[v.v] = u.val + v.w));
}
}
}
void trace()
{
on_path[1] = true; le[1] = ri[1] = 0;
for (int i = 1, cur = 1; cur != n; i++)
{
int edge = tr[cur];
ind[edge] = mx = i;
cur = u[edge] ^ v[edge] ^ cur;
on_path[cur] = true;
le[cur] = ri[cur] = i;
}
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d", u + i, v + i, w + i);
ind[i] = -1;
adj[u[i]].push_back(TEdge(v[i], w[i], i));
adj[v[i]].push_back(TEdge(u[i], w[i], i));
}
dijkstra(n, dis[1]); // reverse the initial dijkstra for the trace to increase from 1 -> n
trace();
dijkstra(1, dis[0], 1);
dijkstra(n, dis[1], 2);
seg.build(1, mx, 1);
for (int i = 1; i <= m; i++)
if (ind[i] == -1)
{
seg.upd(1, mx, 1, le[u[i]] + 1, ri[v[i]], dis[0][u[i]] + w[i] + dis[1][v[i]]);
seg.upd(1, mx, 1, le[v[i]] + 1, ri[u[i]], dis[0][v[i]] + w[i] + dis[1][u[i]]);
}
while (q--)
{
scanf("%d%d", &ed, &nw);
long long ans;
if (ind[ed] > 0)
{
ans = dis[0][n] - w[ed] + nw;
if (nw > w[ed])
ans = min(ans, seg.que(1, mx, 1, ind[ed]));
}
else
{
ans = dis[0][n];
if (nw < w[ed])
{
ans = min(ans, dis[0][u[ed]] + nw + dis[1][v[ed]]);
ans = min(ans, dis[0][v[ed]] + nw + dis[1][u[ed]]);
}
}
printf("%lld\n", ans);
}
}
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
Fast editorial :)
Thanks!
The way Grey code was included in E, so natural, I can only say it was extremely elegant. Another kudo for you guys. ;)
can you please explain the solution for E a little bit more? I didn't get it :(
I really liked problem B.
Problem E is just beautiful.
You can say it was magical :D
in your if block of add function, no need to sort. again, great problem!
"such that the xor value of any two consecutive elements belongs to the basis; or in other words, the corresponding bitmask of any two consecutive elements in the magical permutation differs by exactly 1 bit." Can you explain this part?
Suppose the elements needed to create basis are $$$v_0, v_1, ... v_{x - 1}$$$.
Suppose x = 2; Grey code is,
00 01 11 10
Now you can create magical permutation by taking xor's of all $$$v_i$$$'s for all set bits i. In this case magical permutation is$$$0$$$, $$$v_0$$$, $$$v_1\oplus v_0$$$, $$$v_1$$$
really good problem set, I need more clarification about the counting techniques in problem B, any help would be appreciated
You use 2 counting arrays, one for counting the occurrence of colors, and one for counting the number of colors which have the same occurrences. You can have a look at the implementation for more details.
About idea maintain a "max" variable: frequency that appears most often. I see this brilliant. Maintain count[] and freq[] are also very beautiful. How can you come up with this solution ? Do we have any similar problems using this technique ? Thanks so much.
could you please explain in a bit more detail. Didnt understand how to implement the same, even after going through the implementation code
Thanks
Why long double fails for C whereas double passes ?
When you use floating point numbers there are always rounding errors. Using
double
just happens to discard the rounding errors < $$$10^{15}$$$ so something actually wrong (likea == b
) just happens to work.Do NOT use floating point numbers in problems like this. They'll catch you and knock down you, maybe in an important contest.
Is there any possible test case that would fail for
double
as well?Rounding off of double leads to incorrect key for mappings.
On 32-bit x86 machines (for example, Codeforces runners)
map<double, ...>
is essentially broken because x87 registers use 80-bit representation while the result stored into the memory is truncated into 64-bit. It only "works" because of blind luck.Maybe
map<volatile double, int>
will work (sincevolatile
forces the value to be stored into the memory and eliminates the "existence" of 80-bit value).Even if SSE is used (for e.g on x86-64) or we somehow workaround this x87 problem,
a1/b1
anda2/b2
may be different but truncated to the same value. I'm not sure if it could happen under the constraint of this problem.Thank You.
Iterating through the given array of colors from 1 to n I figure out if given size satisfies the condition or not. If it does, I store it in variable "answer", since we need the maximum one.
So the interesting part, How Do I know, if given subarray from 1 to say k satisfies the condition? I have two additional arrays and a set. The set just stores different colors I have seen so far.
1) vector count_colors stores number of colors I have seen so far. For example, If I had seen color "9" 3 times in the given array, count_colors[9] = 3 2) vector count_numbers stores number of groups with i values in each. For example, I had seen color "9" 3 times in the given array, color "10" 3 times and color "7" 1 time, then count_numbers[1] = 1 for "7" and count_numbers[3] = 2 for "9" and "10". Also I keep track of maximum value in count_numbers, can do it on each change since we keep seeing colors and numbers never decrease.
So, at first I have not seen any color. When seeing new color, I add it to set of seen colors. Then I decrease value of previous value of count_numbers[count_colors[colors[i]]]--; There are 1 less groups consisting of 7 elements, for example, and 1 more group consisting of 8 ones, that is the logic. I also increase count_colors[colors[i]]++; by definition. max_num = max (max_num, count_colors[colors[i]]); gets updated here too.
Now for the checking part. There are 3 cases that I check for. 1) All values met once -> answer is yes, we can remove any. I think I did unnecessary comparison in the second part in my code though, that should be enough. We can remove any hat and be left with none or again each hat met once, that satisfies the answer 2) One value seen once and others seen x times, x > 1. I check count_numbers[1] to be equal to 1, some color group consists of only one element. Then I check if count_numbers[max_num] == num_seen.size() — 1. x should be equal to max_num, otherwise there is third value between 1 and x. And number of groups of size max_num should be num_seen.size(), number of seen minus 1 that is one separate value. 3) One value bigger than all others by one, so that when we remove such element, it would again satisfy condition. I check for count_numbers[max_num] == 1, one element group is maximum. And count_numbers[max_num — 1] == num_seen.size() — 1, others are in amounts of maximum — 1. .
Can you tell me how can you come up with this data structure ? Or we just need to practice more ? I see the idea of maintain a "max" variable: frequency that has maximum color. How can we come up with this idea ?
No data structure needed, just using vectors. I just thought about the variables that we need to get the answer and maintained them.
why is using unordered_map and erasing from the map when the count of that frequency becomes 0, instead of vector and max variable giving tle. https://codeforces.me/contest/1163/submission/209654842
I tried using a map instead of an unordered map to avoid collisions. this should work with complexity on nlogn. https://codeforces.me/contest/1163/submission/209654905
I even tried using a vector for the frequency count of frequencies of color and using a set to keep track of frequencies present, the idea of max variable didn't strike. https://codeforces.me/contest/1163/submission/209656518
I don't see why my second and third approaches don't work
Can someone suggest similar problems to D since many people said it is standard?
Are you sure about time complexity of D? should it not be c*|s|*|t|*26?
The exact complexity is indeed $$$O(26 * |c| * |s| * |t|)$$$, but I removed the constant to simplify it.
Any links to the tutorial for solving such problems using Gaussian elimination ? Also any links for learning general Gaussian elimination?
For learning Gaussian elimination, you may refer this: https://cp-algorithms.com/linear_algebra/linear-system-gauss.html
For C, is this really true...?
I wonder how about such cases like 4x + 6y = 5 and 2x + 3y = 4, which are parallel
(My code in the contest time had this same bug)
Ah, now I understand Such a case like 4x + 6y = 5 does not occur, for this has no integer solutions: gcd(a, b) and gcd(a, b, c) always coincide
My code got accepted for C1. But it is giving wrong answer in C2. Can someone please help
Assuming your logic is correct throughout the code, the only thing that I think could cause this is if you are not using longs as you generate the final answer in C2.
Thanks, missed the fact that set.size() returns int value.
Problem F is almost the same as 《故乡的梦》 on bzoj(which is a Chinese OJ). Anyway,Problem E is very interesting.(Although some part of this problem appeared in Atcoder AGC 31 C) :D
AGC031 C actually inspired this problem :)
can someone help me with my code for D?
I am getting RE on test 18.
We can optimize problem D even further. Suppose at a dp state, we have $$$ks \leq kt$$$, then we don't even need to save $$$ks$$$ as a state, because we can directly calculate $$$ks$$$ using $$$kt$$$. Hence, the number of dp states are now only $$$O(|c| \cdot \max(|s|, |t|))$$$.
Problem D can be solved in a better way.
We build an ACAM(Aho-Corasick Automaton) for $$$s$$$ and $$$t$$$ and then we do dynamic programming on the ACAM.
Let $$$dp_{i,j}$$$ be the largest answer we can get in a walk on the ACAM which consists of $$$j$$$ steps and ends at node $$$i$$$. Initially $$$dp_{rt,0}=0$$$ and the others are $$$-\infty$$$, where $$$rt$$$ denotes the root of the trie of the ACAM. Finally the answer is the maximum value of all those $$$dp_{i,|c|}$$$s where i denotes a node on the ACAM. Do not forget to add all $$$i$$$'s fail-nodes' value to $$$i$$$'s value.
The time complexity is $$$O(26\times |c|\times (|s|+|t|))$$$.
An ACAM can deal with similar problems with 2 strings or more. How nice! :D
Code: 53944139
can someone tell me what's wrong with my solution?
I am not sure why am I getting wrong answer for bigger values of N. https://codeforces.me/contest/1163/submission/53945287
The precision of float is not enough, try double.
thanks, that got me an AC, finally...
For D, What's the complexity that get the nxt array?
$$$O(|s|^{2} + |t|^{2})$$$
Thanks.
Use Aho-Corasick automation,Problem D's Complexity can be O(|c|⋅(|s|+|t|)).
I think the tests of the problem E is not strong enough.
Here is my solution: https://codeforces.me/contest/1163/submission/53950641
Here is the hacking test:
But my solution gets:
It is obviously wrong. Because my solution thinks if it is possible to get all $$$2^i\ (0 \leq i \leq x)$$$ from the basis, $$$x$$$ is going to be valid. Maybe not only me wrote like that.
In problem C2 tutorial, can anyone explain why c=y1x2−y2x1 ?
Equation of a line is (y-y1)=m(x-x1) now m=(y2-y1)/(x2-x1) now try to change this formula in form of equation of line y=mx+c You will get c=y1x2-y2x1.
E can be solved in $$$O(n+MAX)$$$ by using counting sort and Gray code.53956574
Can you explain "We now iterate over these "blocks" of parallel lines and count the number of pairs each block contributes — a block of size s gives s(s−1)2 pairs." ?? And in problem B, why cnt[mx — 1] * (mx — 1) == i — mx && cnt[mx] == 1 is one color has the occurence 1 more than any other color ?? I don't understand. Thank you very much <3 <3 <3
Thanks for the round!
Can someone explain a bit more in detail solution for D? What exactly is the array nxt[N][26], and how it is constructed? I know about KMP as algorithm for finding pattern in text in O(N) time complexity.
you can view nxt[i][c] as, i (before) matched length, c new char, nxt will be (after) matched length. similar in KMP search method, [26] just pre-process those possibility.
Need help for problem C2. Why my submission giving WA. Even it is working fine at IDE.
Because of double comparison (use on map and set) I think.
Rounding off of double leads to incorrect key for mappings.
I'm having trouble understanding one detail for problem F. To handle the case that an edge $$$e$$$ on the main path increases in cost, we need a way to find the shortest path from $$$1$$$ to $$$N$$$ not using $$$e$$$. The proposed approach generates a set of candidate paths, each of which avoids some interval of edges on the main path, and finds the shortest among those avoiding $$$e$$$. How can we prove that for every $$$e$$$, the shortest possible distance will certainly appear within that set of candidates?
Now if for each $$$u$$$, $$$l_u$$$ is tightly bounded, i.e. every shortest path from $$$1$$$ to $$$u$$$ must uses the first $$$l_u$$$ edges of the main path (same analogy for tight $$$r_u$$$), then the the set shortest possible distance not using the edge $$$e$$$ is maximized.
Now, what if $$$l_u$$$ and $$$r_u$$$ is not tightly bounded? I will call the tight bound of $$$l_u$$$ as $$$tl_u$$$, and tight bound of $$$r_u$$$ as $$$tr_u$$$. I will skip over this part a little fast, but basically take the shortest path using the tight bound $$$tl_u$$$ and $$$tr_v$$$ of a candidate edge $$$(u, v)$$$, and let's call the set of edges on this shortest path from $$$tl_u$$$ to $$$tr_v$$$ as $$$S_e$$$. Then I can prove that the union of the ranges $$$l_{u_e}$$$, $$$r_{v_e}$$$ of all the edges belong to this $$$S_e$$$ set to be exactly $$$tl_u$$$ to $$$tr_v$$$, without any interruption. So, in one way or another, the value of the shortest path that must pass through the candidate edge $$$(u, v)$$$ will appear in the range $$$tl_u$$$ to $$$tr_v$$$, regardless of the values of $$$l_u$$$ and $$$r_v$$$.
My way of solving B is maintaining a multiset of the counts of each color. At each step, it is possible if
(1st element is 1 and 2nd element = greatest element)
or(1st element = next-to-last element and next-to-last element = last element - 1)
.Can anyone help me? I am unable to find where I am going wrong. This is my solution for problem C2(Power Transmission), I am getting wrong answer on test 10. link: https://codeforces.me/contest/1163/submission/53963521 Thank You.
fil.size() return unsigned int (4bytes) on codeforces which will overflow when multiply.
Thanks
In C2 code implementation , I didn't understand this part . please help me --- // simplify equation int d = gcd(a, b); a /= d, b /= d; if (a < 0 || (a == 0 && b < 0)) { a = -a; b = -b; }
Why does https://codeforces.me/contest/1163/submission/53983303 get accepted but https://codeforces.me/contest/1163/submission/53982305 give wrong answer?
I am getting wrong answer on test case 10 in Power transmission( Hard version ) Is there any corner case in problem?
Can someone please elaborate editorial's idea on solving D, in more detail?
I will try explaining how i solved it :)
well ... solid understanding of kmp and dynamics would do to solve this one // let f(id,ks , kt) be the recursive function ... we will call f(0,0,0 ) to get our answer ... // here id,ks ,kt represents current index of mysterios code, string s and string t ... respectively and base case will be when id >= length of ( mysterios code )
so we will try to maximize ans as follows
i will explain for ks ... for kt its similar
nxt_s[ks ][ i ] it represents where should we shift ks for i th char of mysteriosString or length of maximum matching prefix of s till now
example ....
mysteriosString : xabaabaa
string s : abaa
so string s occurs 2 times in mysteriosString
so say ... i = 4, ks = 3 , then nxt_s[ks][4] = 3..
// i = 5 (which is character b ) , ks = 3 ;
we will adjust ks to 3 here because
we want maximum matching prefix which is also a suffix ... so nxt_s[ks][5] = 1 ...
hope u have understood till now and code bottom up yourself :)
I discussed a solution here
I tried submitting problem D's solution in practice without precomputing the next arrays, which the Author's solution does and it passed in almost the same time as the solution with the next arrays precomputed. Here's the code: 53966779
The solution has a worst case complexity of $$$O(26*|c|*|s|*|t|*max(|s|,|t|))$$$. So how can it pass? Is it because of weak test cases or is there a reason for this?
Anyone has come across any similar questions like D? Plz put their link.
Could anyone provide a clear explanation for problem D pls ?
In the problem E, why does the dfs-solution (the second solution attached on the tutorial) works? Gray-Code works obviously, but I can not prove we can replace it with a simple dfs. (or am I misreading something?)
That's what I was surprised with to be honest, at the beginning I wrote this DFS to try and hack it, but it ended up as a completely viable solution :/
Since when I DFS like in the implementation, the first usable bit is always used, the sequence of the bit changed is actually the same as the Gray code, i.e. the bit changed are $$$0$$$, $$$1$$$, $$$0$$$, $$$2$$$, $$$0$$$, $$$1$$$, $$$0$$$, $$$3$$$, $$$0$$$, $$$1$$$, ... So, the DFS will trace a straight path of $$$2^x - 1$$$ numbers right away, since it is the same as Gray code.
Wow, so we can construct gray-code simply by using succinct DFS. I didn't know that.
Problem D : (Just Discussing a solution)
1. Given strings S and A , both contain lowercase English char only , we have to count how many occurrences of A in S. ...what we will do?..KMP right? so , we have LPS[] for string A.
( LPS[i] = length of " longest prefix which is also suffix " of sub-string A[0...i])
. Let's make an recursive implementation of KMP.2. Now assume S can have some '*' which can be replaced by any char in between 'a'-'z' . How many occurrences now ?....KMP again..but we need LPS[i][c] now.
Where LPS[i][c] = length of " longest prefix which is also suffix " of string( A[0...i] + (char)(c+'a') );
what change will come in our above recursive solution?...3. Now come to our actual problem D. We need two different lps arrays LPS_A[][] and LPS_B[][] . how the func will change now?
4. we're actually done!..just need to pre-calculate two LPS arrays using brute force and trivial dp memoization .Code
Hi, this solution: http://codeforces.me/contest/1163/submission/54373882 returns WA for both C1 and C2, but in my IDE it returns the correct answer. Is there a problem with the compiler? Thanks.
I didn't watch your code carefully, but as someone earlier said — using floating point numbers in such problems is a big NO NO. Try to remake your algorithm so that you operate only on integers.
Alright, thanks a lot.
db m = (a[i].second — a[j].second)/ ((a[i].first — a[j].first) * 1.0); The value of slope m lies in the range (-INF, +INF). db cannot store slope when it exceeds the capacity of db.
Ok, thanks, but still I don't get why I get the correct answer on my computer. Could someone test it yourselves locally? Thanks a lot.
why does ceil function doesn't work in my solution??solution link-> https://codeforces.me/contest/1163/submission/54708474
Help in C: Giving WA for large test cases... My logic for C is: Calculate number of distinct lines . then find total number of intersections.
And then from total, subtract all the parallel lines which won't be intersecting. Suppose for slope m , then are k parallel lines. Then subtract k*(k-1)/2 from total.
Do this for all the slopes.
Its giving WA for large test cases. Submission link: Submission Link Question Link: Question Link
Thanks in advance:)
KMP state for the replaced sub-code to be ks and kt
Can anyone explain this line from the editorial of problem D
What is KMP state??
Could someone explain problem D to me? I understand that the
kmp
array is the prefix function, but what is thenxt
array supposed to be?