Greetings good people of Codeforces. I hope you're having a great week.
I invite you to participate in CodeChef’s July Cook-Off, this Sunday, 19th July, from 9:30 pm to 12:00 am IST.
Participants in each division will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them.
We will also be hosting a live problem discussion sessions for Cook-Off problems with our panellist Rajarshi RestingRajarshi Basu on 20th July, 6 pm IST. 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 us on the problem setting panel are:
Setters: Shahjalal YouKn0wWho Shohag, Rahul amnesiac_dusk Dugar
Admin: Teja teja349 Vardhan Reddy
Tester: Ildar 300iq Gainullin
Editorialist: Rajarshi RestingRajarshi Basu
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! See you on the leaderboard!
I have some exciting problem ideas and I am very interested to being used them in Codechef contests, but your site isn't working:(
sorry, fixed.
Auto comment: topic has been updated by YouKn0wWho (previous revision, new revision, compare).
"6 Problems" well that's something new, I guess.
Yeah. Maybe this is the first time in CodeChefs history(not sure). The intention is to make the contest balanced and more interesting.
Could anyone have any reason regarding the timing of Codechef contest why can't they have timing similar to Codeforces contest if there is no clash ...
Please kindly update kotlin compiler on CodeChef to at least 1.3.70 (preferably 1.3.72).
Another July Long challenge?
RIP ratings.
Thanks for participating. Hope you guys liked the contest. I worked really hard as it was my first time preparing a cook-off contest.
It will be great if you guys provide me with some feedback about the contest i.e. what you liked, what you didn't like etc so that I can do my best next time.
Problem OR-thodox Distinction Was already available on Leetcode.
Extremely sorry for that. Actually we weren't aware of that problem.
Woah, problems were extremely nice in my opinion. Hope Codechef can keep this level in future, kudos to problemsetters!
That's true. the problemset was amazing.....maybe you could try having problems of these types on CF as well. In my opinion, problems on CF are more constructive than algorithmic. Constructive is fine but i would request you to increase the percentage of DS algo based problems
My Solution for BOJACK.
Print a string with length 2*d as an output.
First d characters should be all 'a'.
Last d characters should be all 'b'.
This always works.
Proof:
Number of different unique sub strings of this string = d + d + d*d.
Number of palindromic sub strings = ncr(d+1,2) + ncr(d+1,2).
Difference = d.
Here is mine:
It has innumerable solutions. Here are two of them $$$-$$$
Distinct substrings $$$= D \times D + D + D$$$
Palindromic Substrings $$$= \frac{D(D + 1)}{2} + \frac{D(D + 1)}{2}$$$
Difference $$$ = D$$$
Say we have a string $$$S$$$ with length $$$n$$$ which doesn't contain 'b'. If we append a new letter 'b' to $$$S$$$ then the difference will be increased by $$$n$$$(number of new distinct substrings( $$$ = n + 1$$$) $$$-$$$ number of new palindromic substrings ($$$= 1$$$)) . If we append it again, this time it will be increased by $$$(n - 1)$$$. So the pattern is like $$$+n, +(n-1), +(n-2), .... +2, +1$$$ (increase in difference is always decreased by $$$1$$$) after appending it $$$n$$$ times.
Initially, the length of $$$S$$$ is $$$0$$$. So if we append a character, let's say 'a', then the pattern will be similar: $$$0, -1, -2, ...., -(n-2), -(n-1)$$$ after appending it $$$n$$$ times.
So if we merge them we will have $$$aaa...aaabbb...bbb$$$ ($$$n$$$ times 'a' + $$$n$$$ times 'b') and the total difference will be $$$n$$$.
:
Was Pathetic about painting tree but instead of painting we multiply. I tried so but getting WA.
My approach to PATHETIC which gives WA, which I don't know why.
we store two values in all the nodes depending on the below condition.
first_val = product of (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71) which is less then 1018
second_val = product of all 25 prime numbers less than 100 — product of (53,59,61,67,71) such that overall product lies under 1018.
1. Start DFS from Node 1 (we can start with anyone rather than 1)
2. If the level of the current Node is less than 23:
then we store the values as first_val in the node.
3. Otherwise,
we store the second_val in the node.
can someone please tell me why this is wrong?
UPD: Found my fault.
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71 is not less than 10^18 I think
upd: It's 29 570 863 996 715 044 931 273 015 670
Stupid PATHETIC: I thought there is a novel solution. But it turns out to divide primes into two subsets.
I did centroid decomposition...
Basically if the tree is chain, you can just number the nodes in increasing order. Then for a tree generally, you can choose the centroid and color paths through the centroid like that, and solve for the subtrees.
It is a overkill, though...
Nah, just random.
I used brute force. Found all pairs distances using bfs from each vertex, and stored end-points of all paths such that their distance is a prime. (Distance is number of nodes for this question.)
Then for each prime, for each pair of endpoints, again retraced the paths using another bfs, and multiplied that prime to the smallest value node I found in the path.
Root tree from some node. In node of depth $$$d$$$, write $$$(2d+2)(2d+3)$$$.
Wow, can you explain why it works?
Consider any path of length $$$k$$$, there will be part of it of length at least $$$k/2$$$ that's going down (or up), so we multiply $$$k$$$ consecutive numbers there.
orz
Why is this valid and how did you come up with this observation, can you please explain :(
It is novel :)
For PATHETIC, I was considering all paths starting from a vertex u and using dfs kept on updating the node values, depending on the fact that the current path has product divisible by the current path length or not. I was getting WA. Can anybody suggest why this approach is wrong? Thanks in advance.
3 magic number to solve PATHETIC.
6746328388800 525737919635921 19657257924641
just place this 3 number in the nodes evenly(make sure first number in every alternate node)You can actually do it with just 2 numbers.
Can you please elaborate ?
how did you come up with the 2 numbers and what are the numbers ?
There are 25 primes , I took 6 largest primes and 7 smallest primes to group together but the other 12 were having the product larger than 2e18 so I exchanged 2 and 23 and it worked.
Problem BOJACK. Could you explain why in the sample answer for 63 is peanutbutter? Looks like value for peanutbutter is 60
Yeah. It should be 60. We didn't notice it earlier. Sorry for the mistake.
Could you also provide your checker code? I stressed my solution, but it got wa. My solution is different from the most popular. If you want look into my solution, then my nickname on codechef is argos.
I also have the same problem. If you find checker or anything else please do tell me
My hope ... gone!
The mistake in sample was due to mistake in checker to count the number of palindromic substrings. We noticed it towards the end of the contest.
Maybe we should have made an announcement in that momemt about the issue.At that time we did not know the exact issue with checker, but it was working most of them. Hence, we waited for end of contest to do analysis abt the number of affected participants and then take decision.
We are rejudging that problem and looking at the affect.I think you were affected by it. I am still waiting for the results. once they come, we will take a call on the contest. Sorry for the issue.
I think I was affected by it as well (handle: nirjhor). I stress-tested my solution before submitting.
We have checked it.
8 users from Div1 and 1 user from Div2 have been affected. We feel it is a small number for other contestants to feel its affect. So we are going ahead with rating changes in both divs. these 9 users will be contacted by the team to know if they want the contest to be made unrated for them.
Stupid Mistake
Actually I manually checked these two different functions on SPOJ and they did work. I checked the
palindromic
function on this problem and surprisingly it passed. I still don't know how.Again, sorry for the mistake. Hopefully, it won't happen again!
The MEX problem: the solution for $$$ n = m $$$ is $$$ n + 1 $$$, the solution for $$$n < m$$$ is $$$\max (m + 1, 2n + 1)$$$. Am I making a mistake somewhere as I've got a WA or there are some corner cases?
min
instead ofmax
. Right? Otherwise the limits are correct.Check your solution for the the case $$$n == m$$$. Both for a $$$n = 1$$$ and $$$n > 1$$$. I had to handle this case slightly differently than my general construction.
Yeah, I wanted to place min instead of max -- yet I still don't know what case my code fails on. Thanks for the help.
Had a look at your submission.
Check $$$n = m = 1$$$. You output is $$$0$$$, which is wrong.
Oh. God. It got accepted now, thanks so much :)
Can you please share your checker of BOJACK?How does it check if a given string is valid?
Even my brute force O(n^3) checker was wrong.
P.S. — Combined round would have been better. Separate divisions exist so that div1 users arent forced to solve easier problems not the other way round.
Can anyone tell what is wrong with following logic for "OR-thodox Distinction".
For the answer to be YES, each and every element of array must have atleast one bit set (equal to one) in its binary representation such that, this particular bit is set only and only in this particular element.
Formally, every ith element of array, the element must have some jth bit set in it, such that jth bit is not set in any other element of array.
TIA. Link to my submission : https://www.codechef.com/viewsolution/35786565
Check with this input:
1
3
9 5 6
The answer should be "YES" but your code returns "NO".
One interesting way of getting a wrong answer and spending 20ish minutes debugging the code)
Weak test cases in EVENTUAL.
https://www.codechef.com/viewsolution/35780417
He just printed NO if
n>70
. Didn't even read numbers of that particular test case. This should affect further test cases. But looks like there is no "YES" after n>70 test case.Answer is
NO\nYES
but it printsNO\nNO
Apart from the complaints and ruckus all are posting. Problems of this cook off were excellent and of nice quality. Keep up this great work for all upcoming contests 0p9o8i. Codeforces div2 and cook off yesterday were so full filling.