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

Автор Ashishgup, 3 года назад, По-английски

We invite you to participate in CodeChef’s December Cook-Off, this Monday, 21st December, from 9:30 PM to 12:00 AM IST.
Note the unusual time.

You will be given a total of 9 problems (7 in Div2, 7 in Div1) to solve in a duration of 2.5 hours.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes: The top 10 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube Channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

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

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

Btw, why it is not on Sunday as usual?

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

The problem submission link is broken.

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

Reminder 1 — Contest starts in 2.5 hours.

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

Is it a first time cookoff will contain 7 problems in each division? (Now, it seems like codeforces :p)

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

reminder : Just 6 min left.
Hope my first Div1 contest will be good .

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

Is the server down for anyone else? I'm not able to submit solutions.

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

Server cannot process your request. Please try again.

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

You didn't mention rippling is hiring through this contest too.

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

We faced some issues with our servers, and as a compromise, we have taken down most of the IDE service. So you will not be able to use https://www.codechef.com/ide properly for now. Apologies for the issue.

The contest is rated.

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

SEDPASS problem was written very poorly. It took me forever to realize that S was the whole string.

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

    Very true, I literally spent half an hour wondering how is "a" a bad substring and then saw the announcement :(.

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

    Let's see:

    • Literally first sentence in the statement: "managed to obtain a string S"
    • Literally last sentence in the statement: "Help Sed find the number of good substrings in the string S."
    • Input: "The first and only line of each test case contains a single string S."
    • Constraints: talks about S.
    • Also somewhere in the statement: "the original string S"

    What else would S be?

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

      "A substring of S is good if it is possible to choose a lowercase English letter C such that the following process succeeds:"

      I missed the "of" in this sentence. :(

      Anyways the problem was nice!

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

      IMHO, the problem statement could have been worded better. There was not that much need of introducing the process success aspect. The problem needs to be studied much carefully to properly understand everything. Probably this much amount of deep reading is not warranted for the problems of easier difficulty level.

      May be the same thing could have been written like this.

      A substring r is considered good if you can convert r into a string R (by replacing each of the '?'s in r by some letter from 'a' to 'z', note that all occurrences of '?' must be replaced by the same letter) such that the parity of each letter from 'a' to 'z' in the original string S ('?' won't be accounted for parity calculation) should be same as that in the string $$$R$$$.

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

        More structured instead of one long sentence, but sure. That's further away from the original statement with its "if we can do the following" and "such that the third condition of the procedure holds", I had enough with 8 fairly long problems (actually 9 at the end) to go into such redesigns.

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

I had such a hard time in understanding the question SEDPASS. May be I should improve my English language skills :(

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

    ahh i agree statements were huge :. also the definition of substring mid problem statement was a bad idea. I think putting it at the bottom would have been better.

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

Cool contest again, thanks to setters and admins! SWEETRQ is especially cool, but, maybe, SDSTRING is too easy to be in Div1 contest.

SWEETRQ: let's count number of triples of cells $$$(c, c_1, c_2)$$$ such that $$$c, c_1$$$ are in the same row, $$$c, c_2$$$ are in the same column, and the number in $$$c$$$ is larger than numbers in both $$$c_1$$$ and $$$c_2$$$. Then sweet rectangle contains $$$2$$$ such triples and non-sweet — exactly $$$1$$$, so it's enough to count number of such triples, which is just sum over all cells $$$(x, y)$$$ of

(how many numbers in row $$$x$$$ are smaller than $$$a_{x, y}$$$)$$$\times$$$(how many numbers in column $$$y$$$ are smaller than $$$a_{x, y}$$$)

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

    Increasing difficulty of the first problem may not be a good idea. Many people will just leave the contest if you raise its difficulty. Solving first problem quickly commits people to participate in the contest, otherwise if it starts taking more time, the propensity of people leaving the contest rises.

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

What's the approach for d1D (Baskets)? I tried experimenting with capacities being powers of 2, but that didn't pass (or I might have implemented it wrong). Am I on the right track?

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

    Am I on the right track? Yes, all capacities except one are powers of 2 (in my solution).

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

    Yep, I think you're on the right track as I also did powers of $$$2$$$. The idea is you fill in a bucket of size $$$2^k$$$ until there are $$$2^{k-1}$$$ fruits, and then keep filling the bucket of size $$$2^k$$$ one fruit at a time while using the rest of your three fruits to fill up $$$2^{k+1}$$$ until the bucket of size $$$2^{k+1}$$$ reaches a fruit count of $$$2^k$$$, which must happen before the bucket of size $$$2^k$$$ gets full. Then do the same thing for the bucket of size $$$2^{k+1}$$$ and so on.

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

      Oh ok, I was trying something similar to that. Guess my implementation was off somewhere. Thanks!

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

    Maybe you forgot that sizes of baskets must be less or equal than $$$n$$$?

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

      Yes, I did that mistake and realized it after the contest.

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

      Oh my god, that was it. I printed 2^x from x=1 to x=16 and forgot that it had to be <=n. I wish they told you if your samples passed or failed, that would have probably made me realize.

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

        I've started writing a lot of asserts on my output to ensure that they satisfy whatever constraints — helps you catch many mistakes locally (also, you get runtime error instead of wrong answer)

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

    Yup, powers of two is on the right track.

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

Amazing problemset! Thanks for all who created this contest.

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

Video editorials for the first 8 problems have been uploaded here. The last video editorial will be uploaded over the next day or two.

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

Problem sets were very good but servers were not :(

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

For "BASKETS", only 3 fruits per day is enough!

Just wondering, if allowing 4 helps in any way. At least I couldn't think of a simpler solution using 4 fruits.

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

    simpler solution using 4 fruits
    Thats the reason they allowed 4 fruits and 1000 baskets. Many times they fake constraints instead of making them tight so as to avoid giving out information.

    Utkarsh and Ashishgup did same in D. Circle Game as well. They could have very easily made T<=1e5 and d<=1e18 in D. Circle Game.

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

It's extremely easy to solve SEDPASS if we just think about one word: Divide and Conquer.

Ez solution to SEDPASS