Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

PoPularPlusPlus's blog

By PoPularPlusPlus, history, 5 months ago,

1847:A — The Man who became a God

tutorial
solution

1847:B — Hamon Odyssey

tutorial
solution

1847:C-Vampiric Powers, anyone?

tutorial
solution

1847:D Professor Higashikata

tutorial
solution

1847:E Triangle Platinum?

tutorial
deterministic solution
randomisation solution

1847:F The Boss's Identity

tutorial
solution
• +124

 » 5 months ago, # |   +6 How this Believer.Code solution is accepted because in this solution vector had initialised with 1e5 and testcases wasupto 1e4 and how can 1e9 will running in 1sec time limit?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 I think you linked wrong solution link
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Nope,it's alright Believer.
•  » » » » 5 months ago, # ^ |   +6 n^2 solution got accepted in problem C.link: 212424847Can anyone explain why?
•  » » » » » 5 months ago, # ^ |   +9 Weak test cases probably contributed, but the other contributing factor is that your code was vectorized, Godbolt link. Your same code without the pragmas will TLE 5. 212505218Assuming CF's machines have 256-bit registers your code would have a near $8\times$ speedup (theoretically). You can read more about vectorization here (short version) and here (more in-depth).
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +8 Thank you very much for explanation.But still weak test cases or constraint.
•  » » » » » » 5 months ago, # ^ |   0 I submitted same solution and it gave tle on 5 you are right ://
•  » » 5 months ago, # ^ |   0 It is frustrating; mine is always showing TLE in test case 5 when I use vector.
 » 5 months ago, # | ← Rev. 2 →   -23 hmm
•  » » 5 months ago, # ^ |   0 What algorithm are you talking about? would be going through the editorial later but if there is a way other than the one mentioned in the editorial do link it please.
•  » » » 5 months ago, # ^ |   0 Problem C can be reduced to finding maximum XOR for a sub-array. Which is a standard problem.
•  » » » » 5 months ago, # ^ |   +33 Reducing problem C to finding maximum XOR for a sub-array is not a trivial task (at least it was not for me; when I finally submited a solution I was still not sure whether it was correct).
•  » » » » » 5 months ago, # ^ |   +6 I agree, it's not trivial in-fact I didn't even remotely think that. I just guessed a way round. (got -ve delta ultimately) The contest was fair except for the initial queue problem, which has happened before so not that big a deal.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, it was not so easy to see that we have to find maximum XOR, I figured that out after spending nearly 40 mins on the problem. But sadly I didn't know the implementation. I just wish I knew it was a standard problem becoz it would have my rating go up.
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 I Think i have much better approach let x[i] is suff xor [i..n] x1 x2 x3 x4 ... xk *(let i choose x3 to append)* (x1^x3) (x2^x3) 0 x4^x3 ... xk^x3 x3 *(let choose (x3^x4) to append)* (x1^x4) (x2^x4) (x3^x4) 0 (xk^x4) x4 x4^x3 Observation: we can create new element with 2 xors only just do (2^8)*(2^8) and find all new element and take max Observation: xor of 2 means X[i]^X[j] -> which remain the subarray 
•  » » » » 5 months ago, # ^ |   +9 The community is pretty weird, the guy asked "what algorithm" and I just answered that, in no way did I blame the authors for carelessness. I think people downvoted because they thought I was critical of the authors.
•  » » » 5 months ago, # ^ |   +1 https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/ I saw the same code in a lot of submissions today along with the same comments lol.I myself copied the code from my old submission in this problem https://cses.fi/problemset/task/1655
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 But the point of this problem is transform its several conditions into standard problem.Can you find the train of thought on the Google?I believe that the main idea of transforming is what the Author want to talk about.
•  » » » 5 months ago, # ^ |   0 Can you please explain,in c if we take i=1 and get a new power then again taking i=1, we can get the max power , why it will not work plzzz help
•  » » » » 5 months ago, # ^ |   +3 Shouldn’t it be 0 if u do so? It’s XOR, any number xor Itself would be 0, and by doing so, you xor 1st-nth numbers for two times each, getting 0 at last.
•  » » » » 5 months ago, # ^ |   0 Sorry bruh I can't clearly understand what you mean,but I can share my idea about this problem.(Btw,this problem cannot be solved by Greedy maybe.)We can find that the new "strength" equals the suffix XOR of the array.Try to understand that two identical numbers' XOR equals to 0.Now it comes to 2 different conditions.First,if you choose a suffix which start at k1,then choose a suffix start k2,you will get a prefix which equals to the XOR of k2 to (k1-1),because k2 to n appeared two times and their XOR is 0.According to this conclusion,we can clearly find that we need to find a contiguous subarray to make its XOR as big as you can.Notice that you can get the prefix XOR.According to the conclusion of XOR,you can get any subarray by two prefix XOR together.Choose 2 numbers among n numbers and find the maxinum XOR,you can solve it by using Trie.Hope this comment can help you.
 » 5 months ago, # |   0 I somehow cheesed F. 212418362 my submission computes every element of (n-1) sized sequences for each different length, which is queried, so complexity is O(n*k), where k is number of different lengths appeared in input. I don't know is there a test to exploit it, random cases can't do it.
•  » » 5 months ago, # ^ |   0
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Got AC one more time 212520810 by don't storing a number twice.
•  » » » » 5 months ago, # ^ |   +24 HackedI generated the test with a help of simulated annealing, couting the number of times your calc() function gets called. In this test it is calculated 1300 times and your solution works in about 3300 ms, but if I run the generator for longer it will get stronger tests (it ran only for 5 minutes).
 » 5 months ago, # |   +35 SegmentForces
•  » » 3 months ago, # ^ |   0 Exactly!
 » 5 months ago, # |   +3 The contest was pretty good. I somehow couldn't find how to prove the assumption in C during the contest, and got lucky with my intuition there (which was that 2 operations are enough to reach the maximum)
•  » » 5 months ago, # ^ |   0 I'm upsolving right now, and I've come to a similar conclusion, it's only after to coming to this conclusion that I am able to understand the editorial.
 » 5 months ago, # | ← Rev. 3 →   +2 [deleted]
•  » » 5 months ago, # ^ |   0 Lets say u want any [L,R] then what u do is do operation of R+1 after this do operation at indices l. so what happens is 1 st step u get xor of (r+1)^(r+2) like this and after operation at l u get l^l+1^l+2^.....^r^r+1^..^n now what happens is first xor cancel all xor after r as r^r=0; so u get xor of [l,r].
 » 5 months ago, # |   0 In problem D, can someone please explain "Now, this t can be found using various pbds like set,dsu,segment tree,etc.", beacuse it is the only thing I couldn't figure out?
•  » » 5 months ago, # ^ |   0 You need the relative order of the first appearances for each index in string T, and when relative order comes into play then pbds or segment tree can be made use of. Not sure how to use dsu.For segment tree I mapped first occurrences for each index to a counter variable starting from 1 and made a segment tree of N nodes to maintain range sum.
•  » » » 5 months ago, # ^ |   0 I was thinking for every number from 1 to n to find first interval [L,R] in which it is? How to do it in O(nlogn)?
•  » » » » 5 months ago, # ^ |   +12 I used a set to find it. The set first takes all numbers from 1 to N and then I run lower bound on each L,R segment in order and remove the indexes which lie in [L, R]. I think it's pretty obvious that in this manner we can find the first occurrence for all indexes. An index once marked is removed from the set.My submission — https://codeforces.com/contest/1847/submission/212454814
•  » » » » » 5 months ago, # ^ |   +1 i assigned priority by using a little trick lets make a jump array initialise jump[i]=i+1 now we will iterate for these m segments for the ith segment(li,ri) lets start from li so if it is not visited(make a boolean bitset) then we will assign the current_priority to it and increase our current_priority by 1 now make li=jump[li] and update jump[li] as max(jump[li],ri+1)do these for all segments
•  » » » » » 5 months ago, # ^ |   0 in your while loop the worst case is O(m),so total time complexity of your set finding stuff is at least O(m*m);so how its not TLE'ing.
•  » » » » » » 5 months ago, # ^ |   0 Do you realize once the set becomes empty its going to be O(1)?
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 im sorry for being such an imbecile but in the worst case at the first iteration of while loop suppose if the lower bound points to the first element in your set then the set will become empty but n operations to erase it and the outer loop of O(m),doesnt that make it O(m*n),i am dumb so i ask these questions please help me,ignoring the logn operations of lower bound as it will affect slightly.
•  » » 5 months ago, # ^ |   0 I did it using a lazy segment tree( I saw many others doing it with sets, but idk how yet) Let T be an array of length 'n' where T[i] = x means that x is the first index such that L[x] <= i <= R[x].Initialise T to inf(or a value greater than m). for i in range(1,m): do range update: T[j] = min(T[j],i) where L[i]<= j <= R[i] The range update can be done in O(logn) using a lazy segment tree (google it). I know this is overkill, and I am looking for someone to explain the method using set. But if you have code for lazy seg tree beforehand, then it really is easy to implement during the contest without any fuss.my submission
•  » » » 5 months ago, # ^ |   0 Thank you guys
•  » » » 5 months ago, # ^ |   +7 We need to know the lowest indexed substring present at a given index 'i' of the string s from a collection of all possible substrings. Let's say we have this set for the index'i'. When we move to 'i+1', we simply need to delete all subtrings which end at 'i' and insert all substrings which begin from 'i+1'. So, we can iterate across all elements from 0 to n, performing 'm' insert and delete operations overall in the set, analogous to a line sweep.https://codeforces.com/contest/1847/submission/212435999
•  » » » » 5 months ago, # ^ |   0 Thanks for this well-phrased explanation( I could understand the idea from reading your comment just once!)P.S. How did I not see this first ?!! (Maybe because I read lazy segment tree just 2 weeks ago, and when I saw the exact problem, I got sucked in.)
•  » » 5 months ago, # ^ |   +3 The way I did it was to insert every number till n in a set. Then for each l and r I find the lower bound of l if it exists and is lesser than r and remove it from the set. Now find the lower bound of this number and keep doing this till either the set is empty or lower bound exceeds r.Submission: 212923478
•  » » 5 months ago, # ^ |   0 Can anyone answered me how to do this with dsu please?I still can't figure it out.
•  » » » 5 months ago, # ^ |   +5 The solution using DSU is actually quite elegant; it should look something like this: At first, all indicies are in their own components. Every component will always represent some continuous segment of indicies. For each component, we should store an integer $r$ — the rightmost value of the corresponding segment. This can easily be updated when merging components. For each component, $r$ has never been picked before, but all other indicies in the component have been picked already. When you want to find all remaining values from a range $[L, R]$ in increasing order, you should start by finding the component containing $L$. Now, the value of $r$ in this component is the first remaining value. After handling this, merge the current component with the component of $r+1$. Now, the new component containing $L$ has a new value of $r$; this is the next remaining value. After handling this, merge the component with $r+1$ and keep repeating this while $r \le R$. After that, you've found all remaining values in $[L, R]$. Those values have been merged into new components from the right and thus, those values are not the right points of any current segments and they won't be picked again. For easier implementation, you should add a dummy component at $n+1$. This allows you to avoid dealing with the element $n$ separately.
•  » » » » 5 months ago, # ^ |   0 Thanks! I can see it now! It is quite similar to the approach of https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/B .
 » 5 months ago, # |   0 Why I am getting wrong answer in D? Please help, my submission:212445636
•  » » 5 months ago, # ^ |   +6 You should debug how you calculate the priorities of indexes. Maybe there are some other issues as well but didn't check all of it.Input: 6 2 0 00000000 3 4 2 5 Must be inf 3 1 2 4 inf but you find inf 3 1 2 inf inf inf inf
•  » » » 5 months ago, # ^ |   +5 got AC... Thanks Man!
•  » » » 5 months ago, # ^ |   0 Can anyone please explain,in c if we take i=1 and get a new power then again taking i=1, we can get the max power , why it will not work plzzz help
 » 5 months ago, # |   0 I'm pretty sure time complexity in D is different from the one from the tutorial as it should include m
•  » » 5 months ago, # ^ |   -14 Can anyone please explain,in c if we take i=1 and get a new power then again taking i=1, we can get the max power , why it will not work plzzz help
 » 5 months ago, # |   0 i have the same solution for c (the first subm before A) but it TLEd on pretest 3 , why?
•  » » 5 months ago, # ^ |   0 from your code: for(int i = 0;i < maxn * 1e5 ;i++){ trie[i][0] = trie[i][1] = 0; }suppose t==1e5 -> needs 1e5*maxn*t -> tle
•  » » » 5 months ago, # ^ |   0 no not the trie one i meant the first submission (before A as i mentioned)
•  » » » » 5 months ago, # ^ |   0 212482567 I changed the map to a vector and it passed. don't use maps when values are not big your complexity is like O(n*(1<<8)*log(1<<8)) honestly it should pass by that complexity but the constant coeff of the map is high !
•  » » » » » 5 months ago, # ^ |   0 yeah i tried changing it to array it passed too, damn man i wouldnt have gotten all this penalty..................................
•  » » » » » 5 months ago, # ^ |   0 why would they not make the TL 2 seconds
 » 5 months ago, # |   0 D was really good problem
 » 5 months ago, # |   0 Can anyone please explain,in c if we take i=1 and get a new power then again taking i=1, we can get the max power , why it will not work plzzz help
 » 5 months ago, # |   0 LRForces
 » 5 months ago, # |   0 I believe the constant factor in C is very tight, I used a vector to save all creatable xor values and then, sort of dp'd it over. It basically was the same as the editorial, just keeping a vector of true values instead of array of booleans, which I hoped would've been equivalent but it is not so. :⁠-⁠\
 » 5 months ago, # |   +1 In Problem B : If the and of all the element is not zero why can't we divide them in more than one group? Example : 3, 3, 3 According to the editorial answer should be 1 but we can clearly see the answer could be 3 with minimum possible and for each group as 3.
•  » » 5 months ago, # ^ |   0 sum of the continuous groups should be minimum. if we divide into 3 groups, the sum is 9 whereas if we divide it as one group, sum is only 3.
 » 5 months ago, # |   0 In Problem B's editorial, it is written that if F(1,n)>0 then the answer will always be 1, but if the test case was like n= 42,3,2,3then we can see F(1,n)= 2>0 and we can divide the array into groups means the answer should be >1
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 the sum of all the groups should be minimumif we divide the array into two groups, the sum would be F(1, 2) + F(3, 4) = 2 + 2 = 4if we don't divide, then the sum is F(1, n) = 2, which is the minimum possible sum
•  » » » 5 months ago, # ^ |   0 Ohh I understood now , thankyou
 » 5 months ago, # |   0 Can anyone Please tell were this code is wrong. https://codeforces.com/contest/1847/submission/212493731
•  » » 5 months ago, # ^ | ← Rev. 3 →   +2 #ifndef ONLINE_JUDGEll freopen("input.txt" , "r", stdin); freopen("output.txt" , "w", stdout); #endif I removed these lines and submitted, it works. I'm surprised you didn't notice. submission:
•  » » » 5 months ago, # ^ |   0 But How it Worked ?
•  » » » » 5 months ago, # ^ |   0 I haven't used it to take input previously but judging from your previous submissions: You previously used #ifndef ONLINE_JUDGE but here #ifndef ONLINE_JUDGEll Perhaps the key lies there.
 » 5 months ago, # |   0 painful E
 » 5 months ago, # |   +3 hartiksalaria explain solution of problem D.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 First, explain to me why for TC 2, the answer for 2nd query is 3. state of string t after update 2UPD: Finally I understand what's going on there thanks to letsintegreat So first observe that you actually just care about the first time any index in s appears in string t(s) which gives us a compressed version t'(s) where every index is present at most one time. Now to make t(s) lexicographically largest we try to put as many ones in the prefix as possible.We can place all the ones we have in our string s in the prefix of t'(s) so our t'(s) can have min(len(t'(s)), one) length of prefix filled with one, so we just need to replace every zero in that prefix with some one. So answer for each query is just number of zeros in that prefix.
•  » » » 5 months ago, # ^ |   0 wish i had read 2nd TC. I was in another dimension, problem misunderstood. I thought that we have to swap in string t but it was 's'. it is easier than problem C :(. Thanks gawd, i would have never cared to read TC.
•  » » » » 5 months ago, # ^ |   0 I agree, the implementation and idea is not that hard to come up with, it's just that there were so many moving parts in the problem that it was easy to miss a crucial detail, during the contest I had the correct idea but somehow I assumed to just ignore every index which was not present in the given m segments due to which I wasn't able to make sense of 2nd query of TC 2.
•  » » » » » 5 months ago, # ^ |   0 I have no regrets. I am still not able to think to give priority to indexes :)
•  » » » » 5 months ago, # ^ |   +3 We can't help misunderstanding the problem in the first go. But not going through sample test cases is a huge mistake, especially in problems with so many intricacies such as D.
 » 5 months ago, # | ← Rev. 3 →   +25 F can be also done in O(Nlog(max(A[i]))logQ):We can notice that from each starting point, only at max 30 positions are important ie. Whenever a new bit is added in the range bitwise OR.So we only need to look at these ~30N potential answers instead of the n^2 potential answers.Now for each potential answer, we get a prefix of queries that can be satisfied, so we can use a difference array type technique, for minimums instead of for sums.submission: 212515812
 » 5 months ago, # |   +11 Is it just me or do the proofs for C make no sense?If anyone can dumb it down for me, I would greatly appreciate it.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 My consideration during contest:let $a_{m+1}=a_i\oplus .. \oplus a_m$ $a_{m+2}=a_j\oplus .. \oplus a_{m+1}$Using the first formula to replace $a_{m+1}$in the second one.(assuming $i •  » » » 5 months ago, # ^ | 0 It does clear things out. Many thanks!  » 5 months ago, # | 0 Can some one explain why this is true for Problem C: ** If it is, then there is some position p •  » » 3 months ago, # ^ | 0 the editorial basically gives a solution similar to finding maximum subarray sum, we store the xor found so far from prefixes in a boolean array and use them to compute maximum xor for j.  » 5 months ago, # | ← Rev. 3 → 0 1847B - Hamon Odyssey Solution from editorial with Greedy algorithms gives wrong answer for test case: 1 5 2 3 1 5 4 output is 1, but should be 2, because: [2, 3, 1, 5, 4] should be divided to 2 contiguous groups: [2, 3], [1, 5, 4] => (2 & 3) + (1 & 5 & 4) = 2 + 0 = 2, this is minimum strengths sumGreed algorithm works as: [2, 3, 1], [5, 4] => (2 & 3 & 1) + (5 & 4) = 0 + 4 = 4, this is not minimum strengths sumPS: My mistake;( It works correct because anyway (2 & 3 & 1 & 5 & 4) = 0 which is less than 2 and 4! For this problem only number of groups matter but not groups themself.  » 5 months ago, # | ← Rev. 2 → 0 F can be solved in O(n log max(a[i]) + q (log n + log q)) 212559533  » 5 months ago, # | 0 Shouldn't it be f(n+1, i) in the first proof part of C by the def. of f(u, v)?  » 5 months ago, # | 0 Why do I keep getting TLE on test 13? 212785251 •  » » 5 months ago, # ^ | 0 me tle on test 12 bud. making me doubt the complexity 212807276 •  » » » 5 months ago, # ^ | 0 It is because of processing a large number of ranges. Just try to not reprocess a index once visited.  » 5 months ago, # | +8 Proof of C is poorly written. •  » » 5 months ago, # ^ | +8 really very very poor  » 5 months ago, # | ← Rev. 2 → 0$O(NlogMAX + QlogQ)$solution for F. Uses some dumb counting sort + the observation about$logMAX$required bits.https://codeforces.com/contest/1847/submission/212474580  » 5 months ago, # | 0 Hi, I have submitted code for problem D, but it is showing WA. Can someone help me understand why? Here is my submission link: 212934178 •  » » 5 months ago, # ^ | 0 Take a look at Ticket 16991 from CF Stress for a counter example.  » 5 months ago, # | ← Rev. 2 → 0 Thank you for problem E!In the end, what worked for me was an adaptive priorities approach. For each side, maintain a mask of four bits: whether this side can still be 1, 2, 3, and 4. Now, as long as we have questions to ask, pick a triple of masks$(m_1, m_2, m_3)$, pick random sides with such masks, and ask about them. As feedback, see how many sides$u$became uniquely determined after this question. After that, change priority of$(m_1, m_2, m_3)$by$u - 1$: it does not change if we found one new side, decreases by$1\$ if we found none, and so on. Now, if we ever pick a triple of masks with the best possible priority, the silly questions are quickly filtered out, and only the promising questions remain.Had to also remember the asked questions, and consider pairs of questions: considering triples alone, my approach could not uniquely assign values for tests like [3, 3, 4, 4]. That's a technical detail though, which can be approached differently.
 » 4 months ago, # |   0 here l and r can be same?
 » 4 months ago, # |   0 .
 » 4 months ago, # |   0 PoPularPlusPlus Where did you get the idea to create the problem B?
 » 4 months ago, # |   0 As a weeb, I feel compelled to solve all these problems
 » 3 months ago, # |   0 noobs are discussing in comments;
 » 2 months ago, # |   0 in question 2 , if test case is 1,5,2,4,8,16,18,32 , actual answer would be 4 but your solution gives answer 3 , really please look into this