We invite you to participate in CodeChef’s Starters138, this Wednesday, 12th June, rated for till 6-Stars(ie. for users with rating < 2500).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Setters: Kanhaiya notsoloud1 Mohan, Harsh harsh__h, Aryan Aryan_Sinha Sinha, Wuhudsm wuhudsm, Abhishek TheAbbie Choudhary, Manan mexomerf Grover.
Tester: Takuki tabr Kurokawa.
Text Editorialists:Nishank IceKnight1093 Suresh.
Statement Verifier:Kanhaiya notsoloud1 Mohan.
Contest Admin : Yash yash_daga Daga.
Note: Some problems have subtasks
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
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. Hope to see you participating.
Good Luck!
Has the contest admin changed ?
TheAbbie orz
TheAbbie orz
Distinct Substring Video Editorial : YOUTUBE Video LInk --Click Here
wth , it hasnt even ended yet
No no....I have uploaded it 2-3 minutes before the end of contest... There was no chance of watching...understanding and implementing in just 2 -3 minutes... But still Sorry for that !
Imagine ppl cheating in CodeChef Starters xD.
The balance feels off, with large gaps between the last four problems. Look at div 2 standings, there's an order of magnitude difference between them. The problems themselves are not bad but the difficulty curve is heavily frontloaded.
The clarification section of Codechef is the most useless thing. They never reply any queries that's been asked.
They replied to me in a few minutes in previous contest.... I think they only reply to a doubt that is non trivial
Non-Trivial is a biased statement. In codeforces, If someone asks a silly question, they often reply with "Read the Problem Statements Carefully" or they clearly clarify and answers the question that's been asked.
My concern to this problem was in both suffix and prefix the "Equal" condition is being used. So, My concern was any array containing all the equal elements will have same AND and XOR for every indices and that clearly satisfies the question conditions. But I was getting WA. I needed [still need actually] a little clarification about that.
Lastly, sorry for being rude as today, I am totally pissed off.
"Read the Problem Statements Carefully"
if we use same elements in array then at some point we got SUFFIX_XOR less then SUFFIX_AND to avoid this just put another number at end(like 3) eg. 7 7 7 7 PREFIX XOR-> 7 0 7 0 PREFIX AND-> 7 7 7 7 0 7 0 7 <- SUFFIX XOR 7 7 7 7 <- SUFFIX AND
Thanks a lot, my friend. Highly appreciate ur explanation.
1) you are not being rude (and nor am I trying to be rude in following arguments)
2) that is indeed a silly doubt. (I am not trying to be rude, just brutally honest). The people will answer a doubt only when they feel that the doubt can genuinely not be cleared by the participant. In your case, you came up with a possible solution of all elements being equal, and it turned out to be wrong (because it gave WA). So what should your next step have been? Is it to directly raise the issue with problem setters? Here is what you should have done: Conduct a dry run of your test case. Solve for every step of what output is your solution giving and what is expected. You would have easily figured out that your solution fails for [the case which is stated in the comment below], and you need to cook a better solution. This is the normal problem solving procedure !! If the problem setter tells you the test case where your solutions fail, there is no point in even conducting the contest.
The clarification section is present to clear any ambiguities in the question. It is not there to ask why your solution is failing or why this approach isn't working or anything else. That is something which we have to do ourselves. There are countless times where I was stuck on a problem because it failed some edge case, maybe on the last test case or something, but that didn't mean I would ask it as a clarification, because that is not what 'clarification' means.
Knowing where your solution fails, finding edge cases, is a part of competitive programming and you should not seek help during contest for that.
I will give you an example of a query that actually got answered in clarification (which was asked by me in previous contest). Because I really want to help you and others who don't understand, what is expected when someone asks a doubt in the section.
In previous contest, I had a doubt in this question. The doubt was, regarding whether the the bomb can be placed at a non-integer position 'X'. It was a genuine doubt that wasn't written in the question, and it's answer being 'YES' or 'NO' could have changed the solution for a test case (actually it doesn't affect the answer either way, but whatever, I thought at that time it did, lol).
Because there was no way I could have answered this doubt myself, I got a clarification about what the question meant, even though that clarification was absolutely useless, it didn't affect what the expected solution should be. Maybe on codeforces I would have got a reply like 'read the statement carefully or sth', but the point is, ignoring that it does not affect the answer, this is the type of doubt that I think are eligible to be asked on clarification section.
Thanks avengers2405 for schooling a layman.
For this problem, here is a solution without divide and conquer. The main problem with $$$M$$$ not being prime is taking modulo inverse but since $$$M \leq 10^9$$$, $$$M$$$ can have at most $$$10$$$ distinct prime factors. So, we can deal with them separately.
In my opinion, a simpler way is to use a segtree with the modular product as its operation to query the product of each length k subarray.
Right, that's even better.
My solution don't hereneed all this . At each point just maintain the ans till k element before.
Let us define $$$last[i]$$$ = $$$\prod_{j=i}^{i+k-1} A[j]$$$ , if $$$i + k < n$$$ , else $$$last[i] = 0$$$. Define $$$Ans[i]$$$ as the sum of product of elements of all good subarrays ( i.e. having $$$\le k$$$ elements ) with left endpoint as $$$i$$$. Then $$$Ans[i] = A[i] + {A[i] (Ans[i + 1]-last[i+1]) }$$$. You can compute $$$last[i]$$$ using sparse tables. The final answer is $$$\sum_{i=0}^{n-1}Ans[i]$$$
Code
My solution for TRIPLE PRIMES is not optimal, i just brute forced all pair of primes less than $$$sqrt(n)$$$.
Test cases are weak ...
The prime number theorem strikes yet again!
after careful observation we can infer that one of the numbers would always be 2 as the N is even i.e.( 2^2 + odd + odd) = N (even), now we have two degrees of freedom only we can iterate through the prime array, and check whether the ( newN — primes[i]*primes[i]) is present their in primes array and its value should be diff from the (primes[i]*primes[i]) , in this way the TC is reduced.
In problem Cyclopian Edges, it says N <= 10^5 and M <= 10^5. But I think there are testcases where N and M exceed those values.
AC submission: https://www.codechef.com/viewsolution/1064731464. Runtime Error submission: https://www.codechef.com/viewsolution/1064731491. The only difference between those submissions is that I assert that N and M are at most 10^5.
Sorry for that, there was some last minute miscommunication between N and M which lead to this. It is now updated.
Why do problems like B exist? Does anyone even enjoy them?