Task A. Idea FairyWinx
The optimal answer has the maximum number of digits, so you only need to use the digits $$$1,2$$$.
Alternate these numbers so that there are no adjacent identical numbers.
Since we want to maximize the number we need, we will first find the longest suitable number. Obviously, it is better to use only the numbers $$$1$$$ and $$$2$$$ for this. Therefore, the answer always looks like $$$2121\ldots$$$ or $$$1212\ldots$$$. The first option is optimal when $$$n$$$ has a remainder of $$$2$$$ or $$$0$$$ modulo $$$3$$$, otherwise the second option is optimal.
Below is an example of a neat implementation.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int type;
if (n % 3 == 1)
type = 1;
else
type = 2;
int sum = 0;
while (sum != n) {
cout << type;
sum += type;
type = 3 - type;
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Задача B. Idea FairyWinx
What is a picture if the answer to the problem is "YES".
Think about a square of size $$$2\times 2$$$.
Note that the answer to the problem is "YES" if and only if the picture is a certain number of disjoint rectangles. Now, in this case, let's look at all squares of size $$$2\times 2$$$, note that there cannot be exactly $$$3$$$ filled cells in each of them.
It is also clear that if there are $$$3$$$ such cells, then there will be two intersecting rectangles. Therefore, you just need to check if there is a $$$2\times 2$$$ square in which there are exactly $$$3$$$ colored cells.
#include <bits/stdc++.h>
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) {
string s;
cin >> s;
for (int j = 0; j < m; ++j) {
a[i][j] = s[j] - '0';
}
}
for (int i = 0; i < n - 1; ++i) {
for (int j = 0; j < m - 1; ++j) {
int sum = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1];
if (sum == 3) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Задача C. Idea FairyWinx
There is always an answer when the upper right cell is painted white.
Imagine that you have only rectangles of size $$$1\times 2$$$.
Paint over the cells from the "end".
According to the condition, if the upper left cell is painted black, then we cannot paint it that way. Otherwise it is possible. Let's colour the cells in the following order: $$$(n,m), (n,m - 1), \ldots, (n, 1), (n - 1, m), \ldots (1, 1)$$$.
Let the cell $$$(i, j)$$$ be colored black, then if $$$j > 1$$$, then just paint the rectangle $$$(i, j - 1)$$$, $$$(i, j)$$$. Otherwise, if $$$j = 1$$$, then we will color the rectangle $$$(i - 1, j)$$$.
After such an operation, no cells that we painted before will be repainted, since they have one coordinate larger than ours, and the cell itself will be painted black.
Thus, we are able to paint the table for a maximum of $$$n\cdot m - 1$$$ operations.
#include <bits/stdc++.h>
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) {
string s;
cin >> s;
for (int j = 0; j < m; ++j)
a[i][j] = s[j] - '0';
}
vector<array<int, 4>> ans;
if (a[0][0] == 1) {
cout << -1<< '\n';
return;
}
for (int j = m - 1; j >= 0; --j) {
for (int i = n - 1; i >= 0; --i) {
if (a[i][j]) {
if (i != 0) {
ans.push_back({i, j + 1, i + 1, j + 1});
} else {
ans.push_back({i + 1, j, i + 1, j + 1});
}
}
}
}
cout << ans.size() << '\n';
for (auto i : ans) {
cout << i[0] << ' ' << i[1] << ' ' << i[2] << ' ' << i[3] << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Задача D. Idea FairyWinx
A number is beautiful only if it is a multiple of $$$d$$$, but not a multiple of $$$d^2$$$
Let's solve a more general problem: count the number of such partitions.
This problem is solved by dynamic programming.
Keep the remaining number in dynamics, as well as the last divisor.
Let's solve a more complex problem: calculate the number of partitions into such multipliers.
This is easily solved by dynamic programming. Let $$$dp_{n, d}$$$ be the number of factorizations, if we have a number left to decompose the number $$$n$$$, and before that we divided by the number $$$d$$$. Let's go through all such beautiful numbers $$$i\geq d$$$ that divide $$$n$$$, then $$$dp_{n /i, i} += dp_{n, d}$$$.
Note that in this case, we took into account each option exactly once, since we count the divisors in the order of their increase.
Let $$$C$$$ be the number of divisors of the number $$$x$$$, and $$$V$$$ be the number of beautiful divisors of the number $$$x$$$. Then it works for $$$O(C\cdot V)$$$ or $$$O(C\cdot V^2\cdot log)$$$ depending on the implementation (since $$$n$$$ is always a divisor of the number $$$x$$$), but it all comes easily, since $$$V$$$ is no more $$$700$$$.
#include <bits/stdc++.h>
using namespace std;
bool good(int i, int d) {
return i % d == 0 && i % (1ll * d * d) != 0;
}
void solve() {
int x, d;
cin >> x >> d;
map<pair<int, int>, int> dp;
dp[{x, 1}] = 1;
int res = 0;
vector<int> del;
for (int i = 1; i * i <= x; ++i) {
if (x % i == 0) {
if (good(i, d))
del.push_back(i);
if (x != i * i && good(x / i, d))
del.push_back(x / i);
}
}
while (dp.size()) {
auto z = *dp.rbegin();
if (z.first.first == 1) {
res += z.second;
}
for (auto i : del) {
if (z.first.first % i == 0 && i >= z.first.second) {
dp[{z.first.first / i, i}] = min(dp[{z.first.first / i, i}] + z.second, 2);
}
}
dp.erase(z.first);
}
if (res == 1)
cout << "NO\n";
else
cout << "YES\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Consider the case
Let $$$x = d^a\cdot b$$$. Where $$$b$$$ is not a multiple of $$$d$$$.
Then consider a few cases:
$$$a = 1$$$. Then $$$a$$$ is a beautiful number, since any number multiple of $$$d^2$$$ can be decomposed into $$$d\cdot(a/d)$$$, each of which is colored, and a number multiple of only $$$d$$$, obviously, cannot be decomposed. So in this case there is exactly one option.
$$$b$$$ is composite, then obviously we can decompose in several ways if $$$a\neq 1$$$.
$$$d$$$ is simple. If $$$b$$$ is prime, then the statement — we have only one option to decompose the number. Since every beautiful multiplier of the form $$$d\cdot k$$$. But since $$$d$$$ is simple, there are no other ways to decompose it, except to add a multiplier from $$$b$$$, and since $$$b$$$ is simple, then all these options will be equal before the permutation.
$$$d$$$ is composite and is not a power of prime. If $$$a\leq 2$$$, then this case is no different from the past, since we still have to get two beautiful multipliers and they will all just be equal to $$$d$$$. Otherwise, let $$$d = p\cdot q$$$, where $$$gcd(p, q) = 1$$$. Then we can make the number $$$p\cdot q^{b - 1}$$$ and $$$p^{b - 1}\cdot q$$$. And also $$$q\cdot p, q\cdot p, \ldots , q\cdot p$$$, in this case we have a different number of divisors, so these options will be different, which means we have several options in this case.
$$$d$$$ is the power of a prime number. Then $$$d = p^k$$$. The statement, if $$$d = p^2$$$, and $$$x =p^7$$$, then it cannot be decomposed in several ways, otherwise, if $$$a > 2$$$ and $$$k >1$$$, then let's look at the partition of $$$p^{2k - 1}, p^{k+1}, p^k, \ldots , p^k$$$, it is clear that if $$$k > 2$$$, then even if $$$b = p$$$, then the multiplier of $$$p^{k+ 2}$$$ will still be beautiful, so it does not differ from the composite $$$d$$$ in last case. Otherwise, if $$$k = 2$$$, then if $$$a = 3$$$ and $$$b = p$$$, then nothing can be added, otherwise we will have the opportunity to choose $$$3$$$ of the multiplier $$$p^k$$$, and somehow decompose the rest (since in this case $$$a > 3$$$, then at least one more multiplier will be) and add $$$b$$$ there. And we can decompose these 3 multipliers into $$$2$$$ or $$$3$$$ multipliers, as written above. Therefore, the only unique case when $$$d$$$ is the degree of a prime is $$$d = p^2, x = p^7$$$.
#include <bits/stdc++.h>
using namespace std;
int prime(int x) {
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0)
return i;
}
return -1;
}
void solve() {
int x, d;
cin >> x >> d;
int cnt = 0;
while (x % d == 0) {
++cnt;
x /= d;
}
if (cnt == 1) {
cout << "NO\n";
return;
}
if (prime(x) != -1) {
cout << "YES\n";
return;
}
if (prime(d) != -1 && d == prime(d) * prime(d)) {
if (x == prime(d) && cnt == 3) {
cout << "NO\n";
return;
}
}
if (cnt > 2 && prime(d) != -1) {
cout << "YES\n";
return;
}
cout << "NO\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
}
Задача E. Idea FairyWinx
After each operation, the maximum number is always increased by a specific number.
Students with a number greater than $$$n$$$ are not interested in us.
Imagine that schoolchildren are not expelled, but at any given time we are just interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.
Understand that every student will move to one particular desk after all the operations.
Write a greedy
After each lesson, the person's number increases from the maximum number by the number of desks where no one goes. Therefore, it is easy to calculate how much time has passed since the very beginning, let it be the number $$$k$$$.
Then let's imagine that schoolchildren are not expelled, but at any given time we are simply interested in a student with a minimum number. Obviously, the answer in this case will not change in any way.
Let $$$to_i$$$ be the desk to which the student will move after $$$k$$$ transfers, who originally sat at $$$i$$$ desk. This is a standard problem that can be solved using binary lifts or not the most pleasant dfs with cycle allocation and the like. (but we do not recommend you to write the latter), we define the set $$$V_i$$$ as the set of all numbers $$$j$$$, where $$$to_j = i$$$.
Let the starting placement of the student be a permutation of $$$b$$$, then we will understand that if someone is transferred to the $$$i$$$ desk after $$$k$$$ operations, then the value in it is the minimum value in $$$V_i$$$. And if no one changes seats for it, then a student with the same number will always sit in it, regardless of the initial seating arrangement. After that, it is not difficult to guess the optimal starting seating of schoolchildren.
Let $$$s$$$ be a lot of schoolchildren for whom we have not yet chosen the desk at which they are sitting. We will iterate over $$$i$$$ from $$$1$$$ to $$$n$$$ in ascending order. Then you need to understand who should sit at the $$$i$$$ desk.
If we know that there is a desk for which $$$min(V_i) = i$$$ must be performed, then we must put a student with the minimum number of $$$V_i$$$ at $$$i$$$, and we can put the remaining people at any desks with a number greater than $$$i$$$, so we will add all the other students to the set $$$s$$$. Otherwise, we just need to take a person from $$$s$$$ with the minimum number and put him in a place under the number $$$i$$$, and then just remove him from the set of $$$s$$$.
#include <bits/stdc++.h>
using namespace std;
const int K = 30;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> cnt(n);
vector<vector<int>> up(n, vector<int> (K));
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
--a;
++cnt[a];
up[i][0] = a;
}
for (int k = 1; k < K; ++k) {
for (int i = 0; i < n; ++i) {
up[i][k] = up[up[i][k - 1]][k - 1];
}
}
vector<int> a(n);
int cnt_bad = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (!cnt[i]) {
++cnt_bad;
}
}
int k = (*max_element(a.begin(), a.end()) - n) / cnt_bad;
vector<vector<int>> add(n);
for (int i = 0; i < n; ++i) {
int v = i, level = k;
for (int j = K - 1; j >= 0; --j) {
if (level >= (1 << j)) {
level -= (1 << j);
v = up[v][j];
}
}
add[a[v] - 1].push_back(i);
}
set<int> now;
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
if (add[i].size()) {
int res = *min_element(add[i].begin(), add[i].end());
for (int j : add[i]) {
if (j != res) {
now.emplace(j);
}
}
ans[res] = i + 1;
} else {
ans[*now.begin()] = i + 1;
now.erase(*now.begin());
}
}
for (int i : ans)
cout << i << ' ';
cout << '\n';
}
Задача F. Idea Igorbunov
Realize that the maximum element is always an "inflection" of the first sequence.
It can be assumed that the "inflection" of the second subsequence will always be to the left of the maximum element (if anything, you can then simply expand the array).
In total, we have $$$3$$$ points in time — both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.
The first and third cases are solved by obvious greed.
For the second one, you can simply write the dynamics.
The inflection of the sequence is the maximum number in the subsequence. Then note that in the first subsequence, the inflection will be the maximum number in our array, let its position in the array be $$$ind$$$.
Then let's say for convenience that the inflection of the second subsequence will be to the right of the maximum element. (then expand the array and run the solution one more time).
In this case, we will have $$$3$$$ states: both subsequences increase, the first decreases, and the second increases, or both subsequences decrease.
Let's solve the first case first:
Let $$$dp1_i$$$ be the minimum possible maximum element in a subsequence that does not contain an $$$i$$$ element. It is considered not difficult. If $$$dp1_{i - 1} < a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, a_{i - 1})$$$, since in this case we can add an $$$i$$$ element to a subsequence that does not contain an element of $$$i - 1$$$. Similarly, if $$$a_{i - 1} < a_{i}$$$, then $$$dp1_{i} = min(dp1_{i}, dp1_{i - 1})$$$.
The third case is considered anologically, but only it needs to be counted from the end. (This array will be $$$dp3$$$)
Now let's deal with the second case:
Let $$$dp2_{i, 0}$$$ be the minimum possible last element in the second subsequence if the $$$i$$$ element belongs to the first subsequence. And $$$dp2_{i, 1}$$$ is the maximum possible last element in the first subsequence if the $$$i$$$ element belongs to the second subsequence. There are several options. If $$$i$$$ and $$$i - 1$$$ lie in the same and different subsequences. And we will count for $$$i\leq ind$$$, since before this section both sub-sequences increase, and this is another calculated case. And then it is not difficult to get the conversion formulas:
- $$$dp2_{ind, 0} = dp1_{ind}$$$, by definition $$$dp2_{ind, 0}$$$
- If $$$a_{i - 1} > a_i$$$, then $$$dp2_{i, 0} = min(dp2_{i, 0}, dp2_{i - 1, 0})$$$.
- If $$$dp2_{i - 1, 1} > a_i$$$, then $$$dp2_{i, 0} = min(dp2_{i, 0}, a_{i - 1})$$$.
- If $$$a_{i - 1} < a_{i}$$$, then $$$dp2_{i, 1} = max(dp2_{i, 1}, dp3_{i - 1, 1})$$$.
- If $$$dp2_{i - 1, 0} < a_i$$$, then $$$dp2_{i, 1} = max(dp2_{i, 1}, a_{i - 1})$$$.
Now let's understand that the element with the number $$$i$$$ can be an inflection of the second subsequence if $$$i > ind$$$, as well as $$$dp2_{i, 1} > dp3_{i}$$$. That is, we can move from the second state to the third.
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 228;
int solve (int n, vector<int> a) {
int ind = max_element(a.begin(), a.end()) - a.begin();
vector<int> dp1(n, inf);
dp1[0] = -1;
for (int i = 1; i <= ind; ++i) {
if (a[i] > dp1[i - 1])
dp1[i] = min(dp1[i], a[i - 1]);
if (a[i] > a[i - 1])
dp1[i] = min(dp1[i], dp1[i - 1]);
}
vector<int> dp2(n, inf);
dp2[n - 1] = -1;
for (int i = n - 2; i >= ind; --i) {
if (a[i] > dp2[i + 1])
dp2[i] = min(dp2[i], a[i + 1]);
if (a[i] > a[i + 1])
dp2[i] = min(dp2[i], dp2[i + 1]);
}
vector<array<int, 2>> dp3(n, {inf, -inf});
dp3[ind][0] = dp1[ind];
int ans = 0;
for (int i = ind + 1; i < n; ++i) {
if (a[i - 1] > a[i])
dp3[i][0] = min(dp3[i][0], dp3[i - 1][0]);
if (dp3[i - 1][1] > a[i])
dp3[i][0] = min(dp3[i][0], a[i - 1]);
if (a[i - 1] < a[i])
dp3[i][1] = max(dp3[i][1], dp3[i - 1][1]);
if (dp3[i - 1][0] < a[i])
dp3[i][1] = max(dp3[i][1], a[i - 1]);
if (dp3[i][1] > dp2[i])
++ans;
}
return ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
int ans = solve(n, a);
reverse(a.begin(), a.end());
cout << ans + solve(n, a) << '\n';
}
Second case in F can be done greedy as well and only slightly less straightforward. We should be looking at two next elements instead of one and if $$$a_{i+1}>a_{i+2}$$$ then we should always add $$$a_{i+1}$$$ to a decreasing subsequence if possible, and vice versa.
That was quick! Nice round! Great Problems!
Problem C, hint 1:
I think you meant the upper left cell
I solved D in a pretty clumsy way without managing to come up with any of the nice math. I'm not sure if it's correct. Can somebody try to explain why it works or if it's wrong?
First you factorize x, then remove the non-multiples of d. These are all the good numbers that are candidates for multiplying to x. Let's let N be the length of these remaining good numbers. N ~ O(sqrt(x))
Now, we want to determine which ones of these are beautiful. After running some examples in my head, it seemed like for each good number g, we can just check to see if g/d is also good. If g/d is good, then g is not beautiful. Otherwise, g is beautiful. We can do this in O(N) or O(N log N) with hashing/sorting.
Now we have our remaining beautiful numbers. We just need to find 2 different ways to multiply to x. I tried locally with some huge numbers and the length of the remaining beautiful numbers is very small (around 15-20 for x=1e9). So i just did backtracking dfs over the numbers and divided until i got to 1.
This passed in a pretty reasonable amount of time. Please let me know if it's wrong.
Here is submission: https://codeforces.me/contest/1647/submission/149324001
.
Why all your submission are skipped
Yeah After cheating. Your all submissions are skipped . And we all know what that means right ??.
In problem D, according to definition, if d=2 then 16 can be a beautiful number because 16 is a good number (multiple of 2) and 16 cannot be represented a product of two good numbers but according to tutorial beautiful number is not divisible by d*d. Where I am wrong?
16=16*1 16=8*2 16=4*4
These are the possible cases, none of them has both the numbers good on right hand side
it can, 16 = 2*8
Ah! Got it, Don't know why I was thinking wrong.
Problem D, can someone prove or explain in more details why we can't factor in two ways if d = p^2 and x = p^7?
If we try to represent $$$x$$$ as the product of three numbers, we end up with the set $$$\{p^2,p^2,p^3\}$$$. If we try to move the extra $$$p$$$ factor, the resulting set is the same.
If we try to represent as $$$x$$$ as the product of two numbers, we end up with the set $$$\{p^3,p^4\}$$$, however $$$p^4 = (p^2)^2$$$, which is not allowed.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
For problem B we can say that the answer is YES if all components of black squares are rectangles. And then we can solve the problem by the hard way and do dfs.
For people who are getting WA on D, this case might be helpful:
Input
1
19208 14
Expected
YES
Thank you!!!
Can anyone explain me the DP tutorial of question D.
Haha. I like the editorial solution of B. I myself spent a lot of time implementing B because I was dumb enough to do the straightforward method of checking if each connected component of 1s formed a rectangle.
Thank you for the quick editorial as well!
Please fix this
In $$$D$$$, a simple way to think about the case where $$$d=p^k$$$, $$$x=d^a\cdot b$$$, and $$$b=p^e\cdot f$$$, such that $$$p$$$ is prime, $$$k\geq 1$$$, $$$a\geq2$$$, $$$0\leq e<k$$$, and $$$f$$$ is not a multiple of $$$p$$$:
The maximum-length valid factorization has $$$a$$$ factors, which can be {$$$d$$$, $$$d$$$, ..., $$$d\cdot b$$$}, let's see if we can obtain a different valid factorization as well:
can problem F be done if the inter-section of the two subsequence need not be the whole array ?
How should one approach problems such as yesterday's D?
A copious amount of casework was required and it is very easy to either overlook or mess up one or more cases.
I can not understand Problem D. Madoka and the Best School in Russia.
How is the test case x=128 and d=4 giving the output 'NO'?
If we factorize 128 then some of the valid results are 8*16 and 32*4. Here all of them are good and 8(first case),4(second case) are both beautiful. I know I am missing something but I can not figure it out.
Both numbers need to be beautiful. 16 and 32 are not.
then what about the final test case "1000 10".How can it can output "YES" since all its beatiful factors are [10,20,40,50,250]?--->(it seems like there are only one set to get 1000(20,50))
you can use >=2 beautiful numbers to get x. So [10,10,10] and [20,50] both work.
Can someone Help me with what is wrong in my solution ?
https://codeforces.me/contest/1647/submission/149384795
I cannot find a case where this will fail. Thanks in advance.
Failing testcase: Ticket 1931
Can anyone tell me why I am getting TLE by using unbounded knapsack approach in problem D?
My submission
Got my mistake.
Anyone looking for dp solution for problem D can check out this — 149391053
Finding beautiful divisors — Let two good numbers be k1*d,k2*d. A number is beautiful iff it cannot be represented as product of two good numbers. This means that beautiful number != k1*k2*d^2. So, a beautiful number cannot be divisible by d^2. Check all divisors of x, if they satisfy x%d == 0 and x%(d^2) != 0 then divisor is beautiful.
Let dp[ i ][ j ] represent no of ways to form product j considering first i beautiful divisors. I used top down unbounded knapsack like approach since we can use any amount of good numbers to reach x. (similar to infinite supply of coins)
dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][j / beautiful [ i ] ];
Using relevant base cases and conditions, required ans = dp[n-1][x]. Since x is uptil 1e9 using conventional 2d array will result in MLE. So I used a map and replaced this memoization condition by map.find({i,j}) != map.end().
I tried a bottom up approach also but got a TLE and almost MLE — 149387702. If anyone has done bottom up please share submission link.
There is a nice a trick to replace the map $$$dp$$$ with a $$$2d$$$ array.
We know that the values that can appear in the second dimension are divisors of $$$x$$$. So, we can have an array $$$to\_id$$$ to map each divisor to an $$$ID$$$, obtain that $$$ID$$$ later in $$$O(1)$$$, and use it as an index in the $$$dp$$$ array's second dimension.
Since for each divisor $$$d$$$ either $$$d\le \sqrt{x}$$$ or $$$\dfrac{x}{d}\le \sqrt{x}$$$, if $$$d\le \sqrt{x}$$$, we can store $$$ID$$$ of $$$d$$$ directly in $$$to\_id[d]$$$, otherwise, we can store the $$$ID$$$ in $$$to\_id[\dfrac{x}{d}+\sqrt{x}]$$$. So, size of $$$to\_id$$$ is at most $$$~2\cdot \sqrt{x}$$$.
Thanks for this trick.Can You please show the implementation of this trick ?
Since my second state of dp is product / beautiful[ i ], how to use to_id map here ?
My submission.
Maybe my English level is low,but what is the meaning of "expand the array" in the editorial of problem F?
In other words,why isn't it called "reverse the array" ?
Sorry to bother you to think about it. :(
Because someone has no better)))
It seems that first and third case in F can be done without dp. Take the first case as example, we can take out all prefix maximal element, then the dp value is the maximul in the rest. 149532612
I think there is a problem with the language in the explanation of problem D solution 2. In the explanation, checking that "a<=2" happens after we check that "d is composite and not a power of prime" (2nd to last paragraph). However, this means that we do not check whether a<=2 for the case "d is the power of a prime" (last paragraph). This means an implementation following this description fails on x=32 d=2 (outputs "YES" when the answer is "NO").
I found the explanation of Solution 1 of Problem D in editorial difficult to read, so I will write down my understanding.
The explanation of $$$dp[n][b]$$$ is as follows.
Take the case $$$(x, d) = (36, 2)$$$ for example. Since there are two ways $$$(2 * 18), (6 * 6)$$$, the answer to this case is "YES".
Since we want to represent $$$x = 36$$$ as a product of several beautiful numbers, let's find all beautiful numbers that is divisor of $$$x = 36$$$. In this case $$$(2, 6, 18)$$$.
Initialize with $$$dp[36][1] = 1$$$. In $$$dp[n][b]$$$ we always need to use one of $$$(2, 6, 18)$$$ to decompose $$$n$$$ once.
Note that transitions such as $$$dp[3][2] += dp[6][6]$$$, where the destination $$$b$$$ value is smaller, are prohibited by the definition of $$$dp$$$ (otherwise it would be overcounting).
As a result, we find two states in which $$$x = 36$$$ is completely decomposed: $$$dp[1][18], dp[1][6]$$$. And we see that they correspond to $$$(2 * 18), (6 * 6)$$$ (as mentioned above).
In other words, the state in which $$$x = 36$$$ is completely decomposed is denoted by $$$dp[1][b]$$$, and the sum of $$$dp[1][b]$$$ is the value we want. We can solve this problem by checking if this sum is greater than or equal to $$$2$$$.
Here is my C++ code (modified to make the editorial code more readable).
157492577
For problem D , I have a different approach of order(T*root(n)) (T is number of testcases.).I took 4 cases.When n=d^1,ans is NO. When n is of form=k*d^2,if divisors of k are greater than 1 then answer is yes else no.When n is of form k*d^m where m>3,Ans is yes if either divisors of k or divisors of d are greater then 2. Last case is n is of form k*d^m.If divisors of k>1,answer is YES.Else if k is prime no.,iterate through divisors of d and check if there exists a divisor such that k*divisor is not equal to d.If it exists then answer is YES else NO. The number of test cases may seem to be many but the coding implementation is simple. Here is a link to my solution : https://codeforces.me/contest/1647/submission/173842574