Идея: 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 - Самая безбашенная оборона
Идея: vmanosin7, разработка: 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.
Enjoyedd it as always ;)
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.
Thank you for the editorial!
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
Is it rated?
Is it rated?
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?
gets TLE
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
yeah I did it with prefix and suffix and then binary search from both sides
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)
simpler maths https://mirror.codeforces.com/contest/1955/submission/256833759
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
Agreed, I don't know why even simple C problem givign me TLE :-(
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!!
Why I am getting TLE in E? Please help Submission link: 255910548
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
60 10 3
6 60 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
Thanks vstiff, I really appreciate
I think the anti-Dijkstra works, the push into the queue should be outside the if statement, but I get MLE.
256041649
Is there a way to fix it?
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}$$$
thank you a lot *_*
Why O(N) solution of problem D is giving TLE in python? 255903393
i don't know the full reason but somehow storing strings instead of integers in a dict reduces time ( may be something related to hashing inside a default dict ig) same happened to me i tried just changing int to str dtype in lists of a and b it got accepted. your code's modified submission
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)
Hi did you find a solution to this?
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.
I think in the tutorial of problem F the transition should be dp[i][j][k] =max(dp[i−1][j][k],dp[i][j−1][k],dp[i][j][k−1])+x(i,j,k)
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.
Thanks for the suggestion. I will try this out
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)
could please you tell what I can do instead of erase? and also how I can avoid mistakes like these so that I won't make them during the contests
Because you're only erasing the first and last element, a deque is a perfect ds for that, replace erase with pop_front().
BTW your solution is also not working, k is 1e15 so obv it will get TLE
ooh my bad silly mistake
and I did not use deque cause I have not familiarized myself with deques. Thanks I will look into it :> 256015838
it's still not working is my logic wrong? sorry for so many questions
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)=>(1,2)=>(2,2)=>(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
https://mirror.codeforces.com/contest/1955/submission/256034339 can anyone give me test case which my code will give wrong answer
https://mirror.codeforces.com/contest/1955/submission/256034339 can anyone give test case which will fail my code
why vector on E solution??
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>0$$$ => $$$500\times (50\times 50-1)-3^r > 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.
Problem D
My submission 256118405 is getting TLE. Need help.
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
I couldn't solve it in contest, but I have queue implementation for problem E in $$$O(nk)$$$ if anyone want an example. https://mirror.codeforces.com/contest/1955/submission/256137527
Same idea, bruteforce for $$$k = n..1$$$ then simulate the flipping. Idea is to maintain the last k indices in $$$[i-k... i-1]$$$ which need to be flipped. The size of this list is same as how many times $$$bit[i]$$$ will be flipped before it. So we'll push $$$i$$$ to queue whenever $$$(bit[i] + size \,\,of \,\, queue) \,\, \% \,\, 2$$$ is $$$0$$$. If there is nothing need to be flipped at the end (queue is empty), then it means $$$k$$$ is possible.
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.
Millions of people around the world are waiting so kindly stop your personal discussions and focus on others
EMJB with kindness offered help and you keep them waiting? Focus on others now!
Anyone used binary search for E?
Can someone explain me why this submission255752599 is giving WA for TEST-CASE 4 in C
In problem G, why does code with 2d arrays for dp work (256666729) and with 2d vectors (256170691) doesn't?
A simple mathematical O(1) solution of F: 256693662
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
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
in problem b if i make two matrix and compare them is there any prblem with this approach i am getting wrong on 2nd test case 257477711 .
somebody help
i don't understand the solution of Question F
mine look so simple and faster
any explain for editorial solution of Question F ?
C without deque using 2 pointers — https://mirror.codeforces.com/contest/1955/submission/257982926
import java.util.*; import java.lang.*; import java.io.*;
public class Main { public static void main (String[] args) throws java.lang.Exception { // your code goes here Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0){ int n = sc.nextInt(); int m = sc.nextInt(); int x = sc.nextInt(); int[] a = new int[n]; Map<Integer,Integer> b = new HashMap<>(); for(int i=0;i<n;i++){ a[i] = sc.nextInt(); }
for(int i=0;i<m;i++){ int k = sc.nextInt(); b.put(k,b.getOrDefault(k,0)+1); } int i = 0; Map<Integer,Integer> window = new HashMap<>(); int res = 0,c = 0; while(i<m){ int k = a[i]; window.put(k,window.getOrDefault(k,0)+1); if(b.containsKey(k) && window.get(k)>=0 && window.get(k)<=b.get(k)){ c++; } i++; } if(c>=x)res++; while(i<n){ int f = a[i]; int l = a[i-m]; window.put(l,window.getOrDefault(l,0)-1); if(b.containsKey(l) && window.get(l)>=0 && window.get(l)<b.get(l)){ c--; } window.put(f,window.getOrDefault(f,0)+1); if(b.containsKey(f) && window.get(f)>=0 && window.get(f)<=b.get(f)){ c++; } if(c>=x)res++; i++; } System.out.println(res); } }}
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!
https://mirror.codeforces.com/contest/1955/submission/259734054 on test: #2 wrong answer expected NO, found YES [122nd token] What did i do wrong here? can anybody figure it out?
B
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
Thanks for the editorial.
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.
Solved for me as well for the same reason ,Thankyou!
what's wrong in the logic of my code, for https://mirror.codeforces.com/contest/1955/problem/D)? 262306435
I wonder why my O( n log n) solution got TLE in the 'D' problem. Submission: 264661140
In the editorial, it's also written that the O( n log n) solution will work.
Can anyone tell me why it's happening? What's wrong in my code?
FOR F .why its name is unfair game
ll ans=0; vll p(4); forl(i,0,4)cin>>p[i]; ans+=p[3]/2; if(p[0]%2&&p[1]%2&&p[2]%2){ans++;} ans+=p[0]/2; ans+=p[1]/2; ans+=p[2]/2; cout<<ans<<endl;
can someone explain me this part from problem C :-
if (k < 2 * mn) { dq.front() -= k / 2 + k % 2; dq.back() -= k / 2; k = 0; }
In problem H, I think the inequality $$$500\pi.r^2 - 3^r > 0$$$ means that the each tower should have positive contribution, why is this true? Can't some towers make up for others for examples?