Codeforces Round 938 (Div. 3) Editorial

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	jiangly	3631
4	Kevin114514	3574
5	maroonrk	3521
6	strapple	3515
7	Radewoosh	3461
8	tourist	3428
9	turmax	3378
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	140
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

1955A - Yogurt Sale

Tutorial

Solution

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
using namespace std;
 
void solve() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = n * a;
    if (b < 2 * a) {
        ans = (n / 2) * b + (n % 2) * a;
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955B - Progressive Square

Idea: ssor96, mainyutin, prepared: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) (x).begin(), (x).end()
 
using ll = signed long long int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
 
void solve() {
    int n;
    ll c, d;
    cin >> n >> c >> d;
    vl a(n * n);
    for (int i = 0; i < n * n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    vl b(n * n);
    b[0] = a[0];
    for (int i = 1; i < n; ++i) {
        b[i] = b[i - 1] + c;
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            b[i * n + j] = b[(i - 1) * n + j] + d;
        }
    }
    sort(all(b));
    cout << (a == b ? "YEs" : "nO") << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955C - Inhabitant of the Deep Sea

Idea: ssor96, Vladosiya, prepared: mainyutin

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

using ll = signed long long int;

void solve() {
    int n;
    ll k;
    cin >> n >> k;
    deque<ll> dq(n);
    for (int i = 0; i < n; ++i) {
        cin >> dq[i];
    }
    while (dq.size() > 1 && k) {
        ll mn = min(dq.front(), dq.back());
        if (k < 2 * mn) {
            dq.front() -= k / 2 + k % 2;
            dq.back() -= k / 2;
            k = 0;
        } else {
            dq.front() -= mn;
            dq.back() -= mn;
            k -= 2 * mn;
        }
        if (dq.front() == 0) {
            dq.pop_front();
        }
        if (dq.back() == 0) {
            dq.pop_back();
        }
    }
    int ans = n - dq.size();
    cout << ans + (dq.size() && dq.front() <= k) << '\n';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955D - Inaccurate Subsequence Search

Idea: mainyutin, Vladosiya, prepared: mainyutin

Tutorial

Solution

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
void solve() {
    int n, m;
    size_t k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    multiset<int> todo, done, extra;
    for (int j = 0; j < m; ++j) {
        int b;
        cin >> b;
        todo.insert(b);
    }
    for (int j = 0; j < m; ++j) {
        if (todo.find(a[j]) != todo.end()) {
            todo.erase(todo.find(a[j]));
            done.insert(a[j]);
        } else {
            extra.insert(a[j]);
        }
    }
    int ans = (done.size() >= k);
    for (int r = m; r < n; ++r) {
        int old = a[r - m];
        if (extra.find(old) != extra.end()) {
            extra.erase(extra.find(old));
        } else if (done.find(old) != done.end()) {
            done.erase(done.find(old));
            todo.insert(old);
        }
        if (todo.find(a[r]) != todo.end()) {
            todo.erase(todo.find(a[r]));
            done.insert(a[r]);
        } else {
            extra.insert(a[r]);
        }
        ans += (done.size() >= k);
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955E - Long Inversions

Idea: ssor96, prepared: Vladosiya

Tutorial

Solution

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::array<int, 2>;
using pll = std::array<ll, 2>;
using vi = std::vector<int>;
using vl = std::vector<ll>;
 
using namespace std;
 
void solve() {
    int n;
    string s;
    cin >> n >> s;
    for (int k = n; k > 0; --k) {
        vector<char> t(n), end(n + 1);
        for (int i = 0; i < n; ++i) {
            t[i] = s[i] - '0';
        }
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt -= end[i];
            t[i] ^= (cnt & 1);
            if (t[i] == 0) {
                if (i + k <= n) {
                    ++end[i + k];
                    ++cnt;
                    t[i] = 1;
                } else {
                    break;
                }
            }
        }
        if (*min_element(all(t)) == 1) {
            cout << k << '\n';
            return;
        }
    }
    assert(false);
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955F - Unfair Game

Idea: mainyutin, prepared: mainyutin

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 201;
 
int dp[N][N][N];
 
void precalc() {
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                int prev = 0;
                if (i) prev = max(prev, dp[i - 1][j][k]);
                if (j) prev = max(prev, dp[i][j - 1][k]);
                if (k) prev = max(prev, dp[i][j][k - 1]);
                dp[i][j][k] = prev;
                int xr = ((i & 1) * 1) ^ ((j & 1) * 2) ^ ((k & 1) * 3);
                if (xr == 0 && (i || j || k)) {
                    ++dp[i][j][k];
                }
            }
        }
    }
}
 
void solve() {
    vector<int> cnt(4);
    for (int i = 0; i < 4; ++i) {
        cin >> cnt[i];
    }
    cout << dp[cnt[0]][cnt[1]][cnt[2]] + cnt[3] / 2 << '\n';
}
 
int main() {
    precalc();
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955G - GCD on a grid

Idea: ZergTricky, prepared: mainyutin

Tutorial

Solution

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    int ans = 1, g = gcd(a[0][0], a[n - 1][m - 1]);
    vector<vector<char> > dp(n, vector<char>(m));
    for (int x = 1; x * x <= g; ++x) {
        if (g % x > 0) {
            continue;
        }
        vector<int> cand = {x, g / x};
        for (int el : cand) {
            for (int i = 0; i < n; ++i) {
                dp[i].assign(m, 0);
            }
            dp[0][0] = 1;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    if (a[i][j] % el > 0) {
                        continue;
                    }
                    if (!dp[i][j] && i) {
                        dp[i][j] = (dp[i - 1][j] == 1 ? 1 : 0);
                    }
                    if (!dp[i][j] && j) {
                        dp[i][j] = (dp[i][j - 1] == 1 ? 1 : 0);
                    }
                }
            }
            if (dp[n - 1][m - 1]) {
                ans = max(ans, el);
            }
        }
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

1955H - The Most Reckless Defense

Idea: VManoshin, prepared: mainyutin

Tutorial

Solution

#include <bits/stdc++.h>
 
using ll = signed long long int;
 
#define all(x) (x).begin(), (x).end()
 
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
 
using namespace std;
 
const int R = 12, INF = 2e9;
 
bool check(int x, int n) { return (0 <= x && x < n); }
 
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> gr(n);
    for (int i = 0; i < n; ++i) {
        cin >> gr[i];
    }
    vector<pii> cord(k);
    vector<int> p(k);
    for (int i = 0; i < k; ++i) {
        cin >> cord[i].first >> cord[i].second >> p[i];
        --cord[i].first;
        --cord[i].second;
    }
    vector<vector<int> > cover(k, vector<int>(R + 1));
    for (int i = 0; i < k; ++i) {
        int x = cord[i].first;
        int y = cord[i].second;
        for (int r = 1; r <= R; ++r) {
            for (int dx = -r; dx <= r; ++dx) {
                for (int dy = -r; dy <= r; ++dy) {
                    int nx = x + dx;
                    int ny = y + dy;
                    if (!check(nx, n) || !check(ny, m)) {
                        continue;
                    }
                    if ((x - nx) * (x - nx) + (y - ny) * (y - ny) <= r * r) {
                        cover[i][r] += (gr[nx][ny] == '#');
                    }
                }
            }
        }
    }
    vector<vector<int> > dp(k + 1, vector<int>(1 << R, -INF));
    dp[0][0] = 0;
    for (int i = 1; i <= k; ++i) {
        for (int mask = 0; mask < (1 << R); ++mask) {
            dp[i][mask] = dp[i - 1][mask];
            for (int r = 1; r <= R; ++r) {
                int j = r - 1;
                if (!(mask & (1 << j))) {
                    continue;
                }
                dp[i][mask] = max(dp[i][mask], dp[i - 1][mask ^ (1 << j)] +
                                                   p[i - 1] * cover[i - 1][r]);
            }
        }
    }
    int ans = 0;
    for (int mask = 0; mask < (1 << R); ++mask) {
        int hp = 0, mlt = 3;
        for (int j = 0; j < R; ++j) {
            if (mask & (1 << j)) {
                hp += mlt;
            }
            mlt *= 3;
        }
        for (int i = 0; i <= k; ++i) {
            ans = max(ans, dp[i][mask] - hp);
        }
    }
    cout << ans << '\n';
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Comments (125)

Show archived | Write comment?

Naman1213

2 years ago, hide # |

Thanks for the editorial.

→ Reply

Cypher70

← Rev. 2 →

Too dumb to understand H

adaptatron

2 years ago, hide # ^ |

I created video editorial for H: The Most Reckless Defense.

Kairm_Zaf

+10

Hacks in problem G were especially too much in this contest Right?

lvisbl_

Sorry but I'm a newbie here. How it can be hacked? I do not see any using of hashing

Timosh

Newbie? Anyways, hacking is when someone finds a counter-example/test which the code fails to answer correctly, on time or exceeds memory limit. Basically, when someone hacks someone's solution/code which passed all tests with "Accepted", they find a testcase following the constraints, however returns wrong verdict when processed by the "solution".

Proelectro444

Can anyone explain this swap preparation

stefdasca

+26

It often is a good idea to let someone else prepare the problem so that in case mistakes happen in terms of the correctness of the solutions, more people are aware of what is going on.

sahaun

What does preparation mean in this context?

Create strong test data, alternative solutions and checkers/validators. In this contest, one validator was messed up but it was fixed later on.

cheezburger

Can somebody please tell me why my submission for B 255683892 got TLE in system testing?

iLLuSiOnZ

Unordered map's worst case time complexity is $$$O(N^2)$$$ due to collisions. Use ordered map for the same.

Thank you.

croma_79

So should we always use ordered map?

vvent

← Rev. 4 →

A rule of thumb is to avoid using unordered map whenever you can.

Verify if you can avoid the unordered map by using an array/matrix as a table to index the elements directly. If you can't use directly, sometimes you can normalize the values to make it possible. If the problem has multiple test cases, remember to analyze the complexity to clean up the table between the cases.
If you can't use an array by any reason (memory, hard to code, complexity to clean/reuse...), analyze the worst case complexity with ordered map. If it's clearly enough to pass within the time, then use it. The complexity is more predictable and stable. There is no reason to exchange the "not so fast ordered map, but guaranteed AC" by a "MAYBE faster unordered map, but also MAYBE TLE" during the contest.
If you really need/want to use the unordered map, keep in mind that the test cases can blow up the average unordered map solution, getting TLE sometimes. Hopefully, you can try to avoid this by making some changes in the hash function. You can read more about here: Blowing up unordered_map, and how to stop getting hacked on it

EDIT: Changed the order and added some explanations.

chicken911

-11

Just for TLE issue, there are two things you can do to make it run faster:

cin / cout for large amount of data is slow, check here https://mirror.codeforces.com/blog/entry/6251 and use std::ios::sync_with_stdio(false); in your code. You can check samples of other user's submissions to see how they use this to speed up input efficiency.
Don't dynamically allocate arrays in runtime as in int a[n*n], allocate a static array in advance, something like int a[510 * 510] at the beginning.

I don't believe unordered_map is the issue.

Thank you. But it seems like unordered_map was the issue because I submitted the same solution but with a map instead of an unordered_map and it got accepted.

JahonaliX

Thank you for fast editorial

LightWave

Can anyone help me with this ? 255764657 getting TLE.. thanks a lot

relaxed-yalowzt2

the complexity of your solution is O(k) = 1e15，that's no doubt it will be TLE

So what can be done to resolve it?, any cool suggestions.

you can have a look on others' solution: https://mirror.codeforces.com/contest/1955/status，Choose problem C from "Status filter"

popcnt

Has anyone solved the problem G with bfs?

Karim__2

finally got BFS to work

code

ShreyHehe

Why did it work? How did this affect the time complexity?

NekoYellow

For C there’s an easier way to think of it: instead of one Kraken, we have two krakens attacking from both left and right, with the left one dealing $$$ceil(\frac{k}{2})$$$ damage and the right one dealing $$$floor(\frac{k}{2})$$$ damage. We can then simulate their attacks independently and count number of ships sunken afterwards.

Code: my solution

_Light

I did with same approach

Tiny_Snow

+11

Problem F has a simple $$$O(1)$$$ mathematical solution: 255716134.

helpmeimprpve

can u elaborate how u come up with this formula

← Rev. 3 →

It can be simplified to $$$\sum_{i=1}^{4}\lfloor\frac{p_i}{2}\rfloor + (p_1,\ p_2\ and\ p_3\ are\ all\ odd)$$$. You just have to count states that have zero xor sum, which can be expressed as $$$\vec p = (p_1, p_2, p_3, p_4) = (2n_1, 2n_2, 2n_3, 2n_4) + (n_5, n_5, n_5, 0)$$$ where $$$n_i$$$ 's are arbitary integers

Greedy, first consider $$$n_4$$$, the number of $$$(100)_2$$$, $$$n_4$$$ should be even to make xor = 0, after erasing all number expect $$$(100)_2$$$, the last $$$\lfloor n_4 / 2 \rfloor$$$ sequences have 0 xor.

Then consider $$$n_1, n_2, n_3$$$, it is evident that $$$n_1, n_3$$$ and $$$n_2, n_3$$$ should have the same parity to make xor = 0. Then you need to try to achieve that by erasing some numbers as shown in the code.

The optimal solution is: first make $$$n_4$$$ even, then make $$$n_1, n_3$$$ and $$$n_2, n_3$$$ have the same parity, thus one zero-xor is obtained for every two erasing.

AnAndrw

Furthermore, ans=\sum_{i=0}^{4}\left\lfloor\frac{p_i}{2}\right\rfloor+\sum_{i=0}^{3}\left(p_i&1\right) 255945388

tsrigo

I come up with similar formula base on the fact that: 1. The result of two XOR elements is 0 if and only if the two elements are equal; 2. The result of three XOR elements is 0 if and only if they are exactly (1, 2, 3); 3. The result of more than three XOR elements is 0 if and only if it can be divided into the sum of the several pairs and triple above. Finally, add a little greedy thought)

SavageFighter001

Could someone explain why BFS TLEs with same logic for G?

It doesn't, if you avoid creating new visited vector for each divisor. Your accepted code with this change.

it took me 14 submissions to realize that T-T

Thanks!

Whats the problem in making the new vector each time? Its still the same time complexity right?

proc_moe

For problem E, I wonder if there exists some other method to choose&reverse which is better? Or, why always choosing&reversing the first zero from left to right(or right to left) can examine whether a 01-string can be converted to all-1-string. Is there any provements? Thanks a lot.

agarwal_tanishq

yaa same doubt

i though something just now, lets take 110.... for example. so now since leftmost one is part of just 1 segment we cant do any operation on this, come to next 1, so due to previous segment there is no change on this 1 and segment starting from this 1 itself is the last one involving this 1 so cant do any operation again, now next 0, so previous segments have no effect. Segment starting from this element is the last one involving it so we have to do operation, no choice and then so on, we will have to take into consideration the operation applied on this zero for next k-1 elements.

-214748364

F — Greedy Approach 255903652

Hussam_Jdid

What is the rate of problem E could it be below 1400 ?

__Waled

$$$clist$$$ gives an approximate rate around $$$1600$$$

DeadMan69

This contest really was not made for python users, most of the solutions were giving tle for python answers and not for the exact same cpp solution

why is BFS getting TLE for problem G ?

nvm i got it to work

Declaring all variables as static seems to be a solution . Especially visited and the input 2Darray

code : 255917745

Thank you!!

Ankit_singh_sisodya

what is the time complexity of this code?? I am. confused about how many factors will be there in a particular state dp[i][j] ?? 255662591

nguyenquocthao00

In state dp[i][j] there are only factors which is not divisible by any other factor. The number is hard to calculate

mouradnouaili

Hi, I try to use the logic of dijktra algorithm on porblem G. GCD on a grid.

But, I get wrong answer 2136th numbers differ - expected: '8', found: '4'

I can't figure out the bug: 255917561

Please, help

Thanks

if (-gcds[next_row][next_col]>-next_gcd){ gcds[next_row][next_col]=next_gcd; q.push({gcds[next_row][next_col],{next_row,next_col}}); }

--> this line is problem like you are ignoring a possible gcd value which cal help you to have transition

given--> a[i][j] = 6, a[i][j + 1] = 12 but you can do a[i][j] = 10 if you ignore 6 you will get wrong answer

Thanks, for your quick response, I'ppreciate.

for example:

3 2

6 18

6 12

10 12

==> answer is 6. Right?

60 10 3

6 60 6

Try this with your logic... Answer should be 6

vstiff

Try this:

2 5
6 3 6 3 6
2 6 6 6 2

max path

My code output is 2, too.

Okay, so you are doing anti-Dijkstra.

Then this:

1
2 5
1120 14 14 8 3
16 08 28 8 8

prints 2, while there is path with 4

Alaatnt

please give me the reason for the TLE : https://mirror.codeforces.com/contest/1955/submission/255756069

Creating vectors of size $$$10^6$$$ in $$$10^4$$$ test cases.

$$$10^6 * 10^4 = 10^{10}$$$

agjignesh

Why O(N) solution of problem D is giving TLE in python? 255903393

SamuelTull

I dont understand why A* and DFS (with early stopping) give TLE for G. Surely the number of nodes visited is similar to that in the tutorial (effectively doing a search from start to end for each divisor of g)

senak

Can someone explain to me how the third example of question F works? I think the answer is 4.

cosenza

Why do you think the answer is 4? The best case scenario is having the same ones adjacent: 1 1 2 2 3 3

lz123

how to prove the num of divisor of N is N^(1/3)

AkiLotus

Not exactly what the tutorial said, but you can have a look at the function's growth rate.

kirapein1

I don't think so they are trying to say that the number of divisors is N^(1/3), but they are trying to say that the number of divisors is not greater than that. Although for the past 15 mins I was also wondering how is the possible and where is the proof. If someone can explain me in simple terms I would be very thankful.

mgch

+13

There were problems about finding the numbers with maximal number of divisors till N, they solved through the backtracking typo generate p_{1}^q_{1}*p_{2}^q_{2}*...*p_{k}*q_{k}, where p_{i} is the i-th smallest number, and the number of divisors is a product of q_{i}+1

So in generation the most non-trivial thing is to find out that q_{i-1} >= q_{i} because if several numbers with equal number of divisors we are interested in smallest ones, by it you can find that number with maximal number of divisors till 10^9 has 1344 divisors, and till 10^18 has ~1.03e5 divisors, but estimation is clearly rough because 1344 > 1e3

Pangbai

Can the twoer located in the enemie's path in the problem H? If it is posiible, why the solution of dp is right?(just one tower has the range of 0?)

pandearindam

By default, all towers have a zero range, but the player can set a tower's range to an integer r (r>0), in which case the health of all enemies will increase by 3r. However, each r can only be used for at most one tower.

it is mentioned r>0

I know that, but when I use dp, in the final answer, no more than one tower will have the radius of 0. However, when some towers located in the enemy's path, as the promblem says(0 is default), those towers will damage the enemy with zero radius. It seems that the dp can not count this part of damage. Because my dp is weak, I want to konw that whether I misunderstand the problem or the dp can count all zero part in fact.

d1amondzz

Towers are located on empty cells

YuJun1024

Hi guys currently stuck on problem H can't find the problem for this code(wa on test 4). Can anyone help me take a look? Thanks in advance!

Great News guys,got accepted already.

What was wrong:

gargvinayak444

which topic to study for solving this problem

If we're only talking about "TOPICS" then this is a pretty standard bitmask DP problem. However, There's an important observation that the maximum radius of a tower doesn't exceed 12, which LEADS to the method of bitmaskDP.

Vie_SQ

For G, why is the number of divisor the cube root of A

Divisor function growth rate: https://en.wikipedia.org/wiki/Divisor_function#Growth_rate

Problem G can be solved using brute force: store the list of gcds at each element and choose the maximum element at point (m,n) https://mirror.codeforces.com/contest/1955/submission/255975752

AARYABHATTA_THE_GREAT

19 months ago, hide # ^ |

https://mirror.codeforces.com/contest/1955/submission/288436719

I have done the exact same thing! Any idea why my code gives a TLE?

What is it I am missing?

You need to reduce the numbers stored in dp. If there are x and y with x%y==0, then you can only store x, as choosing x to gcd will always be better than choosing y.

raj_naitik

Hey anyone have solved Problem E using Segment Tree??

g00ber

yes but its slow 256050987

Mine Giving TLE i am using Range Update

255980410

Aniyow

256004789

can someone please explain why am I getting time limit exceeding on test 3? in question C. Inhabitant of the Deep Sea and also tell where I went wrong please ;-;

vector erase is O(n)

DopplerXD

very easy code for F 256008944

if both cnt[1] and cnt[2] are odds, just think them as one for cnt[3]

(01 XOR 10 = 11)

Vardanverma96

Can someone explain to me why my code for G, in which I use DP having a complexity of O(m.n.n) is not working. What I am doing is, I stored dp[i][j] as max gcd from (i,j) to (n,m).

For this, I update the dp as follows:

dp[i][j] = max(dp[i][j], gcd("gcd from (i,j) to (k,j)",dp[k][j+1]))

dp[i][j] = max(dp[i][j], gcd("gcd from (i,j) to (k,j)",dp[k+1][j]))

here is the code https://mirror.codeforces.com/contest/1955/submission/256013095

It's my first approach in the problem but found an easy counterexample for it

2 3 
6 2 1
3 6 4

here ,by maximum $$$GCD$$$ logic, it will outputs $$$1$$$.

(Since dp[2][2] = max(dp[1][2] = 2, dp[2][1] = 3) = 3 and dp[2][3] = max(1,1) = 1 )

However, the correct answer here is $$$2$$$ by considering the $$$path$$$

$$$(1,1)= \gt (1,2)= \gt (2,2)= \gt (2,3)$$$

P.S:

The above example is correct in you code, since you start from end

consider the inverted version of the same example

2 3
4 6 3
1 2 6

your code outputs $$$1$$$, but answer is $$$2$$$ by the same $$$path$$$ described above

Ohhh ok got it. Thanks. How do I know if a DP approach won't work in a program like any tips?

Well, make sure the solution checks all the possibilities. It's convenient to try on small cases first and try to validate your solution on them.

When you validate your logic, write the slow solution for transition and try to optimize until it fits the time limit.

Ravenin

Can anyone help me figure out why my solution to C got TLE? Seems O(n) to me.

ksodp

your code is O(k), dont subtract a[i] by 1 at a time, you can subtract it by batch

In question G we don't have to iterate through all divisors of g
We can maintain a list of factors
In each loop:
- Choose a search candidate in the list
- If exists a path, discard all values smaller than the candidate
- If not exists a path, discard all values which is multiplier of the candidate
https://mirror.codeforces.com/contest/1955/submission/256059578

Ashwanth.K

For problem H, isnt that the enemy only visit certain cells in path, but cover() considers all cells in the range of radius R, right ???

I forgot the fact that enemies will pass thorugh all # cells, i wias thinking in direction where enemies only pass through some # cells, and compilcated my problem..

srinivas1999

Thus, the maximum radius for the tower can be found from the inequality $$$500⋅π⋅r^2−3^r \gt 0$$$, assuming that the tower has a damage of pi=500. This estimate gives R=12

Could you explain how come the Maximum radius is just 12?

Inequality should be $$$500\times$$$(# of cells)$$$-3^r \gt 0$$$ => $$$500\times (50\times 50-1)-3^r \gt 0$$$ which gives $$$r=107$$$ right?

500x2500 = 1250000
pow(3,13) = 1594323

ah my bad, calculation error, thanks for the response

Ashar-Usmani

Can anyone tell why recursion is giving TLE for G? Even if I put this condition that dp[i][j]==true and visited[i][j]==true, return true it still gives tle This

pelican103

Can someone help for the line below:

cout << ans + (dq.size() && dq.front() <= k) << '\n';

What does the (dq.size() && dq.front() <= k) do? What value does it add to ans?

not_wiz

It’s for handling the last remaining element in the deque.

Dry run the following test case for better clarity:
5 9
1 2 3 2 1

If we didn’t had that line, answer computed by us would be 4 whereas the actual answer is 5.

dattebayo69

why in the problem G the dp[i][j] = max(__gcd(dp[i][j+1] , curr_num) , __gcd(dp[i+1][j],curr_num))

doesnt work any test case

It seems like you are moving from bottom rightmost cell to top leftmost cell. So your answer would be dp[0][0]

This is a greedy strategy which will fail for the following test case:
2 4 11
2 14 7
3 2 14

it is giving 1 and its the answer too

I’ve edited the test case. Check again

Does there exist any solution to problem G using some modification to dijkstra?

I tried submitting a similar approach to dijkstra but it got TLE (on test case 31) because unlike dijkstra, we can't greedily choose the best path with largest gcd for a given vertex and ignore other bad paths with less gcd for that vertex because those bad paths with less gcd further might become good paths. Here's the submission.

tu_rt_le

Damn, prob G we can check divisor of gcd(a11, anm) and check by dfs O(n * m * sqrt(MaxAij)). Enough to AC

lalit._.007

sorted !! finally read 1st line of editorial and got the idea to solve !

lakshyasinghal006

8 months ago, hide # ^ |

But 2e5*1e3 should not work :'(

lungualex00

I want to share an alternative solution for H, which can be solved nicely with a "by-the-book" MCMF implementation:

The key observation is indeed that there are not that many ranges feasible (at most 12). But the fact that two towers can't use the same range may point out the need for a matching kind of approach.

Further, as some choices bring cost (powers of 3) and some are reducing costs (more tiles being covered), then the problem can be modelled as flow graph with:

one source
K nodes representing the towers (linked to the source, with capacity 1 and no cost)
12 nodes representing the powers of 3 (linked to the towers accordingly, with capacity 1 and the negative cost based on the power of the tower multiplied with the covered tiles using a specific radius)
one special node representing that we don't use a power of 3 (i.e. radius 0, linked to each tower, with capacity 1 and no cost)
a sink node connected to the powers of 3 (with the cost being the power of 3 and capacity 1) and to the special node (with no cost and an arbitrary large capacity)

Apply MCMF (min-cost, max-flow) algorithm and the answer is the cost straight-away.

https://mirror.codeforces.com/contest/1955/submission/257223979

ShelpAm

Can someone elaborate why G has a time complexity of O(n*m*cubic_root(A))? I think it's O(n*m*sqrt(A)).

Number of divisors for any $$$n$$$ are $$$O(n^{1/3})$$$.

You can check here.

Wow! That's amazing! Thanks for telling that!

sangam2ishra

Can anyone tell why the following code for the problem G ~~~~~ Your code here... ~~~~~

1955G - GCD on a grid gives wrong answer 259895161

SNX03

The solution and the idea is wrong, you don't take gcd with dp values you take gcd of path (i.e the values given in the grid). Here you are taking $$$dp[i][j]$$$ = $$$max(dp[i][j], gcd(dp[i-1][j]/dp[i][j-1], a[i][j]))$$$ in this $$$dp[i-1][j]/dp[i][j-1]$$$ is storing max values instead of $$$(a[i-1][j] / a[i][j-1])$$$ you are taking gcd of max value and current value instead of $$$gcd(a[i-1][j]/a[i][j-1], a[i][j])$$$ which is wrong.

Hint for correct solution:

Hint-1

Hint-2

yyw233

D have a little strange

neal27

Hey, can anyone please help me understand why this submission 262094929 got TLE at tc35?

squarer

hey did you understand the reason of TLE , I had same doubt

263251053

Vector initialization takes more time than creating a constant size array, so either create an array everytime. Or create a dp vector once, and then inside the for loop, reset it each time. This had solved the tle for me in my code.

MahmoudBassem

19 months ago, hide # |

In problem H, I think the inequality $$$500\pi.r^2 - 3^r \gt 0$$$ means that the each tower should have positive contribution, why is this true? Can't some towers make up for others for examples?

__swoosh__

17 months ago, hide # |

All the solutions for the problem C that I've seen so far seem to be unnecessary difficult.

Kraken has k times to attack. If k is greater than sum of health of all ships, then no ships will left and the answer is n.

In other case, at least one ship will left. Front and back attacks alternate, so if k is even, Kraken can cause a k / 2 damage to both sides. And if k is odd, then make + 1 damage to the front, because Kraken starts attacking from the front. So we have ceil(k / 2) for the front and floor(k / 2) for the back.

Then just iterate from the front and from the back until Kraken can destroy a ship.

huo_hua_ya

15 months ago, hide # |

verma2004

11 months ago, hide # |

In Problem 1955D - Inaccurate Subsequence Search, why to remove element from Extra in the final loop from m to n, if Extra contains useless elements, so just keep it there. Don't check if old is present in Extra, simply check it for its presence in Done.

Baby_Bird

6 months ago, hide # |

I solved H with the Hungarian algorithm but it took me a year and a half lol, but the complexity achieved is $$$O(R^3k)$$$.

Submission: https://mirror.codeforces.com/contest/1955/submission/349977128

mainyutin's blog