YouKn0wWho's blog

Invitation to CodeChef July Cook-Off 2020
By YouKn0wWho, history, 4 years ago, In English

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!

  • Vote: I like it
  • +140
  • Vote: I do not like it

Comments Comments (55)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

I have some exciting problem ideas and I am very interested to being used them in Codechef contests, but your site isn't working:(

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YouKn0wWho (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

"6 Problems" well that's something new, I guess.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Yeah. Maybe this is the first time in CodeChefs history(not sure). The intention is to make the contest balanced and more interesting.

    → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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 ...

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Please kindly update kotlin compiler on CodeChef to at least 1.3.70 (preferably 1.3.72).

→ Reply
»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Another July Long challenge?

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

RIP ratings.

→ Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +168 Vote: I do not like it

Woah, problems were extremely nice in my opinion. Hope Codechef can keep this level in future, kudos to problemsetters!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Here is mine:

    Solution
    How I came up with a solution

    :

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was Pathetic about painting tree but instead of painting we multiply. I tried so but getting WA.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Stupid PATHETIC: I thought there is a novel solution. But it turns out to divide primes into two subsets.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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...

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nah, just random.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Root tree from some node. In node of depth $$$d$$$, write $$$(2d+2)(2d+3)$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, can you explain why it works?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Why is this valid and how did you come up with this observation, can you please explain :(

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      It is novel :)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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)
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You can actually do it with just 2 numbers.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate ?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how did you come up with the 2 numbers and what are the numbers ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Problem BOJACK. Could you explain why in the sample answer for 63 is peanutbutter? Looks like value for peanutbutter is 60

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah. It should be 60. We didn't notice it earlier. Sorry for the mistake.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I also have the same problem. If you find checker or anything else please do tell me

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        My hope ... gone!

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think I was affected by it as well (handle: nirjhor). I stress-tested my solution before submitting.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +52 Vote: I do not like it
          About the mistake
          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    min instead of max. 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Had a look at your submission.

        Check $$$n = m = 1$$$. You output is $$$0$$$, which is wrong.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Oh. God. It got accepted now, thanks so much :)

          → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +35 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check with this input:

    1

    3

    9 5 6

    The answer should be "YES" but your code returns "NO".

    → Reply
»
4 years ago, # |
  Vote: I like it +87 Vote: I do not like it

One interesting way of getting a wrong answer and spending 20ish minutes debugging the codeprimes)

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

Counter testcase
→ Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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.

→ Reply