1202A - You Are Given Two Binary Strings...
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main(args: Array<String>) {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val x = readLine()!!.reversed()
val y = readLine()!!.reversed()
val posY = y.indexOf('1')
val posX = x.indexOf('1', posY)
println(posX - posY)
}
}
1202B - You Are Given a Decimal String...
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
const val INF = 1e9.toInt()
fun main(args: Array<String>) {
val s = readLine()!!.map { it - '0' }
val cf = Array(10) {Array(10) {0}}
for (i in 1 until s.size)
cf[s[i - 1]][s[i]]++
for (x in 0..9) {
for (y in 0..9) {
val ds = Array(10) {Array(10) {INF + 7}}
for (v in 0..9) {
for (cx in 0..9) {
for (cy in 0..9) {
if (cx + cy == 0)
continue
val to = (v + cx * x + cy * y) % 10
ds[v][to] = minOf(ds[v][to], cx + cy)
}
}
}
var res = 0
for (v in 0..9) {
for (to in 0..9) {
if (ds[v][to] > INF && cf[v][to] > 0) {
res = -1
break
}
res += (ds[v][to] - 1) * cf[v][to]
}
if (res == -1)
break
}
print("$res ")
}
println()
}
}
1202C - You Are Given a WASD-string...
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
const val INF = 1e9.toInt()
fun main(args: Array<String>) {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val s = readLine()!!
val alp = arrayOf("WS", "AD")
val aDir = arrayOf(
s.filter { alp[0].indexOf(it) != -1 },
s.filter { alp[1].indexOf(it) != -1 }
)
val baseW = arrayOf(INF, INF)
val bestW = arrayOf(INF, INF)
for (k in 0..1) {
val pSum = arrayListOf(0)
for (c in aDir[k]) {
val add = if (c == alp[k][0]) +1 else -1
pSum.add(pSum.last() + add)
}
for (tp in 0..1) {
val firstMin = pSum.withIndex().minBy { it.value }!!.index
val lastMax = pSum.withIndex().reversed().maxBy { it.value }!!.index
val curBase = pSum[lastMax] - pSum[firstMin] + 1
var curBest = curBase
if (curBase > 2 && lastMax < firstMin)
--curBest
baseW[k] = minOf(baseW[k], curBase)
bestW[k] = minOf(bestW[k], curBest)
for (i in pSum.indices)
pSum[i] = -pSum[i]
}
}
println("${minOf(baseW[0] * 1L * bestW[1], baseW[1] * 1L * bestW[0] )}")
}
}
1202D - Print a 1337-string...
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for(int tc = 0; tc < t; ++tc){
int n;
cin >> n;
int len = 2;
while(len * (len + 1) / 2 <= n)
++len;
n -= len * (len - 1) / 2;
assert(n >= 0);
assert(n <= 45000);
string s = "133";
while(n > 0){
--n;
s += "7";
}
len -= 2;
while(len > 0){
--len;
s += "3";
}
s += "7";
cout << s << endl;
}
return 0;
}
1202E - You Are Given Some Strings...
Idea: Roms
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9) + 7;
const li INF64 = li(1e18) + 7;
const int N = 500005;
const int A = 27;
const int MAG = 500;
struct node {
node *to[A];
int cnt;
} nodes[N];
int szn = 0;
typedef node* vt;
vt getNode() {
assert(szn < N);
fore(i, 0, A)
nodes[szn].to[i] = NULL;
nodes[szn].cnt = 0;
return &nodes[szn++];
}
void addWord(vt v, const string &s) {
fore(i, 0, sz(s)) {
int c = s[i] - 'a';
if (!v->to[c])
v->to[c] = getNode();
v = v->to[c];
}
v->cnt++;
}
int calcCnt(vt v, const string &s, int pos) {
assert(v->cnt == 0);
int ans = 0;
while(pos < sz(s)) {
int c = s[pos] - 'a';
if (!v->to[c])
break;
v = v->to[c];
ans += v->cnt;
pos++;
}
return ans;
}
vector<int> zf(string s) {
vector<int> z(sz(s), 0);
for (int i = 1, l = 0, r = 0; i < sz(s); ++i) {
if(i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < sz(s) && s[i + z[i]] == s[z[i]])
z[i]++;
if(i + z[i] > r)
l = i, r = i + z[i];
}
return z;
}
string t;
int n;
vector<string> s;
inline bool read() {
if(!(cin >> t))
return false;
cin >> n;
s.resize(n);
fore(i, 0, n)
cin >> s[i];
return true;
}
inline void solve() {
vector<int> cnt[2];
fore(k, 0, 2) {
cnt[k].assign(sz(t) + 1, 0);
szn = 0;
vt root = getNode();
forn(i, n) {
if (sz(s[i]) > MAG) {
auto z = zf(s[i] + t);
fore(j, 0, sz(t))
cnt[k][j] += (z[sz(s[i]) + j] >= sz(s[i]));
} else {
addWord(root, s[i]);
}
}
fore(i, 0, sz(t))
cnt[k][i] += calcCnt(root, t, i);
reverse(all(t));
fore(i, 0, n)
reverse(all(s[i]));
}
li ans = 0;
fore(i, 0, sz(t) + 1)
ans += cnt[0][i] * 1ll * cnt[1][sz(t) - i];
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cerr << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1202F - You Are Given Some Letters...
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int a, b;
scanf("%d%d", &a, &b);
int n = a + b;
int ans = 0;
int l = 1;
while (l <= n){
int g = n / l;
if (a < g || b < g){
l = n / g + 1;
continue;
}
int r = n / g;
int a_low = (a + g) / (g + 1);
int a_high = a / g;
int b_low = (b + g) / (g + 1);
int b_high = b / g;
if (a_low <= a_high && b_low <= b_high)
ans += max(0, min(r, a_high + b_high) - max(l, a_low + b_low) + 1);
l = r + 1;
}
printf("%d\n", ans);
}
U good bro?
I like basketball
In C:
Why do we have to check lastMax and firstMin? Can't we always decrease 1 by inserting any character if the width is more than 2. (same for height)
Nope, check this "DDDAAA". width is 4, but we cannot reduce.
Oh, Thanks!
it's impressive how hard were the problems during the contest, but what simple and elegant solution they have.
hard to find out right idea, but when you have one, it seems easy to write down the code, I think. So these problems are still quite hard for a div.2 contest, my thought also.
Except problem C
How do we use a suffix array for problem E?
Build a suffix array for $$$t$$$. For each string $$$s$$$ the suffixes of $$$t$$$ that have $$$s$$$ as a prefix form a (possibly empty) contiguous subsegment of the suffixes in SA order. So you can binary search for the first and last positions in SA order where $$$s$$$ occurs. Comparing can be done in $$$O(\vert s \vert)$$$ so you get the range in $$$O(\vert s \vert \log \vert t \vert)$$$.
Hello, I am new to suffix arrays can you please explain in more detail?
Problem E.
By building suffix automaton of $$$t$$$ and its reverse, you can simply solve the problem in linear time (suppose that $$$|\Sigma|=26$$$ is a constant). Just run each $$$s_i$$$ (or its reverse) on the suffix automaton and mark the end state, then it exists at all end positions in its subtree. Count the number of strings that exists at each position and then you could get the answer.
Aho-Corasick automaton can do the things as well.
Can you please elaborate more. What do you mean by "then it exists at all end positions in its subtree"
A state which refers to a prefix of the string would create a new end position (equals to its length $$$l$$$), so the number of occurrence at position $$$l$$$ equals to the number of occurrences of its suffixes, which lies on its the path to the root.
I'm a bit confused as to how Aho-Corasick works for this problem. Would you mind explaining that part as well?
Just run $$$t$$$ on the automaton of $$$s_i$$$, for each prefix of $$$t$$$, if you go from the current state through fail transitions, then all the string on the path occurs. This however doesn't works well, but what you need is just precalculating the number of strings on the path of each state.
Ok. Thanks!
Can you use exgcd in B?
I used exgcd to solve
,
where a and b is the x-y in the x-y generator. But I couldn't get it right...
And also, DFS Brute force can even pass? --> 58442948
The equation $$$c$$$ % $$$g$$$$$$c$$$$$$d$$$ $$$(a$$$ $$$,$$$ $$$b)==0$$$ may not be tenable in some cases when you're solving $$$ ax+by=c $$$.
It is actually implemented as $$$ax+by = 10k+(n-m)$$$ for some $$$k$$$.
If no solution was found, the answer shall be $$$-1$$$.
The complexity should be $$$O(nA\log A)$$$, where $$$A = 10$$$
Sorry...I didn't read your comment carefully...
The total complexity of your solution could be $$$ O(A^3logA+A^2|s|) $$$ .
I don't know whether it is right ...
This dfs algorithm will pass,because it controls the deep no more than ten,and each will have two choice so no more than 2^10=1000,and total 10^6,never TLE
in fact bfs can run faster
This problem taught me that:
When you think of a brute-force solution, write it down, maybe it can pass...
I used the following python code to evaluate their efficiency. And I found that, as $$$A$$$ increases, my solution becomes faster than the problem setters'...
Here is the code I used $$$\to$$$ Link to Code
Here is the result I got $$$\to$$$ Link to Result
Did I get it wrong? Please point it out :D
In fact,Whether will get TLE depends on the FOR you have.
for example
is O(n^2)
I cannot get your point. Can you please explain further?
we call an algorithm is O(n^2) if there is one FOR in a FOR
O(n^3) if a for in a for and all in a for
it depends on the condition also i think
There are several questions while you are solving the problem using exgcd.
The formula is $$$ax + by \equiv n - m \mod 10$$$. So actually it is $$$ax + by - 10k = n - m$$$. It means there are 3 variables in the equation: $$$x$$$, $$$y$$$, $$$k$$$. If you really want to use exgcd, you should enumerate one of the variables and solve the other two ones.
For example, you enumerate x, and use exgcd to solve the equation, the solutions to $$$y$$$ and $$$k$$$ maybe are not the minimum $$$x + y$$$ since this problem you need to find the minimum number of digits. And that means, you need to iterate through all possible solutions to the equation. ($$$+ \frac {n - m - ax} {gcd (b, 10)}$$$ if you enumerate x)
In this problem, when $$$n - m = 0$$$, you have to find a solution in which $$$k \ge 1$$$ (this k defined same as above). And that's a little bit difficult.
I tried to solve this problem using exgcd during the contest and I failed too. So at last I used brute force to solve the equation. (During the contest, I had a stupid mistake: Didn't consider about $$$n - m = 0$$$). This is my code: 58471355.
Why my submission for E gets TLE? It should be N sqrt N. Hashing seems like it would be fast too. Is it finally time for me to read that old stanford suffix arrays pdf again? Please help, thanks.
https://codeforces.net/contest/1202/submission/58480361
Maybe hash table failed you this time
qwq, how to make it fast? Or just give up and study some real data structures?
You can try to make different contribution maps for each length — this maps can't be large at the same time.
Thanks! Unfortunately even after trying this + only using one hash instead of two + using a faster hash for the strings that are not t, it still gives TLE. I think it's just not possible to solve the problem with hashing. If anyone has solved it with hashing, I would be very interested in seeing it.
https://codeforces.net/contest/1202/submission/58518083
Was able to get AC using hashing. Used different maps for different lengths. 2854 ms is not good though...
Here's a sqrt hashing solution that fits in under 60% of the time limit: 68428902
The main improvements over your version are to iterate over every distinct length that occurs in $$$S$$$ and find matches of that length within $$$T$$$. When you get a match, you can add the appropriate count to both the start and the end of the substring.
This makes the hashing much more cache-friendly and avoids having to hash each substring twice (your solution hashes each once at the start and once at the end). It also removes the need for the hash table entirely.
Considering that this is still over half the time limit, I think it's fair to say that the time limit on this problem was quite strict for sqrt solutions.
Solved D in a weird kind of way.
Let the String be $$$(1^A3^B7) (1^C3^D7)$$$ where $$$d^P$$$ represents digit $$$d$$$ occurring $$$P$$$ times. Bracket is given for clarity.
Number of subsequence 1337 in this string is:
$$$S = A*{B \choose 2}+C*{D \choose 2}+A*{(B+D) \choose 2}$$$
So, what we need to do is find such $$$A$$$,$$$B$$$, $$$C$$$ and $$$D$$$ such that $$$S$$$ becomes $$$n$$$ and also $$$A+B+C+D+2<=10^5$$$
So, I wrote 3 nested for loops over $$$A$$$,$$$B$$$ and $$$D$$$ to find $$$C$$$. And it turns out it always finds some sets of values (and does it very quickly which I don't know why)
Can somebody write a proof as to why does this work everytime?
First of all, I'll try to proof that there is always a solution with the given structure.
Make $$$D = 2$$$ just to make our life easier (since it will isolate $$$C$$$ and we will be able to factorize $$$A$$$). Our expression will be:
Since $$$C$$$ can take any value that we would need, we can send it to the right part of the equation:
Operating:
Now we ask, how does this help since $$$n$$$ could be a prime? The answer is that $$$C$$$ helps us to adjust the divisibility of $$$n$$$ to make it divisible by some integer $$$x \leq \sqrt{n}$$$ (Remember that among $$$p$$$ consecutive integers there is a multiple of $$$p$$$). So if we make $$$B^{2} + B + 1$$$ the maximum integer such that is $$$\leq \sqrt{n}$$$ (thus $$$\leq \sqrt{10^{9}} \approx 31622$$$) and $$$C$$$ the one we need to make $$$n-C$$$ divisible by $$$B^{2} + B + 1$$$ (thus $$$C \leq B^{2} + B + 1 \leq 31622$$$) then $$$A$$$ will have an integer solution.
The length of the string would be:
Which is a valid answer. The reason why you find such an early answer might be this one, $$$A$$$ iterates at most 31622, $$$B$$$ iterates at most 177 and $$$D$$$ at most 2.
I'm not sure if this is the latest answer you could get (since there might be an earlier answer), but it helps I guess :P
In problem C we can also use data structures to maintain the minimum/maximum value.
It is obvious. You shouldn't mention it!
Can somebody pls explain how floyd warshall algorithm is used to solve B ?
Look at my submission 58631999. For every x-y-counter we need to calculate the shortest path between any pair of digits.
Thanks :)
I have some questions about problem F.
Problem is tagged with
binary search
. What application in possible solution it can have? I can only think of binary searching for borders of each periods segment resulting in $$$O(\sqrt{n} \cdot log(n))$$$ solution. Are there any alternative ideas with binary search?It seems that solutions for problem F operate each letter independently (making the same actions on each and then combining the resulting limitations). It can be proven that we can always construct a string with given minimal period if we have at least two different letters in it (and this is always the case for the problem) as long as the limitations for each letter are fulfilled. So, is there any specific reason to restrict the size of alphabet to $$$2$$$?
My solution, when I proposed the problem was, indeed, to binary search borders for the fixed $$$\frac{n}{k}$$$. But my proof that the suitable periods forms a segment is heavily based of the fact that there are only two letters.
Intuitively, it feels that having a larger alphabet cannot make things worse in such constructive problems (constructing a string with given content and period).
We have a proof that we can always construct a string $$$S$$$ of form $$$(X+Y) \cdot q + X$$$ (in other words period repeated $$$q$$$ times with some prefix of period at the end) which will have minimal period $$$(X+Y)$$$ where $$$X$$$ contains $$$cnt_{(X,a)}$$$ letters $$$a$$$ and $$$cnt_{(X,b)}$$$ letters $$$b$$$ and the same for $$$Y$$$. Violating limitation inequality for letter $$$a$$$ will result in making either $$$cnt_{(X,a)}$$$ or $$$cnt_{(Y,a)}$$$ negative, so it is always possible as long as these coefficient are non-negative and $$$(X+Y)$$$ contains both letters at least once.
Now, consider alphabet $$$\alpha$$$ with $$$|\alpha| > 2$$$ and coefficients $$$cnt_{(X,e)}, cnt_{(Y,e)} \geq 0$$$ for each $$$e \in \alpha$$$. We can just move to alphabet $$$\{a, b\}$$$ by dividing $$$\alpha$$$ into two non-empty sets and mapping first set of letters to $$$a$$$ and second set to $$$b$$$. Get $$$cnt$$$-s for $$$a$$$ and $$$b$$$ by summarizing $$$cnt$$$-s of mapped letters, they will also be non-negative (as a sum of non-negative values). Find some $$$X$$$ and $$$Y$$$ in alphabet $$$\{a, b\}$$$. Then we can move back to $$$\alpha$$$ replacing any $$$cnt_{(X,e)}$$$ letters $$$a$$$ in $$$X$$$ to letter $$$e$$$ for each $$$e$$$ that was mapped to $$$a$$$ (and doing the same for letter $$$b$$$ and for string $$$Y$$$). This wont break the period in $$$S$$$, because the letters from $$$\alpha$$$ that were mapped to different letters will for sure be non-equal after moving back. Some of letters that were mapped to the same letter may become non-equal, but this will not break anything because each $$$S_i$$$ and $$$S_j$$$ that must be equal to match periods both will be equal to either some $$$X_k$$$ or $$$Y_k$$$, and character is always equal to itself.
I'm sure we can find a general proof without reduction to smaller alphabet, but I failed to find it in more or less elegant form without considering dozens of cases.
Intuitively, increasing alphabet makes things more complicated. About mapping: consider the case: $$$2$$$ letters $$$X$$$, $$$1$$$ letter $$$Y$$$ and $$$1$$$ letter $$$Z$$$. Mapping $$$(X) \to A$$$ and $$$(Y, Z) \to B$$$ allows period $$$k = 2$$$ ($$$ABAB$$$), but there is no way to make $$$k = 2$$$ with $$$X$$$, $$$Y$$$, $$$Z$$$.
From the other side, we know that $$$s_i = s_{i \mod k}$$$ so we can split $$$s$$$ in $$$k$$$ chains of equal characters: $$$n \mod k$$$ chains of length $$$\frac{n}{k} + 1$$$ and $$$k - n \mod k$$$ of length $$$\frac{n}{k}$$$. In case of two characters we need to represent only one of integers ($$$a$$$ or $$$b$$$) as $$$cnt_0 \cdot \frac{n}{k} + cnt_1 \cdot (\frac{n}{k} + 1)$$$. But in case of $$$m$$$ characters we must represent $$$m - 1$$$ integers simultaneously and it's much harder.
Clearly, such mapping will not work if we apply it to whole string $$$S$$$ before eshablishing it's structure. But we can firstly say that it consists of $$$(q+1)$$$ strings $$$X$$$ and $$$q$$$ strings $$$Y$$$. And of course we have to check letter limitations for original letters: we have to make sure $$$X$$$ and $$$Y$$$ contain non-negative amount of each letter. In case of $$$cnt = [2, 1, 1]$$$ letters with $$$cnt_i = 1$$$ will not allow distributing letters into two complete periods.
About the second part, from that point of view that definitely seems to be more complicated than for alphabet of size $$$2$$$.
This is an easier way to code problems like this sometimes.
Wow, that's really nice and elegant way to use D&C here. Resulting in $$$O(log(N) \cdot C)$$$, where $$$C$$$ is number of segments.
Thanks for sharing this!
I think it's just $$$O(C)$$$ — similar to building a segment tree.
Yes, similarily to building segment tree amount of splitting nodes will be equal to amount of leaf nodes. And if each segment will be of size $$$1$$$ and we will have $$$N$$$ segments, we will have $$$O(C) = O(N)$$$. But similarily to querying segment tree on a range we split original range into $$$O(log(R))$$$ ranges (where $$$R$$$ is the size of range) that fit into some vertexes of a tree. In our case we will not continue building deeper than such ranges, so we will have $$$O(log(N) \cdot C)$$$ leaf nodes in that tree and
/* solve stuff here */
will be visited this amount of times.That seems to be the analysis for arbitrary set of segments. Probably, there is a specific analysis for that case that gives better complexity.
Yes now I see it is not a clear $$$O(C)$$$, but I added a counter to the function, and the number of states visited is close to $$$4C$$$: http://ideone.com/kloEB0
I'll try to explain what I think is special about these segments: consider the $$$2C$$$ endpoints of the segments, if we build a dynamic segment tree over the range $$$[1, n]$$$ with these points, then the number of nodes won't be less than the number of nodes in our case (because reaching $$$[x, x]$$$ may take longer than reaching $$$[x, y]$$$ where $$$n/x == n/y$$$).
If $$$n$$$ is close to $$$C$$$, then the number of nodes is $$$O(n)$$$ as in the normal segment tree. In our segments, the density of the endpoints is more to the left. I tried for many values of $$$n$$$, at least 85% of the endpoints are in the range $$$[1, 2C]$$$. So it is like you are building a normal segment tree in $$$O(C_{85}+logn)$$$ on 85% of the points, and a dynamic segment tree in $$$O(C_{15}\times logn)$$$ on 15% of them.
So I think we can safely use this method assuming it works in $$$O(C)$$$, at least for the usual limits ($$$0.15\times log10^9 < 5$$$).
IN Problem D:
why I input: 1 4 the model solution prints: 133737
Is there a problem with the model solution?
Sorry,I was wrong!
For problem B, the precalculation table could be further simplified to only require $$$O(A^4)$$$ time and $$$O(A^3)$$$ space, making the final time complexity $$$O(|s| + A^4)$$$
This can be accomplished by indexing the shortest counter distances (as well as the digit-pairs in $$$s$$$) not by the start/end digits $$$a$$$ and $$$b$$$, but by their "lexical distance" $$$(b - a) \mod 10$$$, reducing 2 dimensions to 1.
very clean and easy to understand editorial, thanks. Also interesting problems
why this code for E is TLE ? https://codeforces.net/contest/1202/submission/58561929
In problem F we can also empirically verify that for each range with same $$$g$$$ can have one of following forms:
none of periods is possible
all periods are possible
all periods are possible except for the lowest
all periods are possible except for the highest
all periods are possible except for the lowest and the highest
To check which is the case we only need to check if the lowest is possible, the highest is possible and if none of them is also any in the middle.
In Problem D-1337 String, can someone give me the shortest possible answers for n=5 and n=7. Is it 11111337 and 1111111337 ?
i dont know if they are minimal but they are shorter than your examples:
5: 1337737
7: 1337337
1202B can be done in O(n+A^3). Though this improvement is irrelevant with given bounds, I think it's still worth noting.
Filling u..v and x..y is identical if v-u=y-x (mod A). Hence we only need track how many of each kind difference exist in string (for example, 8..4 and 1..7 both count as difference 6). Edge weight 1 SSSP can be done in simple linear BFS, so the inner loop will only take O(A).
Hi, for problem E I have implement the idea in the editorial (the MAG idea with only basic string structures), my submission is here: 65325941. But I get TLE still. Any ideas what I'm doing wrong here? Thanks.
Problem B is a quite elegant dp Problem.
Honestly, Editorial's method seems tough, so here's my simple Floyd dp solution , where basically we just calculated dp[x][y][i][j] i.e. for each fixed counter (x-y), the min. digits needed to go from digit i to digit j. My solution is just another implementation of this.
You can also solve 1202C using a randomized approach. Randomly insert a random character (either 'W', 'A', 'S', or 'D') and find the best rectangle.
138389957