1796A - Typical Interview Problem

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (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

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (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")
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (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;
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (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';
}
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (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**

Tutorial is loading...

**Solution (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

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

mightpass, 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].

ah I see now it is just iterating over [L,mid] or [mid,R]

https://codeforces.com/contest/1796/submission/195474428

it got accepted now. Thank you!

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.

PROBLEM B : ASTERISK MINOR TEMPLATE VIDEO EDITORIAL SOLUTION LINK : https://youtu.be/BfuaPc6ErQU

HAPPY CODING

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

thank you so much i moved the break to the outer loop and it just got accepted.

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)$$$

Can you explain your approach? Thanks in Advance

I was so close with C but didnt realise that these powerful restrictions on

`di`

take 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

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.

I am sorry .I will use English!!!!!!!

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;`

vs`d=(1L)<<k;`

line), but C11 does have`long long int`

which 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 int`

are 32 bit ints with these 3 compilers and`d=(1L)<<k`

or`d=(1LL)<<k`

doesn't seem to work as well`1LL in GNU C11`

code https://codeforces.com/contest/1796/submission/195732043`1L in GNU C11`

code https://codeforces.com/contest/1796/submission/195570188`1LL in GNU C++17`

code 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);`

.`1`

here is a 32-bit`int`

, 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);`

or`printf("%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 int`

is 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|}}$$$.

Thank you!

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

Can somone pls explain what is wrong with my code for problem B 196139115

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

Thanks

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??

Can anyone let me know where this code is failing it is failing on test case 1661

https://codeforces.com/contest/1796/submission/198624493

PROBLEM B

the way of counting in the editorial of problem C (div2) is amazing, I m not that good at math So I binary searched everything! 201596273

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