Ashishgup's blog

By Ashishgup, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Btw, why it is not on Sunday as usual?

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

    Because cf has a round.

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

    That's because the round was clashing with Technocup based Codeforces Rounds that could not be rescheduled.

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

      Next LTIME clashes with AGC(goodbye rng_58 day1).Can the date be changed?

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

The problem submission link is broken.

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

Reminder 1 — Contest starts in 2.5 hours.

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

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

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

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

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

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

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

    Sorry, there was an issue with CodeChef. It is being handled.

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

      The contest should have been extended by 5-10 minutes due to the issue.

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

Server cannot process your request. Please try again.

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

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

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

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.

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

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

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

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

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

    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?

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

      "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!

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

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

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

        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.

»
4 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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

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

    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.

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

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}$$$)

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

    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.

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

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?

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

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

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

    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.

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

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

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

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

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

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

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

      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.

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

        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)

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

    Yup, powers of two is on the right track.

    Spoiler
»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Amazing problemset! Thanks for all who created this contest.

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

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

»
4 years ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Problem sets were very good but servers were not :(

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

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.

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

    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.

»
4 years ago, # |
  Vote: I like it -30 Vote: I do not like it

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

Ez solution to SEDPASS