Idea: myav
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int sq = ceil(sqrt(n));
if (sq * sq == n) {
cout << 0 << ' ' << sq << "\n";
} else {
cout << "-1\n";
}
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
2114B - Not Quite a Palindromic String
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void solve(int tc){
int n, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> cnt(2);
for(char c: s){
cnt[c - '0']++;
}
int mn = max(cnt[0], cnt[1]) - n / 2;
int mx = cnt[0] / 2 + cnt[1] / 2;
if(k >= mn && (k - mn) % 2 == 0 && k <= mx) cout << "YES";
else cout << "NO";
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(int tc){
int n;
cin >> n;
int last = -1, ans = 0;
for(int i = 0; i < n; ++i){
int a;
cin >> a;
if(a - last > 1){
ans++;
last = a;
}
}
cout << ans;
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
struct min_max{
int mx1, mx2, mn1, mn2;
void fix_mx(){
if(mx1 < mx2){
swap(mx1, mx2);
}
}
void fix_mn(){
if(mn1 > mn2){
swap(mn1, mn2);
}
}
min_max(int a, int b){
mx1 = mn1 = a;
mx2 = mn2 = b;
fix_mx();
fix_mn();
}
void add(int x){
mx2 = max(mx2, x);
mn2 = min(mn2, x);
fix_mx();
fix_mn();
}
int get_seg(int x){
pair<int, int> res = {mn1, mx1};
if(x == mn1) res.x = mn2;
if(x == mx1) res.y = mx2;
return res.y - res.x + 1;
}
};
void solve(int tc){
int n;
cin >> n;
vector<pair<int, int>> coord(n);
for(auto &e: coord){
cin >> e.x >> e.y;
}
if(n <= 2){
cout << n;
return;
}
min_max xc(coord[0].x, coord[1].x), yc(coord[0].y, coord[1].y);
for(int i = 2; i < n; ++i){
xc.add(coord[i].x);
yc.add(coord[i].y);
}
int ans = xc.get_seg(-1) * yc.get_seg(-1);
for(int i = 0; i < n; ++i){
int x = xc.get_seg(coord[i].x);
int y = yc.get_seg(coord[i].y);
if(x * y == n - 1){
ans = min(ans, min((x + 1) * y, x * (y + 1)));
}
else{
ans = min(ans, x * y);
}
}
cout << ans;
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
2114E - Kirei Attacks the Estate
Idea: Gornak40
Tutorial
Tutorial is loading...
Solution
from math import inf
from sys import setrecursionlimit
def solve(v, p, mini, maxi):
global res
res[v] = max(arr[v], mini * -1 + arr[v])
mini = min(arr[v], maxi * -1 + arr[v])
for u in gr[v]:
if u == p:
continue
solve(u, v, mini, res[v])
setrecursionlimit(400_000)
t = int(input())
for _ in range(t):
n = int(input())
arr = list(map(int, input().split()))
gr = [[] for _ in range(n)]
for j in range(n - 1):
v, u = map(int, input().split())
gr[v - 1].append(u - 1)
gr[u - 1].append(v - 1)
res = [0] * n
solve(0, -1, 0, 0)
print(*res)
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int get_ans(int x, int k){
if(x == 1) return 0;
vector<int> divs;
for(int i = 1; i * i <= x; i++){
if(x % i == 0){
divs.push_back(i);
divs.push_back(x / i);
}
}
sort(all(divs));
int n = divs.size();
vector<int> dp(n, 100);
dp[0] = 0;
for(int i = 1; i < n; i++){
for(int j = i - 1; j >= 0; j--){
if(divs[i] / divs[j] > k){
break;
}
if(divs[i] % divs[j] == 0) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1] == 100 ? -1 : dp[n - 1];
}
void solve(int tc){
int x, y, k;
cin >> x >> y >> k;
int g = gcd(x, y);
x /= g;
y /= g;
int ax = get_ans(x, k);
int ay = get_ans(y, k);
if(ax == -1 || ay == -1) cout << -1;
else cout << ax + ay;
}
bool multi = true;
signed main() {
int t = 1;
if (multi) cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Idea: myav
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(time(nullptr));
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
int max_op(int a, int b) {
int min_part = a;
while (min_part % 2 == 0 && min_part / 2 != b) {
min_part /= 2;
}
if (min_part % 2 == 1) {
return a / min_part;
}
int true_min = min_part;
while (true_min % 2 == 0) {
true_min /= 2;
}
return 1 + (a - min_part) / true_min;
}
void solve(int tc){
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int &e: a) cin >> e;
vector<int> pre(n, 0);
for (int j = 1; j < n; ++j) {
pre[j] = pre[j - 1] + max_op(a[j - 1], a[j]);
}
vector<int> suf(n, 0);
for (int j = n - 2; j >= 0; --j) {
suf[j] = suf[j + 1] + max_op(a[j + 1], a[j]);
}
for (int i = 0; i < n; i++) {
int res = max_op(a[i], 0) + pre[i] + suf[i];
if (res >= k) {
cout << "YES";
return;
}
}
cout << "NO";
}
bool multi = true;
signed main() {
int t = 1;
if (multi) cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
what are your opinions on this round? I'm asking because I didn't like the problems :(.
I think they were mostly good. A ~ C were standard, D was implementation hell, and E was a nice refresher to finish up. I had part of the idea for F but missed one optimization to solve it.
yes, "D was implementation hell" was the most important to me, it's not hard, but I can't get myself to do it. About E: I don't know graph yet, but I think they shouldn't be on positions like E in div. 3 as we should learn as we improve, not learn advanced stuff as a beginner, but surly I think I should learn graph soon. Therefore I don't like the contest because D was implementation heavy.
Am I the only one who loved question D :( I sorted all the x coordinates and the y coordinates in asc order....then i tried to leave out one point at a time, and find the minimum area of the rectangle bounding the n-1 points...its basically maxX — minX +1 * maxY — minY + 1, with maxX,minX etc can be recovered from the sorted array in constant time, and might need to be the next biggest/smallest element if the excluded point has a matching x coordinate, as say maxX. So overall its nlogn per testcase, which is the sorting time
yes, I knew the solution but it feels so bored to implement.
I used this approach in the contest too. I found it very fun to solve and program this new problem.
I solved it the same way.
There's nothing wrong with putting harder problems towards the end of a contest. Div 3's last few problems should feel fine in a Div 2.
In my case, considering that I spent an hour on D, working through E felt like I was having fun again — and I took only 30 minutes to find the solution because of that.
D is quite simple with multisets.
You can maintain a multiset of all x and y coordinates and simulate removing each position and calculating the min area from there.
also orz utd
it was the same with me used multiset over both x and y coordinates and after that tried removing each pair of coordinate and found the minimum answer in D problem
yes multiset lol
Agreed, I like this round. But D was a nightmare to implement so I didn't solve it. At least A-C were free though.
To solve the problem, you can take 3 steps:
If you iterate through all the monsters, you will get an O(n*n) solution.
But you may find that it's better to move monsters from the borders. There are only 4 boundaries. This means that you need to run this algorithm 4 times. The working time is O(n).
This is slightly longer than using double maxima and minima or structures, but easier to implement.
The sorting of both rows and cols is $$$O(n \log n)$$$
It depends on how we do it, we can use multisets too
After that, we just need maxima, second maxima, minima and second minima for both rows and columns, and iterating them and calculating answers is $$$O(1)$$$.There are a few edge cases we need to take care about
I'm a bit biased because I did well, but I overall enjoyed the round. Problems were nice, though in my opinion E was a bit too easy for its position. Disagree with the replies saying D was impl hell, it wasn't annoying with multisets, though you could also go without it and simply use a sorted array for non-C++ users (though that is a slight bit more complex)
Correct me if I am wrong, but the best alternative for multiset is Counter in Python, I think.
If I'm not mistaken, using Counter runs the risk of a hash-collision attack which can lead to TLE.
You can avoid that by using string keys or tuple keys. those work better than integer keys.
Didn't know that, thanks for the info!
can someone explain me B problem editorial again, am not able to picture the suggested approach?
See first understand, if any binary string is there, swapping any two digits can change the number of palindromic pairs by either 0 or 2. Take few examples and try to wrap your head around this fact. You will understand what they are doing after that.
Couldn't have said it better. I knew that k has to share the same parity as the minimum you can make and the maximum you can make.
There is an easier way to think about this problem.
For a string of length $$$n$$$, there are exactly $$$n/2$$$ pairs (since $$$n$$$ is guaranteed to be even). So, since you want exactly $$$k$$$ identical pairs, you want exactly $$$n/2 - k$$$ non-identical pairs. Each non-identical pair uses one $$$0$$$ and one $$$1$$$. So you need at least $$$n/2 - k$$$ zeroes and ones, and you will pair them with each other. Now, for the remaining zeroes and ones, you want all zeroes paired up with zeroes, and all ones with ones. This can happen if and only if the remaining number of zeroes and ones are even. So just check that as well. Here is my code for reference. Just look at the
solvefunction.I cannot thank you enough for this explanation. I was also thinking for something like this but wasn't able to bring it forward. Thanks to your explanation i have finally solved this problem.
In editorial for problem F, "dp[i]=max(dp[i],dp[j]+1)", shouldn't it be min instead of max, as we desire for the minimum number of operations. Correct me, if I am wrong.
yes, in fact if you look at the code they use min
About problem F:
us
In the Tutorial of F, it should be min(dp[i], dp[j]+1), not max.
D was all about implementation and the editorial code is a bit tough to understand for beginners. So, you can refer the code below.
The main idea here is to find the highest and second highest extremes in all four directions — up, down, right and left. Now, the problem is reduced to removing the extreme most monster in all 4 directions one by one and place inside the rectangle formed by taking second most extreme in that direction and extremes in other 3 directions for eg. rectangle area considering second most right extreme, and up,down,left extreme points.
But here it may be possible that a point is extreme for two adjecent directions, ie. a point on top-right corner is extreme for both right and up directions. So here, the rectangle area is considering the extremes in left and down directions and second most extreme in up and right directions. The two if-elses in AreaC() functions check these 4 corner points.
The Areak() function also takes care of the case where the rectangle is already full ,i.e., the monster removed from one of the extremes cannot be placed inside the proposed smaller rectangle, in this case either the width or the height need to increased by 1 to accomodate the ONE monster that is removed.
Note that each of the variables up, down, right and left are a pair of the highest and second highest extremes in the respective direction.
Feel free to suggest any improvements.
yes this is similar to hat I submitted in Py, and is relatively short: 321482410
Note that the corner case solves itself if you use a set of points and take the min area after removing each
That was good thanks man
:)
Not able to understand F, please help.
I am trying to do it using prime factorisation, but i say comment that for ~20 we can't do bitmask dp, so i'm getting tle with that approach
Seeing that nobody has reposted this idea anywhere...
Including in a comment above which described 4 ways of solving F
I had actually explained my approach here
Do check it out.. Still have queries, then feel free to ask!
You may try BFS
yeah, i wanted to see mathematically how it works, to my surprise a paper-pen few test cases worked wonders.
For problem E, I have no idea why I missed the point that path is towards root during contest, and I solved a delusional version for path starting from each node by rerooting...
I'm actually surprised about how weak problem C's tests were. The fact that some people who use vector.erase() still passes the contest testcases is crazy
G is a cool problem!
Yes. G was nice. Upsolved it after contest without help. Took me around 3 hours, but it was worth it.
In D, correct me if I'm wrong, but it is enough to consider at most 4 monsters, with regard to the relocation. By this I mean, the ones on the extremes in all 4 directions. In the worst scenario, you store at most 4 monsters that you want to move and for each, you brute force normally the min and max coordinates for each axis. No need for a multi-set. For me, way easier to implement.
I tried this and it failed on test case 2. You might have more than one monster on an edge of the bounding box.
My code worked. You must remove the monster with the lowest x, largest x, lowest y and largest y. WLOG, say that you have two monsters with the same largest y. I hold that it does not matter which one you choose to reallocate, as long as neither has the minimum or largest x. If one of them or (both) fall into that category then, by construction, you will reallocate them later.
yeah, i also did same
In question E, it can also solved by the dp relation f(v) = max(av,av−a(v-1)+f(v-2)) where f(v) — the maximum value of the threat of the vertex and v-1 and v-2 represent the parent and grandparent of node v. We can keep track of both parent and grandparent in vector as we do bfs or dfs down from vertex.
what is a^2 in problem F?
$$$a$$$ is equal to the number of divisors of the number that we want to decompose into the minimum number of divisors, each of which does not exceed $$$k$$$ For numbers up to $$$10^9$$$, a is approximately $$$a = \sqrt[3]{x} = \sqrt[3]{10^9} = 1000$$$, respectively, $$$a^2 = 1000 ^ 2 = 10^6$$$
You can quickly find the divisors for a single number by factoring it.
First, we get the factorization of the number in $$$O(\sqrt{i})$$$
Next, we will create an array $$$d = [1]$$$ — these will be all the divisors of our number $$$i$$$.
Let's go through all the prime numbers in the factorization and do the following for each of them: Copy $$$d$$$ to $$$tmp$$$, Then multiply each number from $$$d$$$ by our prime number from the factorization $$$d_i\cdot p_j$$$, where $$$p_j$$$ — is a prime number from the factorization, $$$d_i$$$ — our current divisors. And at the end of each iteration, we will copy our divisors from the previous step, $$$d = d + tmp$$$
thanks for your explain but in the editorial the first approach has complexity of a*sqrt(a) per test case, but he wrote a^2
Problem F with sieve of eratosthenes+dp
Time complexity:$$$O(n\sqrt{n})$$$
Sample code:321647158
Observation:First try to make so simple observation,you can see that if there is a prime number $$$p$$$ exist at $$$x$$$ but not in $$$y$$$ then we need to divide it,similarly for multiply,so first we know is if the $$$p>k$$$ we have not solution,so let us define two number $$$I$$$ and $$$J$$$,$$$I$$$ is the number x need to multiply and $$$J$$$ is the number x need to divide,if we can get $$$I$$$ and $$$J$$$ then the problem of us will reduce to how i use the number not greater than k to construct the $$$I$$$ and $$$J$$$.
I believe most of you already know the trick,for a standard sieve of eratosthenes(short form SIE),we can build an array in $$$O(NloglogN)$$$ to check a number is a prime or not,but additional we can extend the SIE to built an array $$$minprime[i]$$$ denoted the minimum prime factor in number i,so after this you can just simply do a while loop to prime factolization a number in $$$O(logN)$$$,so first prime factorize $$$x$$$ and $$$y$$$ then compare their prime factor from low to high,if they share common prime factor then just calculate it should be multiply or divide,if they don't share the prime factor also do the same thing then you can get $$$I$$$ and $$$J$$$
After this the problem of us is how to construct $$$I$$$ and $$$J$$$ will least factor such that $$$\forall factor \le k$$$,I will introduce a dp solution,we define $$$dp[i]$$$ is the minimum number to construct number i by using factor less equal than k,then the transition is $$$dp[i]=min(dp[i],dp[j]+1),\forall j\mid i\;and\;\frac{i}{j}\le k$$$ why?,the logic here is we observe that if we want to get $$$i$$$ first we need to reach the factor of $$$i$$$ then we multiply a number and reach $$$i$$$,so if $$$j$$$ can completely divide $$$i$$$ and $$$\frac{i}{j}\le k$$$ then obviously the minimum number to reach $$$j$$$ + one step to $$$i$$$,so we can just brute force the dp solution,and the reason it work and won't TLE is for a number $$$num\le 10^{6}$$$ there is at most 240 factor,so $$$240^2$$$ of a dp solution won't TLE.
I'm curious about how "240" is got
Use your computer and write a $$$O(nlogn)$$$ factor count algorithm,remember you are not alone when doing content,your computer is your best teammate
Good idea, thanks!
Problem G with prefix+suffix+bitmask
UPD Thank RHEXAOC for correction,now we got a $$$O(n)$$$ solution
Time complexity:old version:$$$O(nlogn)$$$ new version:$$$O(n)$$$
Sample code:old version:321636482 new version:321845290
Observation:First you need to have some bitmask basic idea,in bitmask perspective if you multiply a number x with 2 then the binary representation of x will left shift 1 position similarly for divide operation it will right shift 1 position.Second least significant bit($$$lsb$$$)denoted the first open bit from right to left in binary representation
let consider a example
$$$10_{10}=0000\;1010_2$$$ when you multiply $$$2$$$ which is $$$10 \cdot 2=20_{10}=0001\;0100_2$$$
$$$10_{10}=0000\;1010_2$$$ and $$$lsb$$$ is 1th bit(0-based count from right)
So how this related to the problem?We can observe if a number $$$x\;and\;2\mid x$$$ then it can be decompose to 2 number of $$$\frac{x}{2}$$$ so similary for $$$\frac{x}{2}$$$ if $$$2 \mid \frac{x}{2}$$$ then we can continue to decompose,so did you observe something?Yes,if we just consider a number x we can calculate the maximum number it can be decompose and we add all of the answer and if answer greater equal than k then it may be $$$YES$$$ otherwise $$$NO$$$,why i am using "may" here?Because we only prove the maximum number of decompose but it that is continous?In otherword if the maximum number of decompose is $$$10$$$ is that possible to decompose like $$$5$$$ times?I can prove to you,yes if $$$k<=max\;times\;of\;decompose$$$ we can construct exactly k times.The second question is how many times for a number $$$x$$$ can be decompose?The answer i already told you,which is depent on the $$$lsb$$$ of $$$x$$$ because if you divide by $$$2$$$ this divide operation is equivalent to right shift the binary representation of x by 1 position,so the maximum times i can right shift will equal to the maximum number of times i can divide $$$2$$$,so assume that the $$$lsb$$$ of $$$x$$$ is $$$i$$$(0-based) then the number of times it can be decompose is $$$2^i$$$.
According to the previous explanation,a number $$$x$$$ with $$$lsb$$$ at $$$i$$$ have $$$2^i$$$ times to decompose,assume that after decompose $$$i$$$ times $$$x$$$ become another number $$$y$$$ with $$$2^i$$$ occurrences,if we only want exatly $$$k$$$ times operation we can just combine $$$k$$$ number of $$$y$$$ with another $$$2^i-k$$$ number of y,then the resulting will left only $$$k$$$ number which mean if initially put these $$$k$$$ number then the resulting operation will be exactly $$$k$$$.
Now we have an another problem is that we can just count the maximum decomposition of all $$$a[i]$$$ and sum together?The answer is not because assume that $$$a[i-1]<a[i]$$$ and $$$\frac{a[i]}{a[i-1]}$$$ is a power of 2 then $$$a[i]$$$ can't really decompose completely,check the example below for more precisely detail.Assume that $$$lsb$$$ of $$$a[i-1]$$$ at $$$j$$$ bit then one of the $$$lsb$$$ of element in decomposition of $$$a[i]$$$ can only reach $$$lsb+1$$$,also check the example below for more detail. In other word we need to substract some extra count
Let us consider a array $$$[1,8]$$$,you can see that assume that if $$$1$$$ appear first then $$$8$$$ can't decompose to $$$1$$$,it only can decompose until $$$2$$$ which is $$$[1,2,2,2,2]$$$ otherwise it will combine to $$$a[i-1]$$$,and you can see for $$$lsb$$$ of $$$1$$$ which is $$$0$$$ and $$$lsb$$$ of $$$2$$$ is $$$0+1=1$$$
In the last,we can observe that always one $$$a[i]$$$ will be construct first,so we can brute the answer,which is assume that $$$a[i]$$$ is the first element been constructed then thre rest element $$$a[1]\dots a[i-1]$$$ and $$$a[i+1] \dots a[n]$$$ will be two disjoint independent part just use $$$prefix\;and\;suffix$$$ to maintain the answer,$$$prefix[i]$$$ denoted the maximum number of decompose start from $$$a[i]$$$ for $$$a[1] \dots a[i]$$$ and $$$suffix[i]$$$ denoted the maximum number of decompose start from $$$a[i]$$$ for $$$a[i] \dots a[n]$$$.
Editorial isn't linked on contest page.
I don't understand this hate for D. It was simple to do in constant time, no? 🤥 it took me 5 minutes to do it. Submission
It's linked on announcement page, why didn't you check it
Exactly D was very obvious to me.
I would say I even suffered with B more than D.
can somebody explain me the problem D? I am not able to understand how we are finding the maximum coordinates
Using a C++ Multiset. code
Isnt that slow? I am finding them like that: 323393359
I solved problem 2114F - Small Operations using simulated annealing, which is certainly not the best way, but it was interesting. My solution 321712725. I create arrays of prime factors to divide and multiply our number by, and then try to greedily divide them into groups with product less than k, starting from the beginning of the array.
Why can't we solve it without simulated annealing, I used the same approch without annealing and got WA on 3
Let's look at an example. x = 1, y = 2^4 * 3^3 ^ 7^2 ( = 21168), k = 28. Then your algorithm will combine the prime factors into the following groups: [7, 3], [7, 3], [3, 2, 2, 2], [2]. It would be better though: [7, 2, 2], [7, 2, 2], [3, 3, 3]
Got it, thanks dude
can't see your solution dude
My Solution
Can anyone please explain the bfs solution of problem F?
Observation: The 2nd operation is just the reverse of the 1st operation.
Another observation: We only need divisors (of $$$x$$$) to reach $$$x$$$ from $$$1$$$.
So, this problem transforms to a shortest path problem with nodes being divisors and edges connecting pairs of divisors $$$(a,b)$$$ with $$$a < b$$$ and $$$ak\geq b$$$. We can solve this problem either by DP or BFS.
For B, parity is the key term.
k has to share the same parity as the minimum pairs that you can make and the maximum as well
hello, can someone please explain to me why in problem B (k-mn)%2==0 is a condition.. i am not able to understand it
First we ensure that
kis not smaller thanmn. Thenk - mnis the distance between the minimum number of good pairs and the target good pairs. Since we can only decrease or increase the number of good pairs by 2, we must ensure that the distance is divisible by 2 so that we can perform an integer number of operations (swaps) to getkgood pairs frommn.how do we prove that the greedy way above of finding the max number of operations for G is correct ? why cant we do it in more operations ?
In problem G, we can calculate $$$x$$$ using
c&-cin $$$O(1)$$$ time, then the algorithm can be finished in $$$O(n)$$$.About Problem F: When the task is to decompose the number a into the minimum number of factors, each not exceeding k, it can be viewed as a variation of the Bin Packing Problem. Each item corresponds to the logarithm of a prime factor of a, and the number of such items equals the exponent of that prime in the factorization. The bin capacity is log(k). We then approach this bin packing problem using a brute-force or dynamic programming style algorithm.
the solution to last question was a bit hurried it could have been explained better with small example thats wwhat i feel i am newbie if there was example in that i would have understood it faster than it took to understand
Problem F, as some people have already mentioned, can be reduced to this problem. However, I did not see any comment explaining a good way to apply this standard technique to the problem F.
The main simplification is the fact that our bits in bitmasks correspond to prime factors of $$$x$$$, and each mask represents multiplication of these prime numbers, which is some factor of $$$x$$$. This way we can get rid of actual bitmasks and bits, and consider only factors and prime factors of $$$x$$$.
Now, the transitions are the pretty much the same as in the linked problem. For each factor of $$$x$$$ we divide it for each prime factor, and update our $$$dp$$$ state for this factor, which is the total number of subsets, and value of the current subset. This gets us $$$O(d(x) * p(x) + sqrt(x))$$$ solution where $$$d(x)$$$ is the number of factors of $$$x$$$, and $$$p(x)$$$ is the number of distinct prime factors of $$$x$$$. Here is my code, but it's pretty messy. Hope this helps.
can anyone help me to find the cause of tle in my code for question F
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // this is code
include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int M=1e6;
vector preCompute() { vector div(M+1,0); for(int i=2;i<=M;i++) { if(div[i]==0) { for(int j=i;j<=M;j+=i) { div[j]=i; } } } return div; }
int main() { int t; cin>>t; vector div=preCompute(); while(t--) { int x,y,k; cin>>x>>y>>k; if(x==y) { cout<<"0\n"; continue; } map<int,int> mx; map<int,int> my; int tx=x; while(tx>1) { mx[div[tx]]++; tx=tx/div[tx]; } int ty=y; while(ty>1) { my[div[ty]]++; ty=ty/div[ty]; }
int ans=0; for(auto it=my.begin();it!=my.end();it++) { int p=it->first; if(div[p]==p && p>k && mx.count(p)==0) { //impossible ans=-1; } } if(ans!=-1) { vector<int> del; for(auto it=mx.begin();it!=mx.end();it++) { int p=it->first; if(my.count(p)==0) { for(int i=0;i<mx[p];i++) del.push_back(p); } } vector<int> add; for(auto it=my.begin();it!=my.end();it++) { int p=it->first; if(my[p]>mx[p]) { for(int i=0;i<my[p]-mx[p];i++) add.push_back(p); } else if(my[p]<mx[p]) { for(int i=0;i<mx[p]-my[p];i++) del.push_back(p); } } sort(del.begin(),del.end()); sort(add.begin(),add.end()); int sz=del.size(); int l=sz-1; int num=1; set<int> temp; while(temp.size()<sz) { while(l>=0) { if(temp.find(l)==temp.end() && num*del[l]<=k) { temp.insert(l); num*=del[l]; } l--; } l=sz-1; num=1; ans++; } sz=add.size(); l=sz-1; num=1; temp.clear(); while(temp.size()<sz) { while(l>=0) { if(temp.find(l)==temp.end() && num*add[l]<=k) { temp.insert(l); num*=add[l]; } l--; } l=sz-1; num=1; ans++; } } cout<<ans<<endl; } return 0;} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
For problem F, why is this solution giving TLE ??
322437145
cuz it run more than 3s
hey, can someone explain why my solution to problem D isn't working?
322578007
I am not able to understand the 7th testcase of Problem F, as it should be 7 as the minimum no. of operation by multiplying [12, 12, 7, 5, 5, 3, 13] to 1, i am not able to find 6 muiltipliers to do so, please help!