Идея: BledDest
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val c = readLine()!!.groupingBy { it }.eachCount().maxBy { it.value }!!.key
println(c.toString().repeat(n))
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (p, f) = readLine()!!.split(' ').map { it.toInt() }
var (cntS, cntW) = readLine()!!.split(' ').map { it.toInt() }
var (s, w) = readLine()!!.split(' ').map { it.toInt() }
if (s > w) {
s = w.also { w = s }
cntS = cntW.also { cntW = cntS }
}
var ans = 0
for (s1 in 0..minOf((p / s), cntS)) {
val w1 = minOf(cntW, (p - s * s1) / w)
val s2 = minOf(cntS - s1, f / s)
val w2 = minOf(cntW - w1, (f - s * s2) / w)
ans = maxOf(ans, s1 + s2 + w1 + w2)
}
println(ans)
}
}
1400C - Восстановление бинарной строки
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
int t;
string s;
int x;
string f(string s) {
string res = s;
for (int i = 0; i < s.size(); ++i) {
if (i - x >= 0 && s[i - x] == '1' || i + x < s.size() && s[i + x] == '1')
res[i] = '1';
else
res[i] = '0';
}
return res;
}
int main() {
cin >> t;
for (int tc = 0; tc < t; ++tc) {
cin >> s >> x;
int n = s.size();
string ns = string(n, '1');
for (int i = 0; i < n; ++i) {
if (s[i] == '0') {
if (i - x >= 0) ns[i - x] = '0';
if (i + x < n) ns[i + x] = '0';
}
}
if (f(ns) == s) cout << ns << endl;
else cout << -1 << endl;
}
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(' ').map { it.toInt() - 1 }.toIntArray()
val cntLeft = IntArray(n) { 0 }
val cntRight = IntArray(n) { 0 }
var ans = 0L
for (j in a.indices) {
cntRight.fill(0)
for (k in n - 1 downTo j + 1) {
ans += cntLeft[a[k]] * cntRight[a[j]]
cntRight[a[k]]++
}
cntLeft[a[j]]++
}
println(ans)
}
}
1400E - Очистите мультимножество
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = int(5e3) + 9;
int n;
int a[N];
int dp[N][N];
int calc (int pos, int x) {
int &res = dp[pos][x];
if (res != -1) return res;
if (pos == n) return res = 0;
res = 1 + calc(pos + 1, n);
res = min(res, calc(pos + 1, pos) + a[pos]);
if (x != n) {
if (a[x] >= a[pos])
res = min(res, calc(pos + 1, pos));
else {
res = min(res, calc(pos + 1, pos) + a[pos] - a[x]);
res = min(res, 1 + calc(pos + 1, x));
}
}
return res;
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d", a + i);
memset(dp, -1, sizeof(dp));
printf("%d\n", calc(0, n));
return 0;
}
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int AL = 9;
const int N = 5000;
const int INF = 1e9;
string s;
int x;
struct node{
int nxt[AL];
int p;
char pch;
int link;
int go[AL];
bool term;
node(){
memset(nxt, -1, sizeof(nxt));
memset(go, -1, sizeof(go));
link = p = -1;
term = false;
}
int& operator [](int x){
return nxt[x];
}
};
vector<node> trie;
void add_string(string s){
int v = 0;
for (auto it : s){
int c = it - '1';
if (trie[v][c] == -1){
trie.push_back(node());
trie[trie.size() - 1].p = v;
trie[trie.size() - 1].pch = c;
trie[v][c] = trie.size() - 1;
}
v = trie[v][c];
}
trie[v].term = true;
}
int go(int v, int c);
int get_link(int v){
if (trie[v].link == -1){
if (v == 0 || trie[v].p == 0)
trie[v].link = 0;
else
trie[v].link = go(get_link(trie[v].p), trie[v].pch);
}
return trie[v].link;
}
int go(int v, int c) {
if (trie[v].go[c] == -1){
if (trie[v][c] != -1)
trie[v].go[c] = trie[v][c];
else
trie[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
}
return trie[v].go[c];
}
string t;
void brute(int i, int sum){
if (sum == x){
bool ok = true;
for (int l = 0; l < int(t.size()); ++l){
int cur = 0;
for (int r = l; r < int(t.size()); ++r){
cur += (t[r] - '0');
if (x % cur == 0 && cur != x)
ok = false;
}
}
if (ok){
add_string(t);
}
return;
}
for (int j = 1; j <= min(x - sum, 9); ++j){
t += '0' + j;
brute(i + 1, sum + j);
t.pop_back();
}
}
int main() {
cin >> s >> x;
trie.push_back(node());
brute(0, 0);
vector<vector<int>> dp(s.size() + 1, vector<int>(trie.size(), INF));
dp[0][0] = 0;
forn(i, s.size()) forn(j, trie.size()) if (dp[i][j] != INF){
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
int nxt = go(j, s[i] - '1');
if (!trie[nxt].term)
dp[i + 1][nxt] = min(dp[i + 1][nxt], dp[i][j]);
}
printf("%d\n", *min_element(dp[s.size()].begin(), dp[s.size()].end()));
return 0;
}
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
const int MOD = 998244353;
int add(int x, int y)
{
return ((x + y) % MOD + MOD) % MOD;
}
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);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int fact[N];
int rfact[N];
void prepare_fact()
{
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(i, fact[i - 1]);
for(int i = 0; i < N; i++)
rfact[i] = inv(fact[i]);
}
int c(int n, int k)
{
if(n < 0 || n < k || k < 0)
return 0;
return mul(fact[n], mul(rfact[k], rfact[n - k]));
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
vector<int> l(n), r(n), a(m), b(m);
for(int i = 0; i < n; i++)
scanf("%d %d", &l[i], &r[i]);
for(int i = 0; i < m; i++)
scanf("%d %d", &a[i], &b[i]);
vector<int> cnt(n + 2);
for(int i = 0; i < n; i++)
{
cnt[l[i]]++;
cnt[r[i] + 1]--;
}
for(int i = 0; i < n + 1; i++)
cnt[i + 1] += cnt[i];
prepare_fact();
vector<vector<int> > p(2 * m + 1, vector<int>(n + 1));
for(int i = 1; i <= n; i++)
for(int j = 0; j <= 2 * m; j++)
p[j][i] = add(p[j][i - 1], c(cnt[i] - j, i - j));
int ans = 0;
for(int mask = 0; mask < (1 << m); mask++)
{
int sign = 1;
set<int> used;
for(int i = 0; i < m; i++)
if(mask & (1 << i))
{
sign = mul(sign, MOD - 1);
used.insert(a[i] - 1);
used.insert(b[i] - 1);
}
int L = 1, R = n;
for(auto x : used)
{
L = max(L, l[x]);
R = min(R, r[x]);
}
if(R < L) continue;
ans = add(ans, mul(sign, add(p[used.size()][R], -p[used.size()][L - 1])));
}
printf("%d\n", ans);
}
Editorial for E is not visible, can you please fix it.
i found that cf problems are often shorter ... lol
Nice explanations!
How detailed it is, upvoted!
You can see nothing
In the contest page, the tutorial link redirects to neal's blog of Unofficial editorial. Maybe you should add this blog as tutorial, and neal's blog as extra tutorial.
Any similar problems like B for practice ?
Can someone explain what's wrong with my solution for B?
You aren't checking the cases when Follower can't pick enough items because Protagonist didn't leave for him. You are running two loops totally exclusively, but in reality they aren't mutually exclusive, and instead, dependent on each other. x swords picked by protagonist means Follower is only left with s-x and he has to choose from them.
Can someone give a binary search approach to problem B, I am not able to implement it, and not getting the function that can be used to find different numbers satisfying the given condition i.e x*(no_of_swords) + y*(no_of_war axes) <= p(or f), or this can't be implemented? Thanks a lot in advance!!
You mean problem B? LINK
Can you explain this please
you are doing r=mid-1 for first BS l=mid+1 for second BS
Why not together? How did u come up this unique in time of contest??
Basic idea : There are 2 people : me and my follower. I will brute force on the number of $$$swords$$$ that I take, binary search on the number of $$$swords$$$ my follower takes, and there will be some space left for both of us, we will use that to take as many $$$axes$$$ as we can.
Problem with binary search : While doing binary search transition to the left or right is the most important thing. In our code $$$mid$$$ represents the number of $$$swords$$$ my follower is trying to take at this moment. If he can't take that much obviously he will try to take less, hence $$$r = mid-1$$$. If he can, then which direction you go next time? You try to take more swords and do $$$mid = l+1$$$, or do you try to take even lesser swords and do $$$r = mid-1$$$? We don't know. That is why I just decided to do both in separate binary searches.
Doing it in one binary search : Do we try to take more swords or less? Actually we know the answer. If the weight of a sword is greater than the weight of an axe, taking more swords only reduces your chance of getting more items. So a simple greedy will allow you to do it in one binary search. LINK.
It's just in contest I instantly had the idea of doing 2 binary searches so I just sticked with it.
Roms awoo In Problem E, what is the meaning of "closed", "open", "unclosed" operation?
The operations of the first type are applied to some segments. An "unclosed" operation means that we have started a segment corresponding to some operation of the first type earlier, but haven't finished it yet. To "open" an operation is to start a segment, to "close" it is to end a segment.
So what does it mean to "close" some operations of the second type and "open" a new operation of the second type?
i cannnot understand the DP solution to problem E, can somebody help me ?
In case you need other solution than DP.
Consider a range [l,r].
For first type of operations: Consider an index x (l<=x<=r) such that a[x] is minimum in that range. If we apply the first operation a[x] times, then each element would be reduced by a[x]. And a[x] becomes 0. Now we can break this range in two parts [l,x-1] ans [x+1, r] and do the same thing.
This case is handled by itself. Here a[x] will be zero, so operations of first type would also be zero. and then the range would be divided in two.
All of these value become zero after we apply the first operation a[x] times. Then this case would be handled as described above.
For second type of operation: We can delete all elements in this range in no more than r-l+1 operations of second type.
Code : 91083858
Problem E . explain the Tag "DP & sorting"
Now i've get the process by checking out the top div.1 programmer jiangly's solution. It's an implement of The line chart .
At first, assume the second option is banned .
This problem == CF1392C — Omkar and Waterslide.
it indicates that when we go up from the (i-1)th positon to the (i)th position, the new cost =the difference betweem a[i-1] and a[i] ,formally,** a[i]-a[i-1]**. when we go down from the (i-1)th positon to the (i)th position, the new cost =0;
now consider the second option, it means we can change the num in ith position,(the raw a[i]) to any num less than or equal to a[i], the cost=(new_num<a[i]?1:0)
note that though we can change a[i] to any new_num<=a[i], but only the n+1 number {0,a[1],a[2],a[3]...a[n]} is effctive. and we sort_unique them to ** m different numbers.**
denote dp[i][j] as : ** on the ith position of array a[], the cost of the process of 0.1.2....i,** after which we change the number to the jth biggest number(same number not inclusive) in array {a[],0};
dp[n+1][0] is the answer ,(we make a[n+1]=a[0]=0,then the restrict "all num==0" is matched )
and then we implement the dp process. simple implement can be O(n^3)
consider MAX_N==5000;
we Change the form of the raw dp equation, and use suffix minimum , preffix minimum,the O(n^2) solution can be implemented.
reference material https://mirror.codeforces.com/contest/1400/submission/90933891
jly&&EI 99
For the second type of operation, you are considering r-l+1 operations but if there are already elements with zeros what about them. Shouldn't we just count the number of non zero elements and use that instead. Or Maybe that case is handled by recursion?
If there is a 0 in range [l,r], then the range would be divided into two without using any operation. Read the first spoiler.
Why does greedy work?
In problem B, why we should take at first min(s,w)?
just greedy , cheaper means more chance to buy more items
Problem D: Can anyone please tell me what is wrong with my solution? it is not working for this test case:
30
28 30 29 29 30 30 29 30 30 30 30 28 28 28 28 29 29 28 29 29 29 30 29 29 30 28 30 30 28 29 expected : 2618 received output : 41212
fo(i,n+1).... in the loop where youre clearing the rig array...
In problem E answer does not exceed $$$n$$$ because we can use $$$n$$$ operations of the second type so we can consider second parameter up to $$$n$$$.
For people interested, 3b1b-styled visual editorial for D. Zigzags this time with narration and as always, with visual dry-run of a testcase.
after reading editorial i feel D was easy i don't know what i was thinking during contest.
After seeing the MOD value for problem G, I was wondering, where/how FFT should be applied here. :)
I loved this contest, specially the problems D, E and F, learned a lot of thouse!! DP with Aho-Corasick blow up my mind but after understand it was awesome!!
Can you please explain the DP part(see below) of problem F x-prime substring?
Sorry, I didn't understand the autor's solution, I write my own recursive approach that think is easier to understand [http://mirror.codeforces.com/contest/1400/submission/91095834](my solution) PD: Also my Aho-Corasik is another implementation
I hand run your code for the input s = '116285317' and x = 8. I was to able to understand finish and cnt array, but can you please explain the "out" and "link" arrays as they both remain zero for the aforementioned input? I know how Aho-Corasick algorithm works and it would be great if you could relate out and link arrays to equivalent arrays used in the Aho-Corasick link provided would really help me. Can you provide a better input(than mentioned at the top) which can make your solution more clear to me?
Thank you!!!
Sure, these are the values that stores each array of my Aho-Corasik implementation:
As you can see the BFS named buildf() calculate these values, so ALL possible transitions of the automaton are calculated beforehand.
Hope this help you...
Thank you Johnny. I have drawn a trie(see below) for 8 prime set (5,3) (3,5) (8)
Suffix link of every vertex is 0 except vertex 4 with suffix link 1 and vertex 2 with suffix link 3. Please correct me if I am wrong.
When I ran the code for same input s = '116285317' and x = 8, I get :
Fail[4] = 1 which is perfect.
My question is why fail[2] = 0 ? Is it because in original string we have substring '53' and not '35'?
I thought fail[2] should equal 3.
May I know why you have taken MAXN=1e5+5 ?
Again thanks Johnny for your time.
Man I just ran my code and got fail[2] = 3, don't know why you got 0. Anyway my advice is focus in the dp instead of the Aho-Corasik implementation (I've used it many times and it works fine to me, but you can use whatever you like)
PD: The MAXN is just a value large enough, nothing special...
Oh ok. Glad to hear that. It must be a manual error(as I hand run the code) by me. I am so sorry about that.
The dp part looked magical at first but breaking it into smaller steps really helped.
Finally, I got it.
I have learnt a lot from this problem.
I don't know how to thank you.
Happy to help
What language are adedalic's solutions written in?
What language are adedalic's solutions written in?
*****************Why a O(2n) code getting TLE in problm C****************
Can anyone tell me please why this submission 90966915 is showing TLE? It was accepted till final standing and after final standing I've submitted the same code in offline also & which was accepted, see here 91082748. I can't understand whats wrong with me. advance thanks. awoo Roms
91117140
I copy-pasted your submission 91117140 and it ran in $$$1918 ms$$$ and then I submitted it again with some comments and got
TLE on test 7
91117335.Basically your code is slow because of the for loop you make to
ans+='0'
.Instead, using
resize
makes it run on $$$31 ms$$$.You got lucky that your code got accepted at all after the contest. These are minor fluctuations in judging time say ~$$$150ms$$$. Your code is basically slow.
I was unable to identify the bug. thanks for your cooperation. But I've a little bit more to know. If you tell me some more details why
ans = ans + '0'
in the loop makes my code slow? Isn't it happening in O(n) time complexity? antontrygubWhen adding (concatenating) strings (and almost any object) using the + operator, each operand is copied, after which they are summing and the result is copied to ans. So O (ans.size()) for each addition, due to copying. If you use the += operator, then only the right operand will be copied, push_back works the same way, it will work in O (1) on average.
if the edge <= 10 I will solve it...
worst contest ever
Yet another solution for G:
There will be at most $$$2m$$$ nodes with nonzero degree, let's call this set of nodes $$$V'$$$, and let $$$k = |V'|$$$. We'll take this part of the graph and solve it independently from the rest. Namely, for each $$$s \in [1..n]$$$, we'll find the subset $$$V_s \subseteq V'$$$ such that these are exactly the nodes $$$v$$$ for which $$$l_v \leq s \leq r_v$$$. For each such subset, we can use meet-in-the-middle and sum-of-subsets DP to calculate, for each $$$j$$$, the number of ways to choose $$$j$$$ independent nodes from $$$V_s$$$, and then multiply this with the corresponding binomial coefficient $$$\binom{z_s-|V_s|}{s-j}$$$, where $$$z_s$$$ is the number of nodes $$$x$$$ satisfying $$$l_x \leq s \leq r_x$$$ in the whole graph. Fortunately, over all $$$s$$$, there can only be $$$2k$$$ different values of $$$V_s$$$, so we do the second phase only a small number of times. Also the sum-of-subsets DP of the first phase needs to be done only once.
Code
In problem G, how to calculate $$$c_s$$$?
The cnt array serves that purpose in the editorial code.
Thank you very much. But the tutorial didn't mention it. I hope the author can add this to the tutorial.
During solving this round, I understood that problem 1400E - Clear the Multiset is similar to 448C - Painting Fence. It's just rephrasing of the problem statement.
But we should notice that: when the input is: 1 0 the output should be 0,instead of 1 This is why I was hacked when I submit the same code as what I submitted in the 448C.
In Problem F, how about the string 2222222232222222232...(1000 characters long)? Doesn't it have about 1000 19-prime substrings, each with length 9? Their total length would then be about 9000. What is wrong here?
I thought the total length <= $$$5000$$$ remark is discussing the set of all possible distinct $$$x$$$-prime strings, and not the multiset of all $$$x$$$-prime substrings of the input or anything of that sort. But that can't be the case, as it is easily calculated with a small dp that there are $$$2399$$$ distinct strings which are $$$19$$$-prime, and their total length is $$$13739$$$. But the Trie generated from the $$$19$$$-prime strings still only has $$$4853$$$ nodes, because many prefixes are shared among those strings, and it is this number that determines the number of values of $$$y$$$ and the state space of the dp.
You're right. I misunderstood the remark. Thanks for the explanation!
There is a small typo in problem G (the factor of $$$(-1)^{|E|}$$$ is missing from the summation) . Other than that, it is a very nice writeup :)
With exact same approach as C, but using Java is giving me TLE. Anything I have missed to optimise? Any solution? My submission: 91120981
Instead of filling w with -1, fill it with 1. Update it's value only when you need to, i.e. when s[i]=0 and you have to make w[i-x] and w[i+x] 0. I copy/pasted your code and made these changes and it got accepted!
In zigzag the explanation should be
i<j(l>k)
, right?I am not able to understand the DP solution of problem E, can somebody help me ?
In problem E, I have implemented a recursive solution where I compare the second operation ($$$r - l + 1$$$) with applying the first operations — subtracting minimum value of the range which splits the range into possibly multiple ranges with all positive elements and recursing further into those ranges. It passed all tests with 202ms in Java and implementation-wise, it's quite easy. I'm wondering if it's the tests were weak or the solution in practice runs faster. Anyone can reason about the complexity? Here's my solution.
The complexity is correct.Every time you visit the solveForAny function,the segment(l,r) is split into at least two parts.In the end,there are no more than n segments,so the total number of visits is no more than n.So the total complexity is O(n^2).You can refer to the blog,there's a clear explanation in it.
Can someone help me with Question D, its giving me TLE on the 6 test case but i am not able to find where i am going wrong, even though my code almost matches the editorial. my code
With PyPy 3 your solution is fast enough. 91575402
I can't figure out when will the answer be "-1" in C. Can anyone help me out please?