### 300iq's blog

By 300iq, 3 years ago,  Tutorial of Codeforces Round #612 (Div. 1) Tutorial of Codeforces Round #612 (Div. 2) Comments (131)
 » 3 years ago, # | ← Rev. 2 →   Could someone please explain the DP approach of problem C of Div-2 ?
•  » » 3 years ago, # ^ | ← Rev. 5 →   there are two ways:Firstly, let dp[i][j][k][0/1] means the answer to range 1-i with j odd numbers and k even numbers and the ith number is even/odd, so you can easily get the dp transition formula.And the final answer is min(dp[n][num1][num0],dp[n][num1][num0]). num1 means the total odd number in range of 1-n and num0 is the even.（num1 equals to ceil(n/2) and num0 equals to floor(n/2) ) The time complexity is O(n³）Secondly, since the number of even and odd used is sure in the range 1-i( if you use j even numbers, the number of odds is certainly i-j) , you can just use dp[i][j][0/1] where j means the number of evens in range 1-i (or that of odds if you like), and the dp dynamic formula will not change a lot. The time complexity is O(n²）
•  » » » Can you explain the transition formula. I still can't get it.
•  » » » » My submission: 68264857. I did almost the same thing but by optimizing the recursion. What you do here is that if we have an empty slot we put a number that is divisible by 2 or not. Then, you have to compare the result of that recursion with out current result and print the final result.
•  » » » » Well, I gonna talk about the first type of dp transition formula and I am sure that you can think about the second one based on my explanations.Firstly, based on the definition of the dp array, the formula is related to the value of ai. If ai ≠ 0， so we know whether it is odd or even. If it is an odd, the formula is " dp[i][j][k]=min(dp[i-1][j-1][k]+1, dp[i-1][j-1][k]) ". The explanation is that if you consider the value in the range 1~i with j odds and k evens used and the current one being odd, you need to think about the values, which you have calculated, in the range 1~(i-1), with (j-1) odds and k evens used since it is the only legal transition state to the current state. And whether the previous one you choose is odd or even depends on their values. Similarly, for a even number, it is " dp[i][j][k]=min(dp[i-1][j][k-1], dp[i-1][j][k-1]+1) ". Otherwise, ai is 0. So we dont exactly know whether it is odd or even, and we need to talk about both two situations. So both two above formulas should be considered.Secondly, in order to get a correct value, we need to initialize the value of dp array correctly. So let's initialize them as 'inf'( a big value ). The reason is that 'inf' represents the illegal condition which we can avoid when we do 'min' operation. After that , just let dp=dp=0 because these two are legal situations.(Before anything starts, we stand at pos 0, use 0 odds and 0 evens, and the complexity is also 0). So that it the first dp transition formula( the dp array of which consists many 'inf' values because there are many illegal situations ) , you can try to think about the second one, which consists less illegal situations.
•  » » » » » Very nice explanation. Thank you.
•  » » » » » Thank you for the explanation
•  » » » » » dp[i][j][k]=min(dp[i-1][j-1][k]+1, dp[i-1][j-1][k]) " Could you please tell me the significance of adding 1 to dp[i-1][j-1][k] in transition function ? Thanks in advance gold1103
•  » » » » » » it is very simple. When you calculate dp[i-1][j-1][k],you put an even number on position i-1. So when you put an odd number(because the last index of the current condition is 1) on position i, the answer(the complexity according to the problem) should add 1
•  » » » » Are the students really angry in problem A ?
•  » » » My submission based on your logic above, and which should be O(n^2), seems to TLE on case 57.Can you take a look, please?
•  » » » » UPD: Nevermind! A stupid error when I was recomputing already computed values. This passes. Thanks!
•  » » » Can you please help me in telling what is wrong with my approach I am using 3 state DP array Here is my code
•  » » 3 years ago, # ^ | ← Rev. 3 →   we can do it without dp also solution without dpcount all odd space(where starting and ending is odd) and even space(where starting and ending is even) sort both odd and even array. put odd at odd place and even at even and check from starting and ending space also.Time complexity:O(n).
•  » » » This is not O(n)
•  » » » » Technically, it can be done in O(n) as the numbers are all from 1 to n using the counting sort.
•  » » » » » Yes. Especially when the range is small.
 » quickest editorial !!
 » Could someone explain the approach for 1287D - Numbers on Tree?
•  » » My solution involves some dp on subtrees.Let's have a vector for every vertex $v$, where all vertices of its subtree are listed in increasing order of values assigned to them.Then, the transition is not difficult. For a vertex $v$, glue together all vectors of its children and insert $v$ into it on the $c_v$-th position. In order to get the answer, we look at the vector corresponding to the root of our tree: there, all vertices are listed in increasing order of values.Submission: 68292734
•  » » » Hey, your code seems to be really simple and neet. Can you please further explain it. I'm not able to understand your concept?
•  » » » I didn't get it. Why is order[v] guaranteed to be listed in increasing order of values even before inserting the element in c[v]th position?
•  » » » Congratulations on your elegant solution!
•  » » » 3 years ago, # ^ | ← Rev. 10 →   I understood lolihunter solution and i will just explain it furtherpart 1 : he will get for every node it's corresponding subtree in one vector so in the dfs recursion for every node he will get a vector with the subtree for the current node subtree[curnode] which in his code is order[v] so order[v] is the vector which contains the subtree for the node vpart 2: he then put every node in the c[node] position in this subtree vector why? that's was my question I will explain let's take the root for an example on the second test case the root was node one it's subtree would contain 4 elements and c[root]=1 what that means it means that there's only one element which is less than the value of the root so if i have an array of the subtree of the current node where will be the position of the root it will be in index 1 cause our index start at 0 and now there's only one element which is less than the root as c[root] states afterwards he calculated the order corresponding to the root node and sorted based on that order the solution can only use one vector for printing which is the root vector if we return the root at the end https://codeforces.com/contest/1287/submission/68254686 like this solution here .sorry if my explanation wasn't very clear.
•  » » » » i did not get it ? could you explain it once again
•  » » » how can i ever learn to think like this?
•  » » My solution of 1287D is just recursion: find all answers for subtrees for childs concatenate them to have nice 1,2,3...n form (all nodes except current node) insert current node at exact position, and increment all numbers above. 68267302 Why it works? Well, because childs are independent, and parent value is selected to cut all child nodes at exact position.
•  » » » could you explain the second and third point more clearly,i saw your code it was quite simple so could you help it more?
•  » » » » Let answer of subtree would be what: what you should output if only the subtree is given. Then define function that will give answer for any subtree, and assume that our function will always work. Then, if this function got task to give answer about certain subtree, we can feed it with all subtrees of childs. All of them has answer in the form 1,2,3...n. Also, keep along with it original indices of vertices.Second point is to concatenate them in similar form. For example, if we have three answers: (1,2,3,4), (1,2), (1,2,3,4,5,6), then we can get (1,2,3,4),(5,6),(7,8,9,10,11,12). Correspoding parts to each child is enclosed into brackets.Last point is: we should place our 'root' (parent of childs) of the subtree in the answer. We just insert it at place we need to satisfy restriction about number of vertices in subtree. So, if it needs to have 5 childs less than number, then we give it value 6, so it should be inserted like this: (1,2,3,4),(5,*6*,7),(8,9,10,11,12,13). Corresponding childs are enclosed in brackets again.
•  » » » WOW! Thanks for the pretty solution!
 » Please someone answer why my code for div2 B 68280267 is getting TLE , though my complexity is O(n^2(k+log(n))
•  » » For this task, even PyPy doesn't help. You also using some set things that are not superfast. To pass the limit, you need to use some magic, like bitwise operations or other tricky things. Just look how other people solved it using python.
•  » » I did the same in c++ i.e using set to get the third character. set has an biggest constant that's why it is giving TLE (at least in c++ not sure in python). So u should try to change set to 3 if conditions.for reference see this thread
•  » » » But I used a set of only 3 elements :(
•  » » » » ya but still due to a huge constant associated with set, this makes your code slow.
 » https://codeforces.com/contest/1287/submission/68316351 this is O(k(n^2)log(n)) solution.But still getting TLE. please help me with this. thanks in advance.
•  » » I guess your solution fails because of sort in your next function. Replace it with simple if's and your solution should pass.
•  » » » I changed it still getting TLE. https://codeforces.com/contest/1287/submission/68316468
•  » » » » Additional problem is that you performing temp=temp+symbol. You should do just temp+=symbol. Because temp=temp+symbol performs copying of string.
•  » » » » use (temp +=) instead of temp = temp + newchar when appending a char to a string
•  » » » » » Hey can you look into my code too please
•  » » » » » thank you so much.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   Gcbn
•  » » Try hardcoding instead of the function nex, might help
•  » » 3 years ago, # ^ | ← Rev. 3 →   Never try to access a value from map by operator[] if you're not sure it exists there. You should do auto it = m.find(temp); if (it != m.end() && it->second > j) ... Otherwise not existing value will be inserted with default constructor of int i.e. 0, which doesn't break the correctness but increases the time for the following tries to find a value
•  » » » Why to use m.find(temp) if same can be done by using m.count() function and it doesn't even return pointer it just return boolean value. if(m.count(temp)==1) ... 
•  » » » » That's because you need not only existence of the key, but its value as well. So in my case you do searching only once, in yours — twice at least
 » 3 years ago, # | ← Rev. 2 →   Wtf with the tags Div2A/Div2C???
 » 1286 A — Garland (C of Div-2) could be solved in $O(n)$ if we use radix sort.
 » My "solution" for div 1C:Query left and right half of string. Use basic backtracking to find all strings matching the answer, generate all candidates as concatenation of any possible string for left an right half. Calculate for each subsegment hash of answer for each string on this subsegment (can be done in O(n^2)) and find a subsegment giving distinct answers on all possible strings and query it. It takes two queries of length $n / 2$ and one of at most $n$ which is enough.I managed to find 8 different strings with same answer, namely: abaabbabaabaabbabbabaabbab abaabbabbabaabbabaabaabbab abbabaabaabbabaabbabbabaab abbabaabbabbabaabaabbabaab baababbaabaababbabbaababba baababbabbaababbaabaababba babbaabaababbaababbabbaaba babbaababbabbaabaababbaaba But in the official testcases my solution never encountered more than two candidates for each half.Any idea how do defeat it? 68322452
 » 3 years ago, # | ← Rev. 2 →   Could you replace the "1286B — Numbers on Tree" editorial's "Rightarrow" and "leq" with symbols. That would be appreciated. It appears only when the language is set to english.
 » Could you please attach the solution too?
 » Add solutions of those who contributed.
 » 3 years ago, # | ← Rev. 3 →   Can anyone please explain why the first code gets TLE on test 43 while the second one doesn't 68329420 68263645 DIV 2 Que B
 » Do yourself a favour and go see problem tags of div 2 C.
 » Could you give code for F? I get TLE with both fast zeta-transform 68330755 ($\mathcal{O}(2^{n} n^{2} \log n)$) and the $3^{n}$ approach 68330966, and AC only with fast randomised binary zeta-transform 68331478 ($\mathcal{O}(2^{n} nk \log n)$ where probability of success is polynomial in $(1 - 2^{-k})$).
•  » » (1 + sqrt(2))^n + n^3 * 2^n#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define endl '\n' #define all(a) (a).begin(), (a).end() #define len(a) (int) (a).size() #define forn(i, n) for (int (i) = 0; (i) < (n); ++(i)) using namespace std; void solve(); mt19937 rnd(2007); signed main(){ #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); swap(rng, rnd); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); } // Code const int maxn = 8000; long long a[maxn], b[maxn]; long long AAll[maxn], BAll[maxn]; long long A[maxn], B[maxn]; long long szA, szB; const int nn = 21; int FFT_A[nn + 1][(1 << nn) + 7]; int FFT_B[nn + 1][(1 << nn) + 7]; int FFT_C[nn + 1][(1 << nn) + 7]; int F[(1 << nn) + 7]; int BASE[(1 << nn) + 7]; void convolute(int *a, int N) { for (int k = N / 2; k >= 1; k /= 2) for (int i = 0; i < N; i += 2 * k) for (int j = 0; j < k; j++) a[i + j + k] += a[i + j]; } void convolute(vector &a) { convolute(a.data(), len(a)); } void reconvol(int *a, int N) { for (int k = 1; k < N; k *= 2) for (int i = 0; i < N; i += 2 * k) for (int j = 0; j < k; j++) a[i + j + k] -= a[i + j]; } void reconvol(vector &a) { reconvol(a.data(), len(a)); } int al(long long base[], int basesz, long long cur[]) { cur = 0; int szcur = 1; for (int ii = 0; ii < basesz; ++ii) { long long x = base[ii]; for (int i = 0; i < szcur; i++) { a[i] = cur[i] - x; b[i] = cur[i] + x; } merge(a, a + szcur, b, b + szcur, cur); szcur *= 2; } return szcur; } long long base; bool tree[(1 << 22) + 7]; void solve(){ int n; cin >> n; vector v(n); forn (i, n) cin >> v[i]; for (int mask = 0; mask < (1 << n); mask++) { int base_sz = 0; for (int i = 0; i < n; i++) if ((1 << i) & mask) base[base_sz++] = v[i]; int m = base_sz / 2; int szAAll = al(base, m, AAll); int szBAll = al(base + m, base_sz - m, BAll); long long AS = accumulate(base, base + m, 0LL); long long BS = accumulate(base + m, base + base_sz, 0LL); bool checkF = true, checkS = true; if (count(AAll, AAll + szAAll, AS) > 1) checkF = false; if (count(BAll, BAll + szBAll, BS) > 1) checkF = false; if (count(AAll, AAll + szAAll, -AS) > 1) checkS = false; if (count(BAll, BAll + szBAll, -BS) > 1) checkS = false; szA = szA = szB = szB = 0; for (int i = 0; i < szAAll; ++i) { long long x = AAll[i]; A[x&1][szA[x&1]++] = x; } for (int i = 0; i < szBAll; ++i) { long long x = BAll[i]; B[x&1][szB[x&1]++] = x; } int c = __builtin_popcount(mask) - 1; int s = (((c) & 1)); for (int _a = 0; _a < 2; _a++) { int _b = (s ^ _a); int r = szB[_b] - 1; for (int cura = 0; cura < szA[_a]; ++cura) { long long x = A[_a][cura]; while (r >= 0 && x + B[_b][r] > c) r--; if (r == -1) break; int nr = r; if ((AS == x && BS == B[_b][r] && checkF) || (-AS == x && -BS == B[_b][r] && checkS)) { nr = r - 1; } if (0 <= nr && x + B[_b][nr] >= -c) { tree[mask] = true; break; } } if (tree[mask]) break; } } for (int i = 0; i < (1 << n); i++) { BASE[i] = tree[i]; } memcpy(F, BASE, sizeof F); convolute(BASE, 1 << n); int rez = 0; int step = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < (1 << n); j++) if (__builtin_popcount(j) == i) FFT_A[i][j] = F[j]; convolute(FFT_A[i], 1 << n); } memcpy(FFT_B, FFT_A, sizeof FFT_A); while (accumulate(F, F + (1 << n), 0LL)) { // for (int test = 0; test < n / 2; test++) { rez++; for (int i = 1; i <= n; i++) for (int j = 1; i + j <= n; j++) for (int k = 0; k < (1 << n); k++) if (FFT_A[i][k] && FFT_B[j][k]) FFT_C[i + j][k] += FFT_A[i][k] * FFT_B[j][k]; memcpy(FFT_A, FFT_C, sizeof FFT_C); memset(F, 0, sizeof F); for (int i = 1; i <= n; i++) { reconvol(FFT_C[i], 1 << n); for (int j = 0; j < (1 << n); j++) if (__builtin_popcount(j) == i){ F[j] += FFT_C[i][j]; } if (accumulate(F, F+(1<
 » Anything else missing in the Div2 C taglist? •  » » How come this is interactive ?? haha...
 » My O(nlogn) solution for Div2D/DIV1B Insert all numbers from 1 to n in a order-statistics tree. perform a dfs,every time you newly enter a node s,assign ans[s]=value at position c[s] in the order-statistics tree,and erase that element from order-statistics tree 68342107
•  » » It's actually not necessary to use an order-statistics tree here, my submission with $O(n^2)$ passes quite easily in 30 ms.
 » Can someone point out what am I missing in this DP approach to C-Garlands? https://codeforces.com/contest/1287/submission/68341470
•  » » There are few issues, first: if(dp[odd][even][level]!=-1) return dp[odd][even][level];The above line doesn't make sense, cause if I am correct dp[odd][even][level] means there are "odd" number of odds and "even" number of even added to the the vector "a" till "level".Imagine a vector, 0 2 0 4 5 0 Now, the answer is 1 2 6 4 5 3 that is 2 but your program will give 3 because of above statement.According to your code, 1 2 6 4 is equivalent to 6 2 1 4, so if the program went on path 6 2 1 4 before 1 2 6 4, it will give the wrong answer. This is because the value of odd, even, the level is the same for both paths but since the path with greater value is calculated first, your dp[odd][even][level] may contain value which is not minimal for those value of odd, even and you are returning that non-minimal value without checking.What you can do is remove that line and check all possible conditions but I tried it and it's resulting in TLE.There's 1 more issue when you are setting a[level] to odd, you are not reverting it back to 0. I am no expert but that's all I could think of.
 » Can someone please help me with the editorial of LCC ? I have a few doubts. How to calculate the probability that the $i$ th collision occurs first ? Why ? Can someone explain this ? The editorial says that the answer for the mask is the probability that none of the $X$ collisions do not occur and the extremes move in the direction of the mask. What is $X$ here ? Also, what do the leaves of the segment tree hold ? What is the meaning of adding a ban ? Please help me.
•  » » Even though I solved just now LCC and just checked isn't there better solution in editorial, I couldn't understand it in the first place. But, it turns out, it's describing same approach. So, not surprising that you didn't understand it.Now, what I want to clarify is following. it says first i. It means first i collisions in list sorted by time. To make things clear, if there are n particles, then potentially you may have 3*n elements in this list. Each element of list is: which pair of two neighboring particles would collide in what configuration (three configuration described).Now, from where insight is comming. It's comming from neat fact that you may concatenate two segments using masks described. All you need to know, is probability to have ends of segment facing in certain directions, then you may concatenate them, and have new four values.So, you represent whole array of particles as array of unit segments with 4 masks, and using segmented tree you may find probability of whole segment. The trick is, that you may change single unit segment to ban some of combinations, and recalculate probability of whole segment in log(n).Finally, fact about occurance. When I realized it on my own, I was thinking in following way: lets calculate probability that nothing collide. It's just ban all collisions. Now, if we allow highest time of collision: there are two cases: nothing collide, or one or more collide at the same time the highest time of collision. So, probability that you have highest time collision is: probability of highest time of collision allowed minus probability of no collision allowed. Similarly, probability of second highest time is probability that it's allowed (and above) minus probability of highest time collision allowed (and above).
•  » » » Thank you for your reply. If it is okay with you, can you please clarify some of my doubts ? Here is what I understood so far. The first collision is always between consecutive particles. We will calculate the time it takes for each of the $(n - 1)$ pairs of consecutive particles. We want to calculate the probability that the $i$-th of these collisions occur first. In order for this to happen, we need to change the directions of some particles to ensure that none of the $(i - 1)$ particles which come before have a collission. What I did not understand is how we use a segment tree to do this. Can you please help me ? :)
•  » » » » (1), (2) is right. (3) we don't change any directions of particles. We ban pairs of consecutive particles to collide in exact configuration. So, for particles 5,6 we can do at once: LL — allow to collide, RR — ban, RL — allow for example (I don't care here about possibility of this case, but we can ban RR only). Segment tree is need to calculate probability of all this happen. If you have trouble with probability understanding, for n particles there is $100^n$ variations, and particle $i$ fly to the right in $p_i$ cases and to the left in $100-p_i$ cases, then you may count how many of configurations among $100^n$ is correct (taking bans into consideration), then divide the number by $100^n$ and it is probability. Then, apply expectation value formula by definition and you'll get answer.
•  » » » » » If you are free, can you please work out a small example $(n = 3)$ by hand and show how to do it on paper ? :)
•  » » » » » » Try to solve different problem. Statement is following: you're given $n,\;m,\; 0 \leq p_i \leq 10,\;0\leq t_i\leq 2,\;0\leq x_i\leq n-1$, it is number of particles, number of bans, probability 0 to 10, type of ban, and position of ban. You need to calculate number of arrays $a$ of length $n$ of numbers 0 to 9 such that some configurations banned. if $t_i = 0$ then condition $a_{x_i} < p_{x_i}\;and\; a_{x_i+1} < p_{x_i+1}$ should be false. (anology to RR) if $t_i = 1$ then condition $a_{x_i} \geq p_{x_i}\;and\; a_{x_i+1} \geq p_{x_i+1}$ should be false. (anology to LL) if $t_i = 2$ then condition $a_{x_i} < p_{x_i}\;and\; a_{x_i+1} \geq p_{x_i+1}$ should be false. (anology to RL) Then, when you'll write this thing, find out how to add ban online and update answer fast.
 » Why is time limit getting exceeded on test case 10? I cannot understand. My submission https://codeforces.com/problemset/submission/1287/68273741
•  » » even i am getting TLE on test case 10 for 68349376
•  » » You can use combination and use map for count the same string. Here is my code
•  » » As it was mentioned in comment above, you should perform appending char to a string with S+=symbol, not S=S+symbol.
•  » » » Thanks
 » 3 years ago, # | ← Rev. 2 →   it's interesting that the vast majority of div1 folks just decided to use dp in div1_a. i bet they knew about the solution the author presented here, but still they prefered dp. so the rule of thumb — avoid greedy approach if you are unsure about some parts of it?
•  » » I think it's more so that the DP solution is much cleaner to implement. With the greedy solution you also have to consider special cases (ie. intervals on the bounds of the array, $n=1$, all zeroes).
 » for problem B, why does 68349376 give TLE inspite of being n^2logn?
•  » » Your problem is in check function. Using set to get needed char increases complexity. And also you missed that fact that your algorithm is k*n^2*logn.
•  » » » yeah,sorry for the complexity,but what should i do to optimise then?should i write using ifs?
•  » » » » yep, here's my submition of your algorithm with ifs that is AC https://codeforces.com/contest/1287/submission/68353515
•  » » » » » my one also got accepted with ifs now 68356480 THANKS
•  » » 3 years ago, # ^ | ← Rev. 2 →   Another approach is to note that it's possible to write a perfect hash function mapping a card to a 64-bit integer, since $3^k < 2^{64}$Example: 68357302
•  » » » Even more $4^k < 2^{64}$. So you can evaluate all symbols in parallel using bitwise operations. Add on top of that open hash table with square steps and you're blazing fast 68356690
 » I can't get it. Can somebody explain it please?
 » In 1286D, can 2 non-adjacent particles collide with each other for anyone else? Because, taking that assumption problem would be much easier.
 » Could you please show the solutions connected to these approaches?
 » Could someone explain the approach for doing div-1 question A though dp?
 » Wow, I have completely different solution to D. Mine is in fact much more complicated and fact that time of collision when both particles go facing each other is strictly less than time of collision when they go in the same direction is in fact crucial to my solution, while model solution just don't care. But I'm too lazy to describe it cause it's long x_0.
 » 3 years ago, # | ← Rev. 2 →   My (maybe simpler) solution for 1286D - ЛЧК:The main idea is still sorting all the collisions and calculate the probability that first $i$-th and $(i + 1)$-th will occur. When it comes to calculating these probability at some certain time, I have some following observations.Lets first denotes the types of two protons colliding: $0$ — moving toward each other, $1$ — both moving to the left and $2$ — both moving to the rightObservations: If we only take collisions of type $0$ into account, a consecutive segments where every protons have collisions with its neighbors, can only accept patterns like this: $«««...»»»$. Which means, we can always find a position which its left part will only move to the left and vice versa. Let's also denote this as special positions. Events of type $1$ and $2$ will narrow the set of possible candidates for such positions in observation 1, but they still lie in a consecutive segment. It's easy to see that if some pair of $i$-th and $(i + 1)$-th protons can not both move to the left, we can not put such position anywhere in the right of them. So each reduction of these events is equal to banning a prefix or a suffix of possible candidates. For a consecutive segment with the range of special positions, we can easily calculate the sum of probability that this segment will obey the mentioned pattern with prefix product array for moving to the left, suffix product for the right, and prefix sum of product of them (just some easy work on paper).When we connect two components with some event of type $0$, it's a few casework to figure out the resulting component's range of special positions. And since events of type $1$ and $2$ always occur later than corresponding events of type $0$, two protons of these events always lie in the same components. So we just need to narrow the range and recalculate the probability. My code: 68383975.
•  » » 3 years ago, # ^ | ← Rev. 2 →   Hey,I have some problems with understanding of the LCC problem. Could you, please, briefly explain why in the third example the correct answer is 150902884?To be honest, when I read the problem description I expected the solution to be a real number.
•  » » » Well it's already stated in the statement that you need to print the answer as $P . Q^{-1}$ where $P/Q$ is the real number you mentioned.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Thanks for the reply. But I am still confused. I was always taught that integers don't have an multiplicative inverse (besides -1 and 1). In addition, it is mentioned that $Q$ is a natural number, which does not have additive inverse as well. What does $Q^{-1}$ mean then? Could you give an example? For instance, if the answer is 99/123, what should I output?
•  » » » » » Here's how $123^{-1}$ modulo $998244353$ looks.For $99/123$, just multiply them together and mod the result by $998244353$.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   Thanks a lot! Now it makes sense!Basically, ($123^{-1}$ mod 998244353) is 32463231, since 32463231*123 mod 998244353 equals to 1.
 » I still have no idea why 1st submission got accepted while 2nd one was not accepted. 1st solution 2nd solution Can someone help me, I only changed s = s + s[i] to s+=s[i]
•  » » s = s + k creates a new string equal to s + k which takes $O(|s| + |k|)$ time and memory and then assigns it to ss += k works in $O(|k|)$ (according to c++ standard might also work in $O(|s| + |k|)$, but that would be ridiculous to implement it this way)
•  » » » Great, just learnt a better way of doing. Thanks.
•  » » » » Just notice you have Luftwaffe in your username. You still can change it for two days.
•  » » » » » The Iran had bombed US bases and I have to prepare for word war 3.
•  » » » » » » So you can at least change it to 303 Squadron
•  » » » » » » » Nopes, I don't trust brits.
 » Can someone point out what's wrong in my DP approach to C-Garlands? https://codeforces.com/contest/1287/submission/68427357
•  » » u need to keep track to previous element to. dp[i][o][e][flag] will be the right dp state.
•  » » » Why? Can you please elaborate?
•  » » » » bcoz when a[i] != 0 and you are calling recurrence, and then when u r checking a[i] == 0 that a[i] != a[i-1] but how can a[i] be a[i-1] if for a[i] == 0 u r just making a[i] to 1 or a[i] to 2. you need to keep track of previous element whether it is odd or even or whether u filled it by even or odd. If you want code you can ping me. Amritanshu_7
 » plz anyone tell me what is wrong in my approach of question B Hyperset 68457311
•  » » 3 years ago, # ^ | ← Rev. 2 →   First: O(n^3k) has no chance of passing a maxtestSecond: for (int i=0;i
 » can anyone point out the mistake for solution of problem-Garland my solution is this...
 » Looks like, even though according announcement 1286E - Fedya the Potter Strikes Back will accept any answer by modulo 2^64, current checker wants full integer or there is some bug with comparison. unsigned long long didn't accepted for me, but bigint accepted.
 » if (a[i] % 2 || !a[i]) dp[i][j] = min(dp[i — 1][j] + 1, dp[i — 1][j]); if (a[i] % 2 == 0 && j) dp[i][j] = min(dp[i — 1][j — 1], dp[i — 1][j — 1] + 1);The above code is a sanp from a garland problem, please can anyone explain what does i,j and 1 mean, i'm not able to get it with any comment
 » 3 years ago, # | ← Rev. 2 →   time complexity of question Dic2-C is O(n) not O(nlogn)
•  » » There is some sorting involved, that's why $O(n\log{n})$.
•  » » » by using counting sort, we receive to O(n) solution.here i explain O(n) solution.
 » How to do OR convolution on independent subsets?
 » Can anyone please help me by telling that what am I doing wrong in my DP approach for problem C Garland.Click here to see my code.
 » can someone checkout where is my solution failing?https://codeforces.com/contest/1287/submission/69256035for problem C Div 2
 » Can someone explain the masking and segment tree used in Div. 1 D: LCC?
 » 3 years ago, # | ← Rev. 2 →   [ignore; Codeforces had a slowdown and caused me to post twice]
 » 3 years ago, # | ← Rev. 6 →   Since I struggled with understanding the solution for 1287F - LCC too, here's my sample code and explanation that may help others:Sample code: 70597982Explanation:Each segment (including the "segment" consisting of a single particle) is represented by a tuple of 5 values, $(ll, lr, rl, rr, ban)$. E.g. $rl$ represents the probability that: No collisions in this segment AND Leftmost particle moves right AND Rightmost particle moves left while $ban$ is an enumerated value or bitmask indicating a ban on certain possible collisions with this segment's right neighbor, only used when the segments are combined.Assume no collisions and no bans when first building the segment tree. We find all possible collisions and sort them by the time of collision (represented in my collision tuple as the fraction $\dfrac d v$, i.e. distance over relative velocity). We iterate through them; to find the probability that a particular collision comes first, we get the probability before the ban, ban the collision by changing the $ban$ value in the leaf node corresponding to the left particle, then get the probability after the ban. The probability we want is then $p_{before} - p_{after}$. We leave the ban in place for later collisions.When combining two segments, consult the left segment's $ban$ to decide what values should be added to the $(ll, lr, rl, rr)$ of the combined segment. The combined segment inherits the $ban$ value of the right segment. This is represented by the function plus in my Seg class.Due to the expense of combining operations and frequent querying for the entire segment tree, the segment tree code, based on the type described by this blog entry, has been modified to always round up to the nearest power of two for the internal size. This allows access to the root in $O(1)$ time, and saves about 400 ms in my example.
 » 3 years ago, # | ← Rev. 3 →   test: 8 2 0 4 0 6 0 7 0 answer on this test is 1 according to accepted solutions: 68650401 , 68385020 , 69983917 , but I don't know which permutation gives us this result?
 » 2 years ago, # | ← Rev. 2 →   I solved Div1D(LCC) with Segment tree, but I see one of the tags for it is matrices. Could it be another solution? If true. Could anyone show me how to solve it? Update: After reading some users using matrices a while, I found out that using matrices only make the source code cleaner and the main idea is still Segment tree
 » Could Someone please explain the approach of problem B of Div-1 in more depth?
 » Can someone please explain the editorial approach of Div1-B.
 » plzzz tell me, why in question B we do XOR with 66 66?
 » I am not able to understand B
•  » » So now 300iq has become admin of codechef......hmmmm......money-money-money!!!
 » Can somebody clear up the explanation for LCC??
 » In the problem Numbers on a Tree, What is the meaning of Rightarrow, leq etc?
 » 1287 A — O(k) solution using regular expressionWe need to find the longest 'AP' Substring (if the string has 'AP','APP', 'APPPP' then 'APPPP' would be the longest substring) this would be the last batch to get angry, so we can employ any technique to find the longest 'AP' substring, Here I have used regular expression to find thatsolution python: import re def find_max_ap(students_line): pattern = r'AP{1,}' return re.findall(pattern, students_line) if __name__ == '__main__': t = int(input()) for _ in range(t): n = int(input()) students_line = input() res = find_max_ap(students_line) if len(res) != 0: print(len(max(res, key=len)) - 1) else: print(0) 
 » Can someone point out what am I missing in DIV1 A problem - https://codeforces.com/contest/1286/submission/141400274
 » 8 months ago, # | ← Rev. 3 →   UPD: After getting accepted, I found that it required the real answer, instead of the value modulo $2^{64}$.I was confused why the solution used unsigned long long passed, but I couldn't find it anymore.Maybe it's my careless mistake (to see such a solution). I'm sorry for that. I'm curious about the judgement of the Div.1 E, because the annoucement said: In this problem, any answer which is equal to the correct answer modulo 2^64 (which has the same remainder of division) will be accepted. and the different answers will lead to different results of decryption of $c_i$, which will lead to multiple answers.The code of the editorial used BigInt realization, while many submissions used unsigned long long or __int128, so it is theoretical that the situation above will appear.Is it because the real answer don't excceed $2^{64}-1$ so that nothing happened?