Блог пользователя YouKn0wWho

Автор YouKn0wWho, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +140
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Another July Long challenge?

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

RIP ratings.

»
4 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +168 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Here is mine:

    Solution
    How I came up with a solution

    :

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Nah, just random.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +61 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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)
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        My hope ... gone!

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +35 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +52 Проголосовать: не нравится
          About the mistake
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        Had a look at your submission.

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +35 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Check with this input:

    1

    3

    9 5 6

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

»
4 года назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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
»
4 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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.