We invite you to participate in CodeChef’s May Cook-Off, this Sunday, 24th May, from 9:30 pm to 12:00 am IST. 2.5 hours, 5 problems.
We will also be hosting a live problem discussion sessions for Cook-Off problems with our panelist Rajarshi RestingRajarshi Basu. You can register by clicking on the GOING button on the top right corner here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Joining me on the problem setting panel are:
- Setters: Ritesh rishup132 Gupta, Vikas [user: cus_pandey__ji] Pandey
- Admin: Teja teja349 Vardhan Reddy
- Tester: Raja raja1999 Vardhan Reddy
- Editorialist: Akash Whiplash99 Bhalotia
- Post-Contest Streaming: Rajarshi RestingRajarshi Basu
- Statement Verifier: Jakub Xellos Safin
- Mandarin Translator: Qingchuan Zhang
- Vietnamese Translator: Team VNOI
- Russian Translator: Fedor Mediocrity Korobeinikov
- Bengali Translator: Mohammad solaimanope Solaiman
- Hindi Translator: Akash Shrivastava
Prizes: Top 10 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.
Good luck and have fun!
Hoping for a set of balance problems in DIV 1.
Please don't.
That's the shame that my bitset solution got TLE in Curious Queries. Is Divide & Conquer and FWHT necessary to get AC?
Intended complexity was log(a_i)*N*logn. What was your complexity (is it better than it)?
Solution was on lines of solving bit by bit and using fft.
Solution: First let’s solve a smaller problem. What if the same question was asked for an array? i.e. An array A is given. Find the sum of beauty over all subarrays where beauty is equal to the product of xor of subarray and size of the subarray.
Prefix-Sum technique: We can solve the question over each bit level. Let’s suppose we know the prefix xor for all i then how to find the subarray whose endpoint is (i+1) and xor equal to 1. We can do this simply to find out the values of prefixes whose xor is 0, but how can we convert this into the length. Let suppose there are 3 prefixes with index value x1, x2, x3 such that x1, x2, x3 <= i then ans for (i+1) index is given by-
(i+1) — x1 + 1 + (i+1) — x2 + 1 + (i+1) — x3 + 1 3*(i+1) — (x1 + x2 + x3) + 3 Count of prefix equal to zero xor*(i+1) — sum of their index value + count of prefix equal to zero xor
answeri is equal to the sum of ans for each i. As we do this calculation for each bit and suppose there are n bits and we denote the answer for each bit by answerj then the overall answer is given by-
ans = answer0 * 20 + answer1 * 21 + … + answern * 2n
FTT technique: For each length from 1 to N if we are able to find out the number of subarrays such that their xor is 1(we are still working on each bit level). Then answerj can be nothing but the sum of the product of count of a subarray of length k and k for each valid k.
To find that, we first find the prefix of the array(still on bit-level) and we know if we subtract a prefix with xor equal to zero out of prefix of xor equal to 1 then we get a subarray with xor equal to 1, so construct the first polynomial where power is the size of the prefix and coefficient is 1 if the xor is 1 otherwise coefficient is 0 and the second polynomial where power is the size of the prefix(in negative) and the coefficient is 1 if the xor is 0 otherwise coefficient is 1.
Let the product of these polynomials is P then the power represents the length of the subarray and the coefficient represents the number of a subarray of that length with xor equal to 1.
But this is not all what If any prefix has xor equal to 0 and we substrate xor 1 prefix from it then this subarray also has the answer is 1, we can just reverse the sign of the power of polynomial P and add that to P gives the desired polynomial.
Now, back to our original question, As a submatrix is represented by two subarrays of different subarrays, so we can manipulate the answer for xor of the matrix from these subarrays.
If Both subarrays have even length then the submatrix should have xor value zero.
Let suppose (even_A)^1 implies that the number of even length subarray in A with xor 1. If we observe than the sum of beauty over all sub-matrix is given by-
(even_B)^1 * ((odd_A)^0 + (odd_A)^1) + (even_A)^1 * ((odd_B)^0 + (odd_B)^1) (odd_A)^1 * ((odd_B)^0 + (odd_B)^1) + (odd_B)^1 * (odd_A)^0
To answer queries, we can use a segment or Fenwick tree or simple prefix sum.
Complexity: O(N log^2 N)
I had n^2/32 * log(A) during a contest. I tried to implement an idea with FFT and it got TLE as well. I wonder how it can pass if for maxtest you do 4 times FFT of size 2^18 and you must do it for each bit. It seems to have huge constant factor. Any tips?
I did some testing over your code. I think, your FFT implementation is too slow and that would cause TLE.
Man this Problem (Chef, Chefina and Their Friendship) even accepted bruteforce TLE Solution
Yeah that was terrible but its codechef so we can expect that.
We can accept the issue from the server side, but this was hilarious, if someone has framed the question with such constraints he should do stress testing also, this shows how careless they are
That also explains why so many Accepted solutions in Div2 than Div1 because Div1 people were trying string hashing, z-function etc. and Div2 people just tried the brute force solution(most of them might be thinking s.substr() takes O(1) time) and got it Accepted.
Yes, it was a mistake. We had anti tests for the brute forces. But we had only one such test in a file which surely was not enough to stop them (we thought it was enough).
It was also partly due to me asking to try to reduce the test files and constraints a bit to reduce load on servers. We reduced constraints on sum of lengths after everything was prepared.We messed up somewhere around there.
Good to see quick response from your side hoping that you will resolve this issue
Yeah I realised it as soon as I saw the no. of people who solved it in div 2 but it was too late :(
Hi,
Test cases are updated. You will have new test cases in the practice section.
That's not cool! my solution wasn't getting accepted and i lost 160 rating and i am back to 3* and during the contest i saw some people solving it quite fast and after reading this comment when i checked their solution most of them used just substr function specially div2 participants :(
Yeah I know but let it be, if you are deserving you will get it back
For sure!
Someone passed Chefland Squads and the Army Chief with wavelet matrix ? (I got AC with fenwick tree ):)
Can you explain how you used fenwick tree for the question?
You can count the number of squads with strength <= K using a two-pointer method in O(n), then binary search on K for the answer.
Edit: it's actually O(n log n) because of the Fenwick tree.
Can you explain how you do that in O(n), smh
Sorry, I just realized I made a mistake in my response. The runtime is O(N log N) (there are O(N) calls to a Fenwick tree).
For each L = 1, 2, ... N, we'll count the number of R >= L such that the subsequence with indices {L, L+1, ..., R} has <= K inversions. Start with L = R = 1. Now if we increment R to R+1 we get |{L <= i <= R | A[i] > A[R+1]}| extra inversions. We can keep track of this number with a Fenwick tree. Increment R as many times as possible while keeping the number of inversions <= K. Now add (R-L+1) to the total number of squads. Next, increment L to L+1, subtract the number of inversions involving L (just like above, use the Fenwick tree), and increment R again as many times as possible. Continue until L = R = N. Since we only increase L and R, the whole runtime is O(N log N)
Would it be better than $$$O(N\log^2(N))$$$?
Same complexity, doesn't need any updates but with a worse constant in the query, so it's more slow :(
Can someone please help why greedy would fail in CHEFTRIP? Link to the explanation — https://discuss.codechef.com/t/why-greedy-fails-in-cheftrip/66605
Hi, I briefly read your description and I think you're making the false assumption that the leader(?) node in your DSU must be the point where the sequence goes from increasing to decreasing.
I tried your code locally and it doesn't work for this case
Hi, thanks for the test case, by my assumption, all vertices for above tc will be in 1 set, and have leader 2 (since its height is max). and answer for the query should be 1. Actually, in my solution, I was checking h[v] < h[u], but I forgot h was sorted, so indices are not correct (Apologies for messed up code). I have now corrected it.
I made the changes here which passes your counter example — https://www.codechef.com/viewsolution/33321951. But fails the system TC.
Can you please tell why my assumption is wrong? Thanks.
UPD: It fails if for a element there are 2 disjoint sets with which it could be a part of decreasing sequence. e.g.
since vertex 1, can be a part of 2 sets, I was ignoring that in my solution.
try this
If I understand your code correctly, node 4 with value 9 will become the leader of 1 and your
find_setcheck will fail because 7 is its own leader.Btw my approach in the contest was to decompose the increasing/decreasing parts of the path and use LCA/binary lifting to quickly check some cases. I didn't see an editorial posted yet, so you can refer to my submission here
Yes you have understood it correctly. Your test case, is somewhat similar to the one I posted in update section, but still different in the way, since both '1' and '7' are in different sets, and a path between them have a component itself ('3' is in a different set). I got it now why it is failing. Thanks once again for your time. Will refer your solution, thanks for that too :).
This is my first and last time participating in Cookoff contest. I believe submatrix means “subset of rows and columns”, but surprisingly it wasn’t. I wasted tons of time debugging sample, and after realizing this I just ragequitted. You should clarify this in the statement.
WTF, what’s wrong with the downvotes? The statement is clearly wrong, and there was no way to do a clarification. In vast context, e.g. the definition of determinants, submatrix is a subset of rows/columns, and it’s how Wikipedia defines it too. I don’t see any reason to assume something is contiguous (such strong assumption SHOULD BE noted)
It’s also not like the sample explanations were clear. You have to count the number of entries, hope author didn’t excluded some terms for brevity, and then guess which kind of strange assumption author had made.
You are right. As per wikipedia it is a subset.We are sorry for it, None of us in the panel never thought of it and we thought it was a straight forward definition. Hence, we never thought of it even being ambiguous. I assume the same with people who downvoted you. Also I tried to check in few other cf problems, they have described the definition of submatrix. Few things to my defence:
a. All of the problems I have checked that used submatrix used the contiguous version (though most or all had the definition mentioned).
b. you could have asked for a clarification, there was a comment option below every problem which is the way clarifications happen in codechef.
c. Sample explanation had all the terms enlisted. I would not assume some terms were excluded for brevity since he got the correct output using those terms. So he could have only excluded zeros (but if you looked at it, you would know he did not assume it).
Finally, I want to understand how to avoid such scenario in future because it is not like we missed something here. Because we never had suspicion in the definition we used (Also I think majority would have had the understanding we had though it is wrong). That was the reason we did not explain it.
I got the point b now (but trust me, I tried hard to find it). Thanks for the information.
For the last part, I don't really know. I think you should be obviously careful about the subset being contiguous or not. But surely people can make a mistake.
This is Polygon advices aka Mike's rules for problem setters. Can be useful for you.
One of them is always copies pasting standard statement instead of reinventing (defining subsequence, substring, subsegment with the same definition). They even define GCD, AND operator, XOR operators always using a Wikipedia link.
Because you are the only person in the world who thinks submatrix is not a contiguous rectangle. And probably you are also a Wikipedia vandal. Look at more reliable source.
novel way of refuting a Wikipedia reference, I approve
Wikipedia generally should not be the end of search of proof, but in this case references for this definition are quite solid
I guess ko_osaga would have to vandalize all the sources provided there as well
I read the problem CROADS wrong, thought the ^ operator as XOR instead of AND. But the interesting fact that I observed during the contest was that the answer is exactly the same for XOR and AND operators except when n is a power of 2.