### awoo's blog

By awoo, history, 6 months ago, translation,

1814A - Coins

Idea: BledDest

Tutorial
Solution (awoo)

1814B - Long Legs

Idea: BledDest

Tutorial
Solution (awoo)

1814C - Search in Parallel

Idea: BledDest

Tutorial
Solution (BledDest)

1814D - Balancing Weapons

Tutorial

1814E - Chain Chips

Idea: BledDest

Tutorial
Solution (BledDest)

1814F - Communication Towers

Idea: Neon

Tutorial
Solution (Neon)
• +68

 » 6 months ago, # |   0 I know it isn't an "issue", but in problem B the variable names are a,b while here they are n,m
 » 6 months ago, # |   0 In problem B, My thought was ternary search since the values tend to decrease at first and then increase but the problem I faced is that around the middle of the curve, the values don't necessarily keep changing in the same way (X-axis for max K length and Y-axis for cost)As you notice some irregularities, can this be handled using only ternary search or by iterating over a much smaller range of K's?
•  » » 6 months ago, # ^ |   0 I tried a weaker 1-D case (go from 0 to n) there $\sqrt{n}$ seems to be the best leg size. (floor or ceil I don't remember) (somewhat related to the fact that $x + a/x$ minimizes at $x = \sqrt{a}$ and similar is the case with $x-1 + \lceil n/x \rceil$) But ofc the problem is going up a notch to the 2-D case. (new to code-forces and I don't know how to write in laTex etc, pardon me for that).
 » 6 months ago, # |   +18 problem EF video solution for Chinese：BiliBili
•  » » 6 months ago, # ^ |   0 why the rating result are not visible now?
•  » » » 6 months ago, # ^ |   +1 because it's an unrated round
 » 6 months ago, # |   0 Can anyone please elaborate on the solution of Problem D, please?
 » 6 months ago, # |   0 First question can be directly solved using concept of LDE Let g = gcd(2,k) If(n%g == 0) cout<
•  » » 6 months ago, # ^ |   0 Perhaps, but I am not sure. According to this: https://cp-algorithms.com/algebra/linear-diophantine-equation.html#finding-the-number-of-solutions-and-the-solutions-in-a-given-intervalIf you have a solution (for which your check should be okay) you have infinitely many. However, I think we would also have to check if there is such a solution pair where both x and y are non-negative.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 it'll work, we just need to check that c is divisible by gcd(a,b) (for ax+by=c). also if c is really the solution then it would be multiple of gcd(a,b) and since constraints already mentioned that k isn't negative we don't need to care about that cuz we aren't interested in finding out a and b cuz here it's already given a=2 and b=k.
 » 6 months ago, # |   +3 A can be solved by just checking parity of n and k if (n % 2 == 0 || k % 2) yes else no 
•  » » 6 months ago, # ^ |   0 Can you please give an explanation of this? Also, what is meant by parity check?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 parity means it's odd or even.if n is even, it can be made with 2 coins. if n is odd then k must be odd as well otherwise it is not possible. exampleLet's check for specific N and all values of k. let N=7k=2 not possiblek=37= 3*1+2*2k=4 not possiblek=5 7=5*1+2*1k=6 not possiblek=7 7=7*1For a more formal proof prooflet n be written as coins of 2 denominations and k denominations as - n=2*a +k*b. Let k be even then n can be written as n=2*a+2*b*c n=2(a+b*c) Hence, if k is even then n must be even as well otherwise it's not possible.if k is odd then you can get all numbers from k to n by using one k coin and the other 2 denomination coins. k,k+2, k+4,k+6,k+8....nsince it's given k<=n we don't need to check cases where k>n
•  » » » » 5 months ago, # ^ |   0 Amazing
•  » » 3 months ago, # ^ |   0 nice solution. It takes me some time to understand your solution. How can I improve my problem solving skills?
 » 6 months ago, # |   0 #include using namespace std; #define all(v) (v).begin(), (v).end() void solve(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while (t--) { solve(); } } void solve() { long long n, s1, s2; cin >> n >> s1 >> s2; long long r[n]; vector> v; for (int i = 0; i < n; i++) { cin >> r[i]; v.push_back({r[i], (i + 1)}); } // for (auto &it : v) // cout << it.first << " " << it.second << endl; sort(all(v)); long long tc1 = 0; long long tc2 = 0; vector lista; vector listb; for (int i = n - 1; i >= 0; i--) { long long cost1 = v[i].first * s1; long long cost2 = v[i].first * s2; tc1 += cost1; tc2 += cost2; // cout << tc1 << " " << tc2 << endl; if (tc1 > tc2) { listb.push_back(v[i].second); tc1 -= cost1; } else { lista.push_back(v[i].second); tc2 -= cost2; } } // cout << endl; cout << lista.size() << " "; for (auto &it : lista) { cout << it << " "; } cout << endl; cout << listb.size() << " "; for (auto &it : listb) cout << it << " "; cout << endl; } can anyone please explain me why this code will not work for problem B?
•  » » 6 months ago, # ^ |   0 I think you mean C
•  » » 6 months ago, # ^ |   0 The cost is different depending on where you put it. Say that the current number of elemnts in list_a is k1, and in list_b is k2, then the cost of adding an element S is S * (k1 + 1) * S1 in the first case, and S * (k2 + 1) * S2 in the second case.
 » 6 months ago, # |   0 Can anyone tell me why we need to fix the value of K in B.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Probably because once we increase leg for a, we have no operation to decrease it. It's fixed that way, and we have to utilize it to reach b as well. If we had calculated k separately for a and b, then it may be the case that k(a) is greater than k(b), which is a move we can't make!So we simply choose leg size that is optimal for both a and b, hence, k is fixed for both. At least that's how I think it goes.
•  » » 4 months ago, # ^ |   0 Let's say we are calculating answer for $b$ only (you can extend this to $a$ also).Now, let's say you are using 2 values of $k$ i.e. $k_1 < k_2$. So your answer would be kind of $b/k_1 + b/k_2$, here if you just replace $b/k_1$ with $1$ you would get better answer and we can always do this since we will always increase value of $k$ from 1 to $k_2$ and $k_1$ is working on just the remainder of $b/k_2$.
 » 6 months ago, # |   +3 E Has a nice observation, we would never take 3 consecutive edges. Any elegant solution using this observation.(Take , NotTake, Take) is better than (Take, Take, Take) and both achieve our goal. f(i) = min(2*e(i,i+1) + f(i+2) , 2*[e(i,i+1)+e(i+1,i+2)] + f(i+3))
 » 6 months ago, # |   0 Solution to problem B seems pretty complicated. Can someone please explain a simpler approach?
•  » » 6 months ago, # ^ |   0 It's not difficult. You should just know the answer is $\lceil\frac{a}{k}\rceil + \lceil\frac{b}{k}\rceil + (k - 1)$ when you add your feet to k long. Then if you remove the ceil, you can get $\frac{a + b}{k} + k - 1$, it's just an inequality $a + b \ge 2 \times \sqrt{a \times b}$ when $a = b$ the equality is achieved. Therefore, for this function, it's $\frac{a + b}{k} = k$, .i.e $k^2 = a + b$. So $k = \sqrt{a + b}$, you can get the smallest value. However, you remove the ceil, so there maybe 2 off the correct answer. You should check around. Anyway, 1e5 is enough.
•  » » » 6 months ago, # ^ |   0 How did you come to the conclusion that (A+b)/k)=k ?
•  » » » » 6 months ago, # ^ |   0 Because the inequality I wrote abode. $\frac{a + b}{k} + k \ge 2 \times \sqrt{a + b}$, and when $\frac{a + b}{k} = k$ the equality takes.
•  » » » » » 6 months ago, # ^ |   0 orz observation
 » 5 months ago, # | ← Rev. 2 →   0 HiCan someone explain how the output for case:15 3is 5 for the problem: (B)Long LegsThanks
•  » » 5 months ago, # ^ |   0 Let, a=5, b=3, leg=1. Make leg=2, so move=1. Go 2 steps forward. 3 steps remain to reach 5. Move=2 (1 to increase leg, 1 to move 2 steps forward) Make leg=3. Move=3. Go one step forward. so move=4. Now, leg=3. Value of b=3. So we need one more step to reach b. So, move=5.
•  » » » 5 months ago, # ^ |   0 Thanks
 » 5 months ago, # |   0 can someone recommend more problems similar to E
 » 4 months ago, # |   0 Sorry for necroposting, but I want to share my solution of F without using KRT.Consider doing lazy tag on rollback DSU, when we visit to a certain time, add a tag with time stamp on the representative of vertex $1$, and when we rollback(assume this edge point to $boss$), if this edge is added before the tag on $boss$ is added, then push down the tag. At the end just check whether each vertex have tag on it.I found it is quite amazing that we can do lazy tag on DSU, maybe there also have some potential application of it?