### majk's blog

By majk, history, 3 years ago,
Tutorial of VK Cup 2018 - Round 1

• +164

 » 3 years ago, # | ← Rev. 2 →   +1 On Div1C/Div2D:The same approach can be also implemented using multiset, which is probably faster to write, but has an extra multiplicative factor, which may or may not fit into TL.My solution got AC with maximum execution time of 2917ms. Let's say that I was lucky, or I have to send a dearest thank-you to pragma and synced C++ I/O for making that happened...
•  » » 3 years ago, # ^ | ← Rev. 3 →   +5 Sorry. Deleted.
•  » » 2 years ago, # ^ |   -16 edit please :D Let's say that I was lucky, or I have to send a dearest thank-you to pragma // AND SYNCED C++ I/O FOR MAKING THAT HAPPENED... you didn't use I/O sync in your code))
•  » » 15 months ago, # ^ |   0 Can you explain your solution?
 » 3 years ago, # |   +8 for div1a/div2b The solution works in O(N^(3/2)), which is fast in practice I used to think so, coded it in 36171159 and got TLE :( Perhaps I should learn a normal language
•  » » 3 years ago, # ^ | ← Rev. 3 →   +15 It can be much faster.Let the largest prime factor of X be p(X), and q(X) = X / p(X). Given X1, X0 = X1 - p(X1) + 1 = X1(1 - 1 / q(X1)) + 1. Notice that leagl X1's are always composite (not prime) and q(X1) is at least 2. If we find a X1 such that q(X1) = 2, all larger X1's will not produce better answer, and we can stop searching. X0' = X1'(1 - 1 / q(X1')) + 1 ≥ X1'(1 - 1 / 2) + 1 > X1(1 - 1 / 2) + 1 = X0, where X1' > X1 and X0' corresponds to X1'.q(X1) = 2 is actually quite common. It just means X1 is double of a prime, and prime is quite common. Since the distance to the next prime after N is roughly , we only need to search X1's. Therefore, the overall complexity is .My solution runs in 15ms: http://codeforces.com/contest/947/submission/36159299
 » 3 years ago, # |   +8 "Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."I agree with that, but why is P(N) always the best choice for the prime? Why is not possible to pick a smaller prime factor for X2 and then P(X1) for X1?And you meant [N - P(N) + 1, N], right?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +24 The largest prime factor gives the widest range of possible solutions. For example, if N = 14, the largest prime is 7 so the range is [8, 14] but if you choose the prime 2 the range is only [13, 14].I also think it is a typo in authors' range formula.
•  » » 3 years ago, # ^ |   +3 You can prove it that if you will pick some prime divisor smaller than the largest prime divisors the range, which you will get, of numbers from which we can obtain N will lie in the range given by the largest prime divisor.
•  » » 3 years ago, # ^ |   +3 Ad first question: The interval of the previous value is always [N - p + 1, N], where p is a prime divisor of N. For any prime, this interval would be contained in the interval [N - P(N) + 1, N], hence it is optimal to consider only the largest prime divisor.Ad second question: Yes, I'll fix it.
•  » » 3 years ago, # ^ |   0 "Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."Can you please explain this statement
 » 3 years ago, # | ← Rev. 2 →   0 The solution for B has an error in it, the range will be [N-(P(N)-1),N] and not +.
•  » » 3 years ago, # ^ |   0 here X(i) >= X(i-1) not just greater than so value should be strictly greater than its previous multiple
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 x2 = k2p2 — (1) x2 >= x1 — (2) (k2-1)p2 < x1 -> k2p2 — p2 < x1 -> x2 — p2 < x1 by (1) — (3) By (2) & (3) Range of x1 is (x2 — p2, x2] -> [x2 — p2 + 1, x2] where p2 is largest prime factor of x2.
 » 3 years ago, # |   +5 Auto comment: topic has been updated by majk (previous revision, new revision, compare).
 » 3 years ago, # |   0 can someone please explain the idea behind this solution : http://codeforces.com/contest/948/submission/36161437
•  » » 3 years ago, # ^ |   0 If you have X2 and want to know the range of X1 then you do the following. Factorize X2 = p1^k1*p2^k2...pn^kn (p1,p2..,pn are primes), then the range of X1 is (X2-pn+1, X2). Because if you choose a bigger range then we can not obtain X2. For example think about X2 = 14 = 2^1*7^1 The range for X1 will be (14-7+1, 14) = (8,14). If we choose the range (7,14) then when we peek x1 = 7 and the prime less then x1 (2 or 5) we can not get the X2. the same process is done for finding X0.
 » 3 years ago, # |   +1 majk Excuse me, about problem E. How can I figure out the eigenvectors v (and Q, Q^-1) using eigenvalues only rather than proof it after knowing it. Is there any material about this? Thanks.
 » 3 years ago, # | ← Rev. 2 →   +1 Answer to Bonus of Div1A/Div2B:We can precompute P(X) for all X in [1..N] with slightly modified Eratosthenes Sieve in : Each time we run a prime p through the sieve, mark all multiples of p with p. In the end, all numbers are marked with P(X)!Now, for each query X2, we can find the range of X1 in O(1) by looking at the precomputed table of P(X). According to my another comment, we only need to search X1's. And, for each X1, we can also find X0 in O(1) by lookup.Putting things together, this algorithms works in .
 » 3 years ago, # |   0 can anyone explain me the solution of problem c
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 The second solution: If we make a new pile of snow and subtract all pile of snow, obviously, we will get TLE. So, we don't do the subtraction. We can use a variable called sum which means the accumulated temperature until now. If v[i] <  = sum + t[i], then it will disappear and we can calculate the total volume of melted snow. For those v > sum + t[i], we just add t[i] * num to the answer. And there is another problem, the new pile of snow may v[i] <  = sum + t[i], but actually it doesn't disappear. So, we can add sum to every pile of snow in the begin. Finally we can use multiset to remove element in log(N). Here is my submission 36189438UPD: num means the number of pile in the multiset, because v > sum + t[i], so it won't disappear, the volume of melted snow is t[i] * num
•  » » » 3 years ago, # ^ |   0 thanks got it
•  » » » 3 years ago, # ^ |   0 what do you mean by this " add t[i] * num " .here num means???
•  » » » » 3 years ago, # ^ |   0 sorry, I didn't define it clearly. It means the number of pile which v > sum + t[i](already in multiset) And multiset has already sorted all element, so we can do it from the being of the set.
•  » » » » » 3 years ago, # ^ |   0 Why you add sum+t[i] always???
•  » » » » » » 3 years ago, # ^ |   0 Because sum means the accumulated temperature. Instead of subtracting all piles every time, we can just see sum to decide whether the pile disappear or not
•  » » » » » » » 3 years ago, # ^ |   0 OK,,I got it.Thanks..
•  » » » 3 years ago, # ^ |   0 Thanks for your explanation and submission, they were very clear!
 » 3 years ago, # |   -7 In Primal Sport problem shouldn't the answer be 14 for input of 20. Assume X0 = 14 If P1 = 4 then X1 = 16 (X1>X0) If P2 = 5 then X2 = 20 (X2>X1) Since we got answer 20 with X0 = 14 shouldn't that be the answer.
•  » » 3 years ago, # ^ |   +1 Here you are choosing p1 = 4 which is not a prime number
•  » » » 3 years ago, # ^ |   0 My Bad Sorry and Thanks gaurav569singh
 » 3 years ago, # | ← Rev. 2 →   +10 Problem F can be solved by randomized algorithm:If you just try random permutation and check if it meets the condition, (as you may know), it fails in test case around 96. However, if you modify this algorithm a bit, you’ll get accepted!Details are as follows:•Pick up vertex A which has biggest degreeAnd repeat this until you find the answer:•Take one leaf B from the other tree (that is, the tree which doesn’t contain A) randomly and map A to B•Take Vertex C which belongs to the tree with A and doesn’t connect to A randomly, and Vertex D which connect to B (B is a leaf, so D will be uniquely determined), and map C to D•Just try random permutation for remaining parts and pray for judge :)Code :36183744
•  » » 3 years ago, # ^ |   +15 Good job! What you described is equivalent to the correct way of solving the case where the the highest degree vertex has N-2 neighbours. This was the case that the most "naive" random solutions struggled with — and the antitests were usually of the form G = "almost star", H = "almost path". Part of the reason why there weren't too many strong pretests against random solutions is that this might help you tweak the meta parameters until you get accepted. In retrospect, I would put the test 96 in the pretest, so that contestants are at least given a chance to realize that we do not expect randomized to pass.In other words, if the contest was full feedback, we would probably require solution by increasing N to 100000. We felt that the task was difficult enough and implementing the required operations on the graph on sublinear time just added implementation time, but was more or less standard.
•  » » » 3 years ago, # ^ |   +10 Thank you for replying.Yes, I know it's very hard to implement this solution and pass system test within contest time.... (partly because we only know the result from pretest)I'll check O(N log N) solution later, thank you for interesting problem!
 » 3 years ago, # |   0 Can Div2 C is done by segment tree? if Yes please explain it.
•  » » 3 years ago, # ^ |   0 It can solve by segment tree, we only need to maintain the snow that melts every day for a volume equal to the temperature of the day.
 » 3 years ago, # | ← Rev. 5 →   -11 I get WA on test case 4 for question "producing snow"...Please help...Thanks in advance... Here's the link to my solution (http://codeforces.com/contest/923/submission/36195419)
 » 3 years ago, # | ← Rev. 2 →   -11 Can anyone please tell me what is the problem in my 948A: https://imgur.com/a/DYoBP. Judge says Changed (1,2) from S to D. But it doesn't look like that. UPD: I found it. I considered it as a 1 based indexing first. Sorry!
 » 3 years ago, # |   0 Can anyone elaborate on how to add 1 to a segment by two additions using prefix sums in Div2C/Div1B Producing Snow?
•  » » 3 years ago, # ^ |   +4 You add 1 to the start of the segment, and add -1 to the end of the segment. When processing points, you add the value in the previously created array to a curr variable, which will always indicate current element.
•  » » 3 years ago, # ^ |   0 By using a difference array. You can perform the updates in constant time and access all the updated values at the end in linear time.
 » 3 years ago, # | ← Rev. 3 →   +9 In the formula I think there must be T[j] not T[i]. Correct me if I am wrong.Problem 923B producing snow.
•  » » 3 years ago, # ^ |   0 Should be fixed now.
 » 3 years ago, # |   0 Can anybody explain how to do this? To calculate all F[i]'s fast, we can again use prefix sums — adding 1 to interval can then be done by two additions. Adding 1 to the range by 2 additions?
•  » » 3 years ago, # ^ |   0 Check the previous comments. It has just been asked.
 » 3 years ago, # |   +1 Can anyone explain the correctness of the trie/multiset solution of 923-C Perfect Security ? I just don't seem to understand why the algorithm mentioned in the editorial is correct.
•  » » 3 years ago, # ^ |   0 The question wants the minimum sequence. This means we should find the j that minimizes a[0] ^ b[j], remove b[j] from our list and continue. The structure with operations "minimize a[i] ^ x" over all x in a set and add/remove x is the binary trie.
 » 3 years ago, # |   -7 36157666Why RE?
 » 3 years ago, # |   0 Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710
 » 3 years ago, # |   0 There might be a typo in the editorial for problem f.The editorial says,"Assume that one of the graphs is 1-star. Without loss of generality let it be G. Denote v the vertex that can be removed to turn G into star, u its only neighbor, and w be the vertex of degree N - 2. In graph H, find any leaf and denote it w'. Let its only neighbour be u'. Furthermore, pick v' a vertex that is not adjacent to u' (such vertex always exists as H is not a star). "It seems that v' and u' should be swapped.
 » 3 years ago, # |   0 why my code is giving WA.http://codeforces.com/contest/948/submission/36241274
•  » » 3 years ago, # ^ |   0 Ya Got Accepted no need of help
 » 3 years ago, # |   0 In 923D — Picking Strings, transforming BAAB to BBAABB is possible, as per ac solutions, can someone demonstrate how the transformation is done?
•  » » 3 years ago, # ^ |   0 B.A.A.B -> B.BB.A.B -> B.BB.A.AB ->B.BB.A.AAB = BBBBB.B.B.B -> B.B.AB.B -> B.B.AAB.B = BBAABBI hope you understand my transitions :)
•  » » » 3 years ago, # ^ |   0 Yes I get it, and thanks a lot.
 » 3 years ago, # |   0 What is the tricky case in Test case 11 in Div1D — 923D Picking Strings?
•  » » 3 years ago, # ^ |   0 AAA BBAAA 1 1 3 1 5Answer is 0.
 » 3 years ago, # |   0 How would you solve Div2A if you were to minimize the number of walls being built?
 » 3 years ago, # |   -8 Thank You.Nice Editorial.solved C...First approach :)
 » 3 years ago, # |   0 Can someone explain priority queue method in div2c??
 » 3 years ago, # |   0 How to find Minimum number of Dogs in [948A — Protect Sheep]
 » 8 months ago, # |   0 Could someone please explain how to use dfs and similar in A part(948A) Please!!
•  » » 4 months ago, # ^ |   0 Collect all of the cell coordinates/ vertices of the wolves, W.Create an edge between every cell and it's left, right, down, up neighbors. For each w in W, run DFS and see if it can reach a sheep. If a dog (or another wolf?) is encountered during the search, end that leg of the search.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 I used this idea and ran a BFS from every cell containing a wolf and placed a dog if i ever encountered a ship but my program gives MLE. Can you help me where I'm going wrong? Code#include using namespace std; #define for0(i, n) for (int i = 0; i < (int)(n); i++) #define for1(i, n) for (int i = 1; i <= (int)(n); i++) #define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) #define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define forr1(i, n) for (int i = (int)(n); i >= 1; --i) #define deb(x) cout << #x << "=" << x << endl #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define tr(x) for(auto it = x.begin(); it != x.end(); it++) #define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define printclock cerr<< "Time : "<< 1000*(ld) clock()/(ld)CLOCKS_PER_SEC<< "ms\n"; #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define mod 100000 #define inf 1e18 typedef long long ll; typedef double ld; typedef vector< int > vi; typedef vector< vi > vvi; typedef pair< int, int > pii; typedef pair< ll , ll > pll; typedef vector vpi; typedef vector vpll; typedef vector vll; void dk_98() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } int lcm(int a, int b) { return (a * b) / gcd(a, b); } int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; void solve() { int r, c; cin >> r >> c; char grid[r][c]; for0(i, r) { for0(j, c) { cin >> grid[i][j]; } } vector > visited(r, vector (c, false)); for0(i, r) { for0(j, c) { if (grid[i][j] == 'W') { queue q; q.push(mp(i, j)); while (!q.empty()) { pii v = q.front(); int vrow = v.first; int vcol = v.second; visited[vrow][vcol] = true; q.pop(); for0(k, 4) { int crow = vrow + dx[k]; int ccol = vcol + dy[k]; if (crow<0 or ccol<0 or ccol >= c or crow >= r or grid[crow][ccol] == 'D' or visited[crow][ccol]) continue; if (grid[crow][ccol] == 'S') { if (grid[vrow][vcol] == 'W') { cout << "No\n"; return; } else { grid[vrow][vcol] = 'D'; } } else { q.push(mp(crow, ccol)); } } } } } } cout << "Yes\n"; for0(i, r) { for0(j, c) { cout << grid[i][j]; } cout << "\n"; } } int main() { clock_t begin = clock(); fast; dk_98(); int t = 1; //cin >> t; while (t--) { solve(); } printclock; } I found the error in my code and fixed it, but I can't fully understand why it was an error. Initially i was marking the cell to be visited while popping it from queue, but now i mark it as visited before pushing it in the queue. Can someone please explain why this was causing an error? AC code#include using namespace std; #define for0(i, n) for (int i = 0; i < (int)(n); i++) #define for1(i, n) for (int i = 1; i <= (int)(n); i++) #define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) #define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) #define forr1(i, n) for (int i = (int)(n); i >= 1; --i) #define deb(x) cout << #x << "=" << x << endl #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define tr(x) for(auto it = x.begin(); it != x.end(); it++) #define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define printclock cerr<< "Time : "<< 1000*(ld) clock()/(ld)CLOCKS_PER_SEC<< "ms\n"; #define READ(f) freopen(f, "r", stdin) #define WRITE(f) freopen(f, "w", stdout) #define mod 100000 #define inf 1e18 typedef long long ll; typedef double ld; typedef vector< int > vi; typedef vector< vi > vvi; typedef pair< int, int > pii; typedef pair< ll , ll > pll; typedef vector vpi; typedef vector vpll; typedef vector vll; void dk_98() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } int lcm(int a, int b) { return (a * b) / gcd(a, b); } int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; void solve() { int r, c; cin >> r >> c; char grid[r][c]; for0(i, r) { for0(j, c) { cin >> grid[i][j]; } } vector > visited(r, vector (c, false)); for0(i, r) { for0(j, c) { if (grid[i][j] == 'W') { queue q; q.push(mp(i, j)); while (!q.empty()) { pii v = q.front(); int vrow = v.first; int vcol = v.second; // visited[vrow][vcol] = true; q.pop(); for0(k, 4) { int crow = vrow + dx[k]; int ccol = vcol + dy[k]; if (crow<0 or ccol<0 or ccol >= c or crow >= r or grid[crow][ccol] == 'D' or visited[crow][ccol]) continue; if (grid[crow][ccol] == 'S') { if (grid[vrow][vcol] == 'W') { cout << "No\n"; return; } else { grid[vrow][vcol] = 'D'; } } else { q.push(mp(crow, ccol)); visited[crow][ccol] = true; } } } } } } cout << "Yes\n"; for0(i, r) { for0(j, c) { cout << grid[i][j]; } cout << "\n"; } } int main() { clock_t begin = clock(); fast; dk_98(); int t = 1; //cin >> t; while (t--) { solve(); } printclock; }