Идея: mainyutin, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: ssor96, mainyutin, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#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 - Обитатель морских глубин
Идея: ssor96, Vladosiya, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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 - Неточный поиск подперестановки
Идея: mainyutin, Vladosiya, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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 - Длинное инвертирование
Идея: ssor96, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: mainyutin, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: ZergTricky, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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 - Самая безбашенная оборона
Идея: VManoshin, разработка: mainyutin
Разбор
Tutorial is loading...
Решение
#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();
}
}
Thanks for the editorial.
Too dumb to understand H
I created video editorial for H: The Most Reckless Defense.
Hacks in problem G were especially too much in this contest Right?
Sorry but I'm a newbie here. How it can be hacked? I do not see any using of hashing
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".
Can anyone explain this swap preparation
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.
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.
Can somebody please tell me why my submission for B 255683892 got TLE in system testing?
Unordered map's worst case time complexity is $$$O(N^2)$$$ due to collisions. Use ordered map for the same.
Thank you.
So should we always use ordered map?
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.
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.
Thank you for fast editorial
Can anyone help me with this ? 255764657 getting TLE.. thanks a lot
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"
Has anyone solved the problem G with bfs?
finally got BFS to work
code
Why did it work? How did this affect the time complexity?
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
I did with same approach
Problem F has a simple $$$O(1)$$$ mathematical solution: 255716134.
can u elaborate how u come up with this formula
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.
Furthermore, ans=\sum_{i=0}^{4}\left\lfloor\frac{p_i}{2}\right\rfloor+\sum_{i=0}^{3}\left(p_i&1\right) 255945388
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)
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?
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.
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.
F — Greedy Approach 255903652
What is the rate of problem E could it be below 1400 ?
$$$clist$$$ gives an approximate rate around $$$1600$$$
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!!
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
In state dp[i][j] there are only factors which is not divisible by any other factor. The number is hard to calculate
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:
1
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
Try this:
My code output is 2, too.
Okay, so you are doing anti-Dijkstra.
Then this:
prints 2, while there is path with 4
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}$$$
Why O(N) solution of problem D is giving TLE in python? 255903393
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)
Can someone explain to me how the third example of question F works? I think the answer is 4.
Why do you think the answer is 4? The best case scenario is having the same ones adjacent: 1 1 2 2 3 3
how to prove the num of divisor of N is N^(1/3)
Not exactly what the tutorial said, but you can have a look at the function's growth rate.
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.
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
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?)
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.
Towers are located on empty cells
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.
add dp[i][mask] = max(dp[i][mask], dp[i — 1][mask]); outside the if clause(the one with the isset function), I missed this part of the transition :(
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.
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
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.
Hey anyone have solved Problem E using Segment Tree??
yes but its slow 256050987
Mine Giving TLE i am using Range Update
255980410
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)
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)
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 storeddp[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
here ,by maximum $$$GCD$$$ logic, it will outputs $$$1$$$.
(Since
dp[2][2] = max(dp[1][2] = 2, dp[2][1] = 3) = 3anddp[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
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.
Can anyone help me figure out why my solution to C got TLE? Seems O(n) to me.
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
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..
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
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
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?
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.
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.
Damn, prob G we can check divisor of gcd(a11, anm) and check by dfs O(n * m * sqrt(MaxAij)). Enough to AC
sorted !! finally read 1st line of editorial and got the idea to solve !
xD
But 2e5*1e3 should not work :'(
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:
Apply MCMF (min-cost, max-flow) algorithm and the answer is the cost straight-away.
https://mirror.codeforces.com/contest/1955/submission/257223979
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!
Can anyone tell why the following code for the problem G ~~~~~ Your code here... ~~~~~
1955G - GCD on a grid gives wrong answer 259895161
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:
Notice you will always include $$$a[0][0]$$$ and $$$a[n-1][n-1]$$$ in your final value.
D have a little strange
Hey, can anyone please help me understand why this submission 262094929 got TLE at tc35?
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.
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?
All the solutions for the problem C that I've seen so far seem to be unnecessary difficult.
Kraken has
ktimes to attack. Ifkis greater than sum of health of all ships, then no ships will left and the answer isn.In other case, at least one ship will left. Front and back attacks alternate, so if
kis even, Kraken can cause ak / 2damage to both sides. And if k is odd, then make+ 1damage to the front, because Kraken starts attacking from the front. So we haveceil(k / 2)for the front andfloor(k / 2)for the back.Then just iterate from the front and from the back until Kraken can destroy a ship.
Solution
.
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.
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