1796A - Typical Interview Problem
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
string fb;
int cur = 1;
while(fb.size() < 100)
{
if(cur % 3 == 0) fb += "F";
if(cur % 5 == 0) fb += "B";
cur++;
}
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int k;
cin >> k;
string s;
cin >> s;
cout << (fb.find(s) != string::npos ? "YES" : "NO") << endl;
}
}
1796B - Asterisk-Minor Template
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
a = input()
b = input()
if a[0] == b[0]:
print("YES")
print(a[0] + "*")
continue
if a[-1] == b[-1]:
print("YES")
print("*" + a[-1])
continue
for i in range(len(b) - 1):
if (b[i] + b[i + 1]) in a:
print("YES")
print("*" + b[i] + b[i + 1] + "*")
break
else:
print("NO")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int l, r;
cin >> l >> r;
int max_size = 1;
while((l << max_size) <= r)
max_size++;
int ans2 = (r / (1 << (max_size - 1)) - l + 1);
if(max_size > 1)
ans2 += (max_size - 1) * max(0, (r / (1 << (max_size - 2)) / 3 - l + 1));
cout << max_size << " " << ans2 << endl;
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const int N = 222222;
const int K = 22;
const li INF = 1e18;
int n, k, x;
int a[N];
li dp[N][K][3];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--) {
cin >> n >> k >> x;
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int t = 0; t < 3; ++t) {
dp[i][j][t] = -INF;
}
}
}
dp[0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
for (int t = 0; t < 3; ++t) {
if (dp[i][j][t] == -INF) continue;
for (int jj = j; jj <= min(k, j + 1); ++jj) {
li add = a[i] + (j == jj ? -x : x);
for (int tt = t; tt < 3; ++tt) {
dp[i + 1][jj][tt] = max(dp[i + 1][jj][tt], dp[i][j][t] + (tt == 1 ? add : 0));
}
}
}
}
}
cout << max(dp[n][k][1], dp[n][k][2]) << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
vector<vector<int>> g;
vector<multiset<int>> len;
multiset<int> all;
int getlen(int v){
return len[v].empty() ? 1 : *len[v].begin() + 1;
}
void init(int v, int p = -1){
for (int u : g[v]) if (u != p){
init(u, v);
len[v].insert(getlen(u));
}
if (int(len[v].size()) > 1){
all.insert(*(++len[v].begin()));
}
}
int ans;
void dfs(int v, int p = -1){
ans = max(ans, min(*len[v].begin() + 1, *all.begin()));
for (int u : g[v]) if (u != p){
if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
len[v].erase(len[v].find(getlen(u)));
if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
len[u].insert(getlen(v));
if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
dfs(u, v);
if (int(len[u].size()) > 1) all.erase(all.find(*(++len[u].begin())));
len[u].erase(len[u].find(getlen(v)));
if (int(len[u].size()) > 1) all.insert(*(++len[u].begin()));
if (int(len[v].size()) > 1) all.erase(all.find(*(++len[v].begin())));
len[v].insert(getlen(u));
if (int(len[v].size()) > 1) all.insert(*(++len[v].begin()));
}
}
int main(){
int t;
scanf("%d", &t);
while (t--){
int n;
scanf("%d", &n);
g.assign(n, {});
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
len.assign(n, {});
all.clear();
all.insert(n);
init(0);
ans = 0;
dfs(0);
printf("%d\n", ans);
}
}
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
using li = long long;
const int MAXLEN = 5;
vector<int> divs(int x) {
vector<int> res;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
res.push_back(i);
if (i * i != x)
res.push_back(x / i);
}
}
return res;
}
int main() {
int A, B, N;
cin >> A >> B >> N;
vector<int> pw(10);
pw[0] = 1;
for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10;
int PW = pw[MAXLEN];
set<array<int, 3>> used;
vector<int> len(PW);
for (int i = 0; i < PW; ++i)
len[i] = sz(to_string(i));
for (int lenn = 1; lenn <= 9; ++lenn) {
int x = pw[lenn] - 1;
for (int k2 : divs(x)) {
int r = x / k2;
for (int d = 1; d < PW; ++d) {
for (int lenb = len[d]; lenb <= MAXLEN; ++lenb) {
int bg = pw[lenb] - d * li(r) % pw[lenb];
int dd = d / __gcd(d, bg);
int lb = (pw[lenb - 1] + bg - 1) / bg;
int rb = (pw[lenb] - 1) / bg;
for (int g = (lb + dd - 1) / dd * dd; g <= rb; g += dd) {
int b = bg * g;
assert(b % d == 0);
if (b >= B || __gcd(b / d, r) != 1) continue;
int ag = (d * li(r) + bg) / pw[lenb];
li n = b / d * li(k2) * ag;
if (n < N && ag * g < A && __gcd(ag, bg) == 1 && sz(to_string(n)) == lenn)
used.insert({ag * g, b, n});
}
}
}
}
}
int res = 0;
for (auto it : used) {
li a = it[0], b = it[1], n = it[2];
int lenn = sz(to_string(n));
int lenb = sz(to_string(b));
res += a * b * pw[lenn] + n * b == a * n * pw[lenb] + a * b;
}
cout << res << endl;
}
high quality problemset
В Д (мне кажется) более понятная и лёгкая ДП — dp[i][k] — максимальная сумма подотрезка, заканчивающегося в i, если уже увеличили на x в k позициях.
Пересчёт понятный, в k приходим из (k — 1 или k) или отрезок длины 1. обновляем ответ по каждому значению на каждом слое, так как отрезок ответа должен где-то закончится, в этот момент и поймаем его. Главное не забыть, что не все конфигурации i k допустимы и проверять, что не использовал +x на больше позиций, чем прошёл. Или что не осталось использовать на большем количестве, чем осталось элементов.
I have implemented this idea, but because it didn't work, I decided that idea is wrong (there is a flaw in it).
https://codeforces.com/contest/1796/submission/195319788
Описанное вами решение по сути и является решением, описанным в разборе — вы просто исключаете состояние "до/внутри/после" из динамики, что начинает требовать больше микроменеджмента и обработки различных условий и случаев.
У вас есть отдельная проверка на $$$K = 0$$$ (даже если допустить, что у вас не будет отдельной копипасты всего вычисления динамики).
Появляются дополнительные сценарии перехода с условиями, которые легко потерять или перепутать (суждение субъективное, я так вижу описанные вами внутренние переходы динамики)
Ответ надо искать по всем состояниям динамики, не забыв проверить определенные базовые состояния.
Вы даже в описании явно говорите "главное не забыть Х, главное не забыть Y". Согласен, что в авторской динамике тоже можно забыть переход с нулевой длиной взятого отрезка, но это единственная деталь, которая обрабатывается лишь одним дополнительным переходом.
Кому-то может быть и проще так придумать, но лично мое мнение, что описанное авторами решение реализовать верно с первого раза намного проще (да и кода выглядит не сильно больше, чем у вас без учета копипасты).
Я примерно поэтому и добавил (мне кажется). И мне действительно кажется, что динамика "сумма заканчивается ровно здесь" сильно легче интуитивно понимается, чем что-то с 3 флагами и "не зашли, вышли, внутри". Хотя этот метод что-то там ещё прикольное решает конечно.
Can someone check why is it giving TLE on Test Case 3 in C? I used binary search.. https://codeforces.com/contest/1796/submission/195465321
I haven't checked the details of your code, but one common issue with C is that participants don't realize that there is no bound on the total size of $$$r$$$ over all test-cases. So you can theoretically have $$$20000$$$ test-cases that all have $$$r$$$ at or near $$$10^6$$$. With this knowledge, you may able to figure out why your approach TLEs. You're basically restricted to logarithmic time or better, i.e., $$$O(\log r)$$$ time (maybe a highly optimized sublinear polynomial might pass, but idk)
But if you were conscious of this when estimating your time complexity, then the issue is likely something else...
Thanks, my BS was wrongly implemented
What kind of BS you used. Looks like just iterate over [L, R].
It's a different kind of BS that doesn't stand for binary search :P
(yash246 please don't be offended, I just couldn't help but make this joke)
LMAO! Came down to comment the exact same thing.
Can someone tell me what i did wrong with problem B? Im always getting error on test 2 but i cant figure out what is wrong with my code
https://codeforces.com/contest/1796/submission/195477231
you should add a condition if(flag2==false) for outer loop you just added it for inner and if statement only that's why check for this output it will give multiple yes aabaaba babbabb
For problem D, can someone help me see why my top down solution TLEs but the bottom up solution passes? Top down: 195483749 Bottom up: 195485579
'cause you call for dp(n-1, k, i) and dp(n-1, k-1, i) in the function, so there are too much recursion calls ($$$C_{n}^{k}$$$). You can avoid it, if you check, that dparr[n-1][k][i] (and the other one) is not INF, so you don't have to call for this function.
For Problem E
After rooting the tree at vertex 1, I greedily rooted the tree at the leaf of the shortest vertical path. Two iterations were enough to pass the test cases. Maybe someone can give me a counter test? I am not sure of the correctness of this greedy solution. Submission link.
Huh, this might be correct. I did some stress testing and couldn't find a counter test. Can't quite come up with a proof, though.
You:
The guy she tells you not to worry about:
Can anyone please help me understand why my code gives TLE?
https://codeforces.com/contest/1796/submission/195509093
I basically followed the editorial exactly but used memorization instead of bottom-up.
In general, is bottom-up faster, or is my implementation just flawed?
Did you find the answer?
I needed to change the line "else if (cache[i][j][t] != 0)" to "else if (cache[i][j][k] != -1)" and default all values in the array to -1. That way you can precompute the answer to states where the answer is 0, which is much faster.
For D i didn't read that $$$k \le 20$$$ so I ended up with a solution that I think is $$$O(n \log n)$$$ (independent of k) rather than $$$O(k n)$$$
I was so close with C but didnt realise that these powerful restrictions on
ditake place, very coolproblem D can be solved with k<=10^5 in O(nlogn).
check my submission: https://codeforces.com/contest/1796/submission/195344685
it can be solved in O(n).
should be O(d*n)
how it can be done in O(n)?
you can separate cases by the length of the subarray you are going to choose
length<k, you can use some dp
length>=k, you can use O(n) sliding window RMQ with deque.
this is my orz friend(Pacybwoah)'s code as an example: 195337817
What is RMQ?
Range Maximum（Minimum) Queries
Can you explain your segment tree approach ?
assume that x>0. if the segment [l,r] is our final answer after performing some operations, it's obvious that we should increase the value of k distinct positions lying on the segment [l,r]. so it's always optimal if we increase the value of continous positions.
in the case that x<0. we have a new x=-x, new k=n-k
For problem C can someone help me why I got wrong answer ? I thought I was very close to the answer,Submission here:195398117
on question C why there is no mod in solution code but it still gets accepted?
I found it too. I had considered the correct solution, but it didn't require any mod, so I missed the chance to get an AC.
the numbers never go over 998244353
[deleted]
What is the greedy method for D task?
For problem E, I don't think it is necessary to save all the length, just the top three, which is O (n)
Yeah, I mentioned that in the tutorial. You can do that but it is more annoying to code and is not that much faster under the given constraints.
why my solution is giving TLE on test on problem D my submission link :195537978 i used multiset for implementation and used greedy logic.
居然没中文
Please use English. This is Codeforces, not Luogu.
In problem C:
For some reason my code written in C doesn't work but same code submitted as C++ code got accepted
C Code: https://codeforces.com/contest/1796/submission/195570786
C++ Code: https://codeforces.com/contest/1796/submission/195570367
Found out the reason, integer overflow.
GNU C11 doesn't have 64 bit ints and GNU C++20 (64) has.
What do you mean by "GNU C11 doesn't have 64 bit ints"?
I don't know why your code doesn't work in C (the only obvious difference I see is the
d=1<<k;vsd=(1L)<<k;line), but C11 does havelong long intwhich is 64 bit.I should clarify GNU C11 does have 64 bits ints but codeforces one's is only 32 bit same with GNU C++ 14 and GNU C++ 17 and
long long intare 32 bit ints with these 3 compilers andd=(1L)<<kord=(1LL)<<kdoesn't seem to work as well1LL in GNU C11code https://codeforces.com/contest/1796/submission/1957320431L in GNU C11code https://codeforces.com/contest/1796/submission/1955701881LL in GNU C++17code https://codeforces.com/contest/1796/submission/195732012All these codes would work in GNU C++20 (64) so the problem can only be due to 1 of 2 reasons:
scanf() or printf() not handling long long ints properly
complier not supporting 64 bit int and integer overflowing
Yeah, it's the first reason. See 195959191 and 195959158.
The problem is in the line
printf("%lld %lld\n", 1, right+1-left);.1here is a 32-bitint, but it gets passed as 64-bit. I think you even end up reading from unallocated memory (or memory allocated for something else). The fix is either:printf("%lld %lld\n", 1LL, right+1-left);orprintf("%d %lld\n", 1, right+1-left);I can reproduce the erroneous output on my MinGW gcc compiler. Although Code::Blocks outputs the intended output for me (differing from the separately installed MinGW instance, even with the correct/same flags set up).
Neither compiler report a warning for this, but I have found an online compiler that does: https://www.onlinegdb.com/online_c++_compiler You can see it by pasting in your code.
long long intis at least 64-bit on all mentioned compilers, as per the standard.Hey you are correct, I was wrong.
Thanks you for both your replies.
No problem
Binary search solution for E.
https://codeforces.com/contest/1796/submission/195570895
Actually it is not a good idea to use binary search because checking an answer is more difficult than solving it directly with greedy.
For D
I think my solution is O(N) 195675418
Consider the subarray we finally chosed i~j
(let S[i] be the sum of a[1~i])
we can assum x>0 (otherwise we can let k=n-k,x=-x)
$$$j-i>=k$$$: answer is $$$max$$$ { $$$S[j]-S[i]+ k*x -(j-i-k)*x$$$} = $$$max$$$ { $$$ (S[j]-j*x) - (S[i]-i*x)$$$} + $$$2*k*x$$$ }
$$$j-i<k$$$: answer is $$$max$$$ { $$$S[j]-S[i]+ (j-i)*x$$$} = $$$max$$$ {$$$(S[j]+j*x) - (S[i]+i*x)$$$}
both can be easily done in O(N) with a queue
In problem B, I need help with the failed test case. 195438093
String A and B's size need not be same. You mistakenly assumed them of the same length.
can anyone help me understand the solution of problem f?, the "unique solution to the previous module equation" part
It means once you chose d and r, the value of b' is fixed since it is a value between 10^(|b| — 1) and 10^|b|
More accurate: if $$$b' \equiv - d \cdot r \pmod{10^{|b|}}$$$ then all solutions of $$$b'$$$ can be represented as $$$b' = c \cdot 10^{|b|} - d \cdot r$$$ for any integer $$$c$$$. But since $$$1 \le b' < 10^{|b|}$$$ there is only one solution in these bounds: it's when $$$b' = 10^{|b|} - (d \cdot r) \bmod{10^{|b|}}$$$.
Is there a typo in F's solution? "all divisors k1 of (10|n|−1) for a fixed |n|." should it means "all divisors k2" instead?
Also g can't equal to ⌊10^|b|b′⌋ I think, consider the case 10^|b| is divisible by b'
Thanks, fixed
Why does the following greedy solution fail for E: If the tree is a chain then answer is its length. Else, for each degree 1 node find the distance of the closest degree >= 3 node from it and insert {dist, node} into a set. Now pick r to be one of node from the smallest two values of {dist, node}. Thus we erase the smallest two values and insert distance of node1 and node2 into the set as that path is now of same color and the smallest element currently in the set is the ans. Submission link : https://codeforces.com/contest/1796/submission/195404472
Greedy Approach for D in $$$O(nlogn)$$$ independent of $$$k$$$:
Prerequisite: knowing how to solve dynamic subarray sum with $$$O(logn)$$$ updates to the array.Submission link and link to solution
Lets split into two cases, $$$x\ge 0$$$ and $$$x<0$$$
First case: Let's assume a subarray $$$[l,r]$$$ is optimal, the sum of this subarray is always sum of $$$a_l, a_{l+1},...,a_{r-1},a_r$$$ $$$+ min(k, r-l+1) * 2x - (r-l+1)x$$$. This is because assuming no positions are selected in the subarray, we just get the subarray sum with $$$x$$$ subtracted from all indexes, however than we assign the most amount of positions as possible for the subarray, when we do this we have to add $$$2x$$$ to every position selected because we already subtracted $$$x$$$ from all positions. This means the positions of the selected indexes do not matter as long as they are in the subarray. It is always optimal for all $$$k$$$ values to be next to each other because compressing the values always makes sure they are in this subarray assuming that the first index is in the subarray, while not compressing the values can leave out values in the subarray. Since we assume that the first index is in the subarray, we can just brute force all $$$n$$$ first indexes in $$$O(nlogn)$$$ time with the dynamic subarray sum mentioned above.
Second Case: The second case turns into the first case pretty easily. We can just represent $$$k$$$ as $$$n-k$$$ and $$$x$$$ as $$$-x$$$
Link to Code
A formal proof or suggestions are appreciated :D
who is 54Michael top 1 ?
he wrote only 1 round and already top 1
he also only one who solved task F
.
In problem D, Does anyone have greedy solution, if you have Could you explain me?
Link
My clean O(n*k) dp approach for problem D not involving any casework for positive and negative x. Link
Thanks a lot for this.
Hey! can you plz explain this line of your code??
Problem C: What is reason of this joking telling about mod operation? Which is not necessary yet. Isn't it create confusion about second number can be very large? but actually not
Problem C: What's the reason of this modulo joking? It's totally creates confusion about second number can't be very large. But a misleading info
jh
I can't understand how problem solved for all roots in problem E!?
Is this some kind of trick to solve problem based on solving it for one root (because I know something like this exists) or not, am I missing something?
BledDest, awoo?
Anyone?
Can someone explain it?
The Editorial isn't clear. I can't understand!?
I'll continue to comment until someone answer.
I'm still waiting...
Can someone explain it?
nice
Why Awoo and BledDest like casework, Irritating Implementation problems ?