### AlphaMale06's blog

By AlphaMale06, 2 months ago, Thank you for participating in the first ever Serbian Div. 3 Codeforces round!

Sorry

Also a massive thanks to Vladosiya for giving us a chance to create a divison 3 round!

1878A - How Much Does Daytona Cost?

Problem was authored and prepared by
Hints
Tutorial
Solution

1878B - Aleksa and Stack

Problem was authored and prepared by
Hints
Tutorial
Solution

1878C - Vasilije in Cacak

Problem was authored and prepared by
Hints
Tutorial
Solution

Problem was authored and prepared by
Hints
Tutorial
Solution

1878E - Iva & Pav

Problem was authored and prepared by
Hints
Tutorial
Solution

1878F - Vasilije Loves Number Theory

Problem was authored and prepared by
Hints
Tutorial
Solution

1878G - wxhtzdy ORO Tree

Problem was authored and prepared by
Hints
Tutorial
Solution Tutorial of Codeforces Round 900 (Div. 3) Comments (149)
 » Pretty balanced contenst
 » reverse madness was a cool one
 » Thanks for the fast Editorial.
 » Very interesting problem set, especially problem F
•  » » Why my solution is failing for F on tc 4 ; SolutionUsed pollard rho algorithm for d(n)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   it usually fails on test 4 when n overflows SpoilerYou have to check for divisibility by checking that all factors of divisor count are present in n, or like in the editorial
•  » » » » ok, thanks !!
•  » » » because n can be much more than 1e9 only d(n) <= 1e9, but not n
 » 2 months ago, # | ← Rev. 3 →   One of the best Div3. D problem, first I just printed valued of a,b (cause nothing else was coming in my mind :)), and then i was not difficult to see that for each possible a there is unique b
 » The idea behind E is nice but you can just code a sparse table to handle the query part from the binary search.
 » Can you please help me see why the code below times out? This code is for E. Thank you very much! #include using namespace std; int a; int sl,k; int check(int x) { int res = a[sl]; for(int i=sl+1;i<=x;i++) { res &= a[i]; if(res
•  » » Your check functions runs in $O(N)$
•  » » » Is the total time complexity O(t*p*n*logn)?
•  » » You can use a ST table or binary lifting to make your check in O(logn).
•  » » » Thank you very much!
 » I have a slightly different implementation for Problem G . My approach is the same as the editorial (finding the selective nodes where the bitwise or changes).However to find these nodes, instead of using binary search, we can maintain a map for every node. The map will have the $closest$ $ancestor$ to the current node for each distinct bitwise or possible. To find such ancestors we can use a map and iterate on it.Implementation
•  » » This implementation got TLE. To fix the TLE we can use vector of pairs instead of using an map. New implementation
 » 1878B — Aleksa and Stack, how smoothly they made me realise that only only odd numbers can divide odd numbers. while even can be divided by both.
 » I'd like to rephrase the proof of Problem C.The key observation is that we can always change the sum of k numbers from s to s + 1, given that s is not the maximal. The proof comes as follows. Assume that we have a set of k numbers which sum to s. Let denote the maximal among the k numbers as m. If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done. If the maximal is n, we can prove it by contradiction as shown in the tutorial, i.e., n, n — 1, ..., n — k + 1 will belong to the set. This set will yield the maximal and contradicts the assumption that s is not the maximal.
•  » » 2 months ago, # ^ | ← Rev. 2 →   If m < n, we can always achieve s + 1 by replacing m with m + 1 and the proof is done.m < n, so maximal is not n it is mentioned. even if it is n, we have to replace next maximal by +1 if it does not already exist. so on...
•  » » » Yes. I think the original proof in the tutorial is incomplete. The original proof actually proves the m = n case. When first reading the solution, it was hard for me to understand "However, since we have k of them, these are the k numbers that would yield the maximum sum (n,n−1,n−2,…,n−k+1). This is a contradiction!"
•  » » » » I don't get it how it's contradiction. but it is obvious that if we want maximum sum of k digit out of any random n numbers without repetition, we would choose first k digit after sorting in desending order or last k digit in asending order. Sometime Induction principle create overhead for simple problems isn't it?
•  » » » » » It contradicts with the assumption that the sum s of the k numbers is not the maximal.As stated before, the key observation is we can always achieve a sum s + 1 for the sum s, given that "s is not the maximal". Based on this observation, any value that lies between the minimal and maximal can be achieved. To prove the correctness of the observation, we can sort current k numbers and denote the maximal as m. 1) If m < n, we can replace m with m + 1 and obtain s + 1. 2) If m = n, we can prove by contradiction that "there exists a number a
 » 2 months ago, # | ← Rev. 2 →   In problem G, I don't understand why for each bit, we choose the vertex z such that it contains that bit, and z is closest to x (or y). What happen if we choose z such that it is not the closest?
•  » » Because it would produce the same results with the closest one. Therefore we don't have to check that node
•  » » » I don't know if I misunderstand something. I think that if we choose another vertex that is not the closest one, the result for the current bit which we want will stay the same, but we don't know whether bits in other positions will increase the answer or not.
•  » » » » That's why we need to consider both nodesFor example assume the path from $u$ to $v$ looks like this :$000, 001, 100, 101, 000, 010$Here are the path looks for each bits from $u$ to $v$ : bit $0$ : $0, 1, 1, 1, 1, 1$ bit $1$ : $0, 0, 0, 0, 0, 1$ bit $2$ : $0, 0, 1, 1, 1, 1$ And for bits from $v$ to $u$ : bit $0$ : $1, 1, 1, 1, 0, 0$ bit $1$ : $1, 1, 1, 1, 1, 1$ bit $2$ : $1, 1, 1, 1, 0, 0$ For the sake of explanation, let's number the nodes in the path with $1, 2, 3, 4, 5, 6$ (where $u=1$ and $v=6$)Now the closest nodes with $u$ that has a bit on for each bits are : $2, 6, 3$And the closest nodes with $v$ are : $4, 6, 4$Notice that the only important nodes are $2, 3, 4, 6$Node $5$ — for instance — is not important because from the perspective of $u$, the bit $0$ and $2$ will be "turned on" at node $2$ and $3$ respectively. While the bit $1$ is still "turned off" at node $5$ The key observation here is once the bit has turned on within a path, it will never be turned off again because the nature of the $\text{OR}$ operations
•  » » » » » Okay, let me think about it for a while, since I don't strongly understand about the fact of picking the first occurrence will give us optimal answer. However, thanks for your help!
•  » » » » » » Maybe the way you view it should be something like this : if the first occurence node produces the same outcome with the other nodes for the rest of the path, then it's sufficient for us to only check the first one and no need to check the rest
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   Could you provide an example when the second occurrence will be useless? The node 5 you provide above is not one of that type (it is totally 0)
•  » » » » » » » » Try this : $101, 100, 011, 110, 101, 110$The important nodes are respectively : From $u$ : $1, 3$ From $v$ : $5, 6$ We can see that node $4$ is useless because it produces the same results as node $3$ and $5$And node $2$ is useless because it produce the same as node $1$
•  » » » » » » » » » Thanks, I get it now!
 » even i can't solve the B one, but watching the editorial was really satisfy and pleasant
•  » » simple just print odd numbers from 1 to n since the condtion is always true for odd numbers
 » 2 months ago, # | ← Rev. 3 →   For problem E, we can calculate every position, the first 0 to the right of every bit.Then for each query, iterate each bit from low to high, and check first 0 to the right. If the current bit of k is 1, it needs to satisfy all the smallest right end points that are not 0. If the current bit of k is 0, since we iterate from low to high, the rightmost non-0 can be greater than or equal to k.I am not sure if my solution is correct, after all, it has not passed the system test. But I want to share my ideas with you, and the code is as follows:https://mirror.codeforces.com/contest/1878/submission/225352692
•  » » 2 months ago, # ^ | ← Rev. 2 →   I'v implemented this idea and got very simple code https://mirror.codeforces.com/contest/1878/submission/225492472
 » If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution. Here is my live screencast of solving problems [A -> E] (with detailed commentary in Hindi language).PS: Don't judge me by my current rating :(
 » Nice hints and comments in the solutions!For problem C, I wrote down lots of test cases on the paper to check and came up with the solution but couldn't prove it. It's good to see the proof in the editorial now!Thanks guys for the contest!
 » Hello. I have a question about Problem G. Why is the complexity not q*logA*logn*logn? Because finding the intersection points takes logA time, finding LCA takes logn time, and finally calculating by bits also takes logn time. I'm a little confused here，and my code get TLE.
 » E had a very long implementation, a little bit much for div3 question imo.
•  » » Have you seen the authors solution
•  » » » Small tutorial doesn't necessarily mean small code, apparently me being noob in implementing long code also hurts. Creation of prefix of all bits and then applying binary search on all of it is too much imo.
•  » » Lol, you should have seen Problem G then
 » don't say sorry contest was very nice. All the problems were very interesting.
 » 2 months ago, # | ← Rev. 3 →   there's a very simple O(N+Q) solution for E 225432409First, notice that the only positions of R that change a[L]&...&a[R] are those where the bit which was set in a[L] gets reset. Calculate the next positions where each bit gets reset and store them. Then for each query iterate over those "important" R positions and update the current value of a[L]&...&a[R]. If at a certain R the answer stops being greater than K, then the answer is R-1, otherwise the answer is N-1.
•  » » That is a O(NlogN + QlogN)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   It's not logN, it's log(max a[i]), but fair enough, I guess it shouldn't be considered a constant
•  » » » » That's more than log N lol(n<=2e5, max(a) is 1e9)
•  » » » » » my point is it's faster than the editorial solution while not being any more complex
•  » » » » » » In editorial its said it can be O(NlogN) with sparse tables(which is faster than yours) :)
•  » » » » » » Yeah, we said there is a $O(N \cdot \log(N))$ solution with sparse tables, and it's very simple (if you know sparse table). We said we allowed slower solutions because it's div. 3.
 » Can I solve the problem E using segment tree? For each query I can use binary search to find the value of "r" and find the value of f(l,r) using query method of segment tree. Time complexity O(q*logn*logn). But I am getting wrong answer after performing binary search.
•  » » Yes
•  » » for(int i = n; i >= l; i--)This doesn't look like binary search I think.
•  » » » Thanks for the reply. When I used this for loop I was getting TLE. But when I used binary search, I got wrong answer on the first test case.
•  » » Here it is: 225454109
•  » » » Thanks vai.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Can you tell me where did i do wrong? void solve() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n); vector rn; int q; cin >> q; while (q--) { int l, k; cin >> l >> k; int ans = -1; int left = l; int right = n; while (left+1 < right) { int mid = (left + right) / 2; int val = query(1, 1, n, l, mid); if (val >= k) { left = mid; ans = mid; } else { right = mid - 1; } } rn.push_back(ans); } for (int i = 0; i < rn.size(); i++) { cout << rn[i] << " "; } cout << endl; } 
•  » » You can even perform it $O(qlogn)$ when you are in some node in the segment tree, you see if the $and$ to the right child is still >=k then you go there. Else you go left.
•  » » » Would you mind giving me the code?
•  » » » May be there is a misunderstanding. How the complexity is O(qlogn)? ..ans every query by binary search and inside every transition of binary search finding "AND" of (l to mid) take O( q* (log(n) )^2)
•  » » » » sorry I was wrong I don't think my solution works
•  » » 2 months ago, # ^ | ← Rev. 2 →   Yup..after the contest when i was going on through the questions and saw problem E,the first approach which came to my mind was of segment tree. I coded it and it got accepted. It's time complexity was of O(nlogn+q*logn*logn). It crossed 2s time limit. I got little astonished but then i saw that the maximum time limit was of 5s. Here is my code 225420310
 » Problem E and D could have been swapped.. But I'd still say I liked the contest, specially solving D gave me so much pleasure :)
 » In problem E cant we do bitwise AND between low and high using simple linear for loop like: for(i=low; i
•  » » 2 months ago, # ^ | ← Rev. 2 →   NOP! It cause TLE. It is because the complexity will be O(q * n * log(n)), but expected is O(q*log(n)) or O(q * (log(n))^2)
•  » » » ok got it thanks buddy!
 » I think the most easier way (I mean no need handle bit by bit) to do 1878E - Iva & Pav is to use seg tree. Here is my solution: 225454109
•  » » YES got it, and one thing the time complexity is better if we solve by using bit by bit than seg tree I guess ?
•  » » » I think, my solution can be optimized a little bit to gain expected complexity.
•  » » » » okay.
•  » » » Using pref sums or sparse tables is lowest possible complexity in this problem, but segtree also passes with added log N factor :)
•  » » » » Yes.okay.
•  » » » » Can you please let me know if there exists a way to calculate bitwise between given range l and r using segment tree?
•  » » » » » yea its pretty easy. Just search on internet AND segment tree(u can take lets say sum segment tree and just instead + write &). Just note that in E from this round u don't need update(its called modify in some sources), so just use qry and build function.
•  » » » » » » ok thanks dude
•  » » » » » » am sorry, i am about to upvote yourr reply, by mistaken I downvoted and now its undoing even i try :|
 » In D, I used binary search to get the indices, then calculated all the reversals I have to do, then just copy paste a solution of CSES substring reversals. Even if the CSES solution uses treaps, you still can just copy a solution without thinking about the treaps part
 » 2 months ago, # | ← Rev. 2 →   I've observed this thing regarding all ICPC-style contests on CF(i.e., div3/div4/edu rounds): fast solving doesn't matter as much as it matters in normal rounds. For eg. contestants who solved the same no. of problems as me in this div3 but half an hour before me are ranked just 400 places ahead of me.
 » In problem C it should be the sum of 1 to n-k elements (4th line)
 » 2 months ago, # | ← Rev. 2 →   Awesome round in general. The problem are balanced and cover a lot of topic. I really like problem F.However C is a little bit adhoc but I think it is fine. And in my opinion, the gap between C and D is close enough.
 » sparse tables are a little bit too advanced of a topic for div3 E Meanwhile problem G: range minimum query, binary lifting, LCA.
•  » » That's a Div3G though. Div3G can be near Div2E level, which is fine to have these kinds of algorithms
•  » » » Yup
 » 2 months ago, # | ← Rev. 4 →   This is a snippet of neal's solution of D snippetfor (int q = 0; q < Q; q++) { int x; cin >> x; int index = int(lower_bound(R.begin(), R.end(), x) - R.begin()); int a = min(x, L[index] + R[index] - x); a--; flips[a]++; } for (int i = 0; i < K; i++) { int sum = 0; for (int a = L[i] - 1, b = R[i] - 1; a < b; a++, b--) { sum += flips[a]; if (sum % 2 != 0) swap(S[a], S[b]); } } Not getting why max(x, l[i] + r[i] - x) is not being considered while doing the swap or even during the preprocessing of queries. Edit: Ok, got it. So the answer lies in this statement — It is easy to see that the modifications x and n - x + 1 are equivalent.Can this CSES task be also solved by similar trick, or advanced DS like treap is mandatory?
•  » » The task cannot be solved the same way, because here the operations aren't symmetrical, and the order of operations matters.
•  » » » Oh, ok. Thanks for clarifying.
 » Can Someone explain why my code gave TLE ? 225358802
•  » » Have you tried lowering your bitscount to 30 or at least 31? Also you don't need 64-bit integers for this problem since all elements in the array are not greater than $10^9$.
•  » » » Yes , but it is still giving TLE 225510500
•  » » » » Your prefix array size MAX is wrong, in the problem array can have up to $2e5$ integers.Accepted submission: 225521320, TLE: 225521499
•  » » » » » Thank you so much , I didnt realise that simple mistake in contest :(
 » F is a very nice problem. Thanks for this round. Hope we see you again.
•  » » Thank you, it's my favorite problem I created
 » During testing, I found a nice offline solution for E.The idea is to iterate from right to left and keep the value for each current prefix. When the values $f(i,i)$, $f(i,i+1)$, $f(i,i+2)$, ... are stored in some array, we can find the answer to some query by performing a binary search. In fact, we keep the right endpoints (denoted by $j$) in an array. We update the left endpoints ($i$) dynamically.This is $O(n)$ memory. Updating the values when traversing from $i$ to $i-1$ can require up to $O(n)$ time. It seems like the total complexity is $O(n^2)$, which is untrue. In fact, it is amortized. Notice how we only need to update the values for which $f(i,j)$ changes. Modifying them decreases the total number of bits (among all values of $f$). The number of bits is $O(n \ log \ A)$, making the complexity $O(q \ log \ n + n \ log \ A )$.
 » Thank you for the round. Hope we see you again.
 » Man, there's an even simpler solution for B: for(int i = 0; i < n; i++) { std::cout << i + 5 << ' '; } 
•  » » I know, I said there are many constructions, but this one is the easiest to prove I think.
•  » » » I guess you're right. This one though also fits a possible restriction for the output like a_i <= 3 * 10^5.
•  » » AhhhhhhI tried to make the answer table, but the code is too long...And I used a strange code:225314696
 » I hope all contests all balanced like this one , great contest
 » I solved problem E by using a segment tree to query each segment in logarithmic time but it TLE'd in python3 during the contest. I found out just now that using Pypy is much faster and the solution is easily accepted. Is pypy a reasonable choice for competitive programming or will I still commonly run into this runtime trouble in the future?
•  » » I don't know much about python but pypy is much faster than standard python compiler(found that while was working on round xD).
 » Hall of fame level task names and descriptions
•  » » Iva & Pav as best problem on codeforces ever :)
•  » » » Agree :)
 » 2 months ago, # | ← Rev. 2 →   In problem D, instead of editorial's approach where it is taking into consideration the parity of number of operations as a condition to swap. I'm maintaining an array (1 based) which stores the number of operations on x [x = min(x, ri + li — x)]. For every query, I perform prefix[x]++ and take prefix sum of this array after all the queries. Now, if parity of number of operations (in the prefix sum array) before starting a new pair of (l, r) and number of operations at any index (in the prefix sum array) during the iteration in this pair is different, that would suggest a swap is required at that index. Otherwise, continue iterating. But I'm getting wrong answer as verdict. Please help me find where I'm going wrong.Here is the submission link : https://mirror.codeforces.com/contest/1878/submission/225566736
•  » » You do realize that $a=min(x,ri+li−x)$ in problem's text is a gimmick because it can be simplified to $a=x$ always?This means that in your query loop you can directly use $prefix[x]++$ without calculating $a$ and $b$ bounds at all.
 » 2 months ago, # | ← Rev. 2 →   why solving C in o(k) gives TLE ? Thanks in advance
 » Tutorial of D is terribly explained. Worst.
•  » » Could you elaborate?
 » A simple way of understanding...
 » AlphaMale06 may you explain how sparse table can help here ? as in what we need to implement in the sparse table related to this problem ? sparse tables as far as i know is used to find minimum in a subarray how here it works ?
•  » » Sparse table also used to find and , or , xor , min , max , sum etc in subarray
•  » » » ok what will it be used here as ? its not finding xor or min or max or sum isnt here?
•  » » » » and
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   thanks AndrewPav Acanikolic73
•  » »
 » I personally feel D was easier than E. Maybe it were the long statements.
•  » » Yeah it is, but many people learn some topics that are really advanced for their rank(like segment tree, not including pref sums here because it's easy to learn that idea even for newbie) and that's why E has more solves than D.
 » anyone can explain any of the below solutions if possible ? they took very much less time or sometimes quite low memory space. https://mirror.codeforces.com/contest/1878/submission/225305916 by satyam343 https://mirror.codeforces.com/contest/1878/submission/225321019 by vgtcross https://mirror.codeforces.com/contest/1878/submission/225297136 by jiangly
•  » » I'm pretty sure they use sparse tables (the thing mentioned in the end of editorial for E), that's how they get a solution in $O(n \log(n))$
•  » » » 2 months ago, # ^ | ← Rev. 5 →   My solution (linked above) used a segment tree and it is $O(n \log^2 n)$ (that's why memory is so small). I don't know why it runs so fast.Looking at the codes, neither of the other two linked solutions seem to use sparse tables. To me, it looks like they're using the fact that for fixed $l$, there are only at most $1 + \log_2 a = 31$ different values of bitwise and of subarray $[l, r]$ over all $r$. The "changing points" of the bitwise and can be calculated for each $l$ and stored in $O(n \log a)$ time and memory, and each query can be solved in $O(\log a)$ leading to a $O((n + q)\log a)$ solution.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   thanks for the reply it really helped me to understand now vgtcross AlphaMale06. The '31' is because suppose the l is having all bits set then we can put 1 bit to 0 and then the and will reduce that bit only else it all remains set only . likewise we can have maximum 31 different numbers. is this interpretation right ?
•  » » » » » Yes. Each bit can change value at most once so the total value can change 30 times, meaning that there can be 31 different values.
 » In problem E, how can we use sparse table to get $f(l,r)$ in $O(1)$? I thought it's still needed to reconstruct the segment in $O(log_2(r-l))$ time? (I don't know much about sparse tables)
•  » » If a query result can contain overlapping segments (min, max, or, and) then the sparse table only needs to look at two values for the answer. You find the largest power of 2 less than the range and calculate an overlap (eg for length 7 you do 2 queries of length 4 and include the value at position 4 twice).
•  » » » Ohhhh I see, thank you.
 » I'm getting TLEd on G. What I am doing is, while binary searching the answer, I am fetching the ancestor. So basically the binary search is from 1 to the number of nodes in the path, and accordingly I'm fetching the count of bits. The implementation isn't the best, but it works. This is heavy on time because during my binary search I'm constantly binary lifting to find the node, so the binary search costs O( log(n) * log(max(a)) ). Combine that with query and it TLEs out. I cannot clearly understand how the editorial does it in O( log(n) + log(max(a) ). Any help will be appreciated, thanks in advance!https://mirror.codeforces.com/contest/1878/submission/225749618
 » 2 months ago, # | ← Rev. 2 →   For E, solution has mentioned that we can use sparse table also.I am learning segment tree currently.. I think segment tree can also be used here, am i correct?
•  » » yes
 » Good contest and wonderful tutorial! Thanks.
 » 2 months ago, # | ← Rev. 2 →   Extended proof for F which may be useful in the future: If $x$ and $y$ are coprime, then $d(x\cdot y) = d(x)\cdot d(y)$ ProofWe will set some definitions first. Let $x$ be a positive integer, and let $f$ be it's prime factorization. $f$ is defined such that $2^{f_1} \times 3^{f_2} \times \ldots \times p_n^{f_n} = x$ where $p_n$ is the $n$-th prime number.By assuming the original conjecture to be true, we can also say that $d(x) = \prod_{i=1}^{n} d(p_i^{f_n})$ without loss of generality, since each term of the product contains a unique prime as their sole prime factor, making it coprime with any other term.It is well-known that a traditional method of factor counting is $d(x) = \prod_{i=1}^{n} (f_i+1)$. It is also easy to see that $d(a^b) = b+1$ for prime $a$. Therefore, we may equate the expansion of our original conjecture to the traditional method of factor counting (which is known to be true), proving the original conjecture. $\square$
 » Problem C: Note that the sum of n over all test cases may exceed 2⋅105.TC 05: 10000 194598 194598 10085825445 196910 196910 19386872505 193137 193137 6236620375 194427 194427 8160790120 ...shouldn't O(n) also be accepted according to constraints? have i missed something?
•  » » 2 months ago, # ^ | ← Rev. 4 →   the sum on $N$ over all the test cases $MAY$ exceed $2 * 10 ^ 5$
•  » » » oof, need to turn off the autocomplete thanks
•  » » » » no problem, I thought also the same xD
 » Can any of you tell me how the E question was optimized with a hash table, the official question solution doesn't give any specific instructions.
 » 2 months ago, # | ← Rev. 2 →   For problem F solution 2, I was actually originally going to do this solution for the problem, but I was deterred because to find prime divisors and their exponents for $d(N)$, I have to find prime factorization of $d(N)$. Thus, we need to keep track of the smallest prime factor of numbers up to 1e9 (because $d(N)$ is bounded by 1e9) if we want logarithmic complexity. This uses too much memory. Has anyone figured out an implementation to find this prime factorization without use of smallest prime factor?
•  » » If you have all the primes up to sqrt(1e9) there are less than 3500 primes to check. You can loop through that list and if you don't find a factor then the value is a prime. It isn't logarithmic complexity, but fast enough as there are only 1000 queries.
•  » » » However, in the editorial it is claimed that a logarithmic time complexity can be achieved for the prime factorization d(n) (it shows this in the time complexity). How is that achieved?
•  » » » » It's possible to store d(N) as the map of prime divisors adding/removing new divisors on each query and never needing to factor a large number. Each query can add at most 19 new divisors.
 » Hye guys!You can see the detailed solutions for the problems A,B and C with proofs from my youtube video below:https://youtu.be/odTQC7AOL3s?feature=shared
 » somebody help me with my implementation for F, it is getting wrong on test 4 My Code// i started at 1:03 A.M. 1/2/2022 Author:: Gorssorser , nice to see you here , thnx for visiting // somebody give me self control text me at my codeforces handle : gorssorser // i am gorssorser <-n-> //Mei toh bass bajata hun mujhe kya pata ¯\_(ツ)_/¯ //Duniya mei sb log jo tumhare aspas hai sb bhut acche hai.. aur yhi tum glt hogaye, sb madarchod hai.. ////////////////////////////////////////////////////////////////////////////////////////// #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include ////////////////// Defining here /////////////////////////////////////// #define debmatrix(matrix){ cout<<"debuged matrix: "<, rb_tree_tag, tree_order_statistics_node_update> pbds; using namespace std; ll n, x, m, y ; ll mod = 1e9+7; ll mul(ll a,ll b, ll mod = mod) { return ((a%mod)*(b%mod)+mod)%mod; } ll add(ll a,ll b, ll mod = mod) { return ((a%mod)+(b%mod)+mod)%mod; } ll power1(ll a, ll b, ll mod = mod) { ll ans = 1 ; while(b) { if(b&1) { ans = mul(ans, a, mod) ; } a = mul(a, a, mod ) ; b>>=1 ; } return ans ; } ll solve(ll bit ) { cin>>n >> x ; m = n ; while(x--){ ll div = 1 ; cin>> y; if(y == 1){ cin>>y ; n *= y; ll n_ = n ; for(ll i = 2 ; i <= sqrtl(n) ; i++){ ll cou =0; while(n%i == 0){ n/=i ; cou++ ; } div = div*(cou+1ll) ; } if(n != 1 ){ div = 2ll*div ; } n = n_ ; // cout<>n ; correct order , // like sort or arrange the things accordinglyif int main() { #ifndef ONLINE_JUDGE // For getting input from input.txt file freopen("input.txt", "r", stdin); // Printing the Output to output.txt file freopen("output.txt", "w", stdout); #endif cin.tie(0)->sync_with_stdio(false); cout.tie(NULL); int t = 1 ; cin>>t ; // mod = mod ; int counter = 0; while(t--) { counter++ ; int bit = 0 ; if(counter == 5 )bit = 1; // cout<<"Case #"<
 » In ProblemG, can anyone say why am i getting TLE in testcase 24 227234745?
 » my segment tree solution for E 227542958
 » Problem D was a good one. However the tutorial was not so clear. I think the tutorial should emphasize the relation between the example (l = 1 and r = n) and common l and rs. It really took me an effort to really comprehend(Yes I'm newbee, and I'm sure there are lots of like me out there.....)
 » Hi, for problem G, I don't quite understand why the array r can be used to calculate the OR operations. Can anyone explain to me what is the logic behind that?
 » Gave virtual contest, solved A B D E, failed on C. for C I assumed it would be on the easier side and I guessed the solution kinda. I am not able to correctly prove the solution. I tried doing a brute-force simulation of the process by taking the smallest set 1..k and then replacing it as needed but not able to proceed as the logic itself was not clear. Is it possible to get the valid set ? Asking in case instead of YES / NO, if it was a constructive question.