yash_daga's blog

Invitation to CodeChef Starters 84 (Rated till 6-stars) — 5th April
By yash_daga, history, 21 month(s) ago, In English

We invite you to participate in CodeChef’s Starters 84, this Wednesday, 5th April.

Time: 8:00 PM — 10:00 PM IST

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.

The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

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.

Hope to see you participating. Good Luck!

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

Comments Comments (20)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it

I'm Sorry for the big gap b/w SUM_OR and MEX_SEQUENCES, still I hope you'll learn a cool combinatorics trick from the editorial of MEX_SEQUENCES and lots of cool ways to modify equations to handle overflows from the last problem.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    One polite suggestion from my side would be please don't put googlable subproblems of a problem like many coders just go to oeis and copy-paste the formula/solution whereas those who solve the question by themselves get lower rank :(

    An example: SUM OR has a formula on oeis (I got to know after the contest ended I did this problem using dp with maths submission).

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your DP approach briefly?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Sure!
        Here dp defines, $$${dp[bit\space number][carry][flag] = no\space of\space ways}$$$.
        Here $$$flag$$$ was just to ensure $$$X$$$, $$$Y$$$, and $$$Z$$$ are all non-zero.
        I just tried all $$$8$$$ possible combinations for each bit till $$$61$$$.
        To fulfill the condition $$${X + Y + Z = N \space and\space X\space |\space Y\space |\space Z\space = N}$$$.
        I checked at each bit the resultant parity is the same as of $$$N$$$ or not.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          i tried implementing the same thing but this approach is giving me TLE.

          please see,

          code
          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Use fastio (if not using) and remove endl with '\n' and don't do res %= mod always (as it cost much time) better to use that only when an addition is happening. or you may try replacing some long long to int again (except N).

            → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      But wouldn't such a person have to realize that the answer only depends on the number of set bits in N? Like you I tried the DP approach and I only realized a more efficient approach is possible when my solution TLE'd, so I feel like that's a non-trivial observation and if a person realized the answer only depends on the number of set bits and guessed the pattern that's basically like solving the problem fully.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Did you mean solving a problem by just looking at the output and finding a pattern at oeis is better than solving problems logically? (No offense to anyone)

        I would be agree with you if the problem would have been Div1 $$$A$$$ or $$$B$$$ but putting at Div1 $$$D$$$ isn't good I think. We can't expect to just find the pattern for a Div1 $$$D$$$ problem.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I solve without dp . It logically makes sense that the bits which are set in n corresponding to that one of x,y, and z have their corresponding bit set to satisfy all the conditions. Let x be the number of set bits. Then, We have to find the number of Ways to distribute these x different bit positions among 3 values. Which is a combinatorics problem.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

for SUM OR problem

The equation proposed in editorial is 3^k — 3*2^k + 3

During contest, I came up with the equation 3^k — 3*( 2^k — 1)

Both the equations are same but I was getting wrong answer during the contest

Can someone clarify??( I think it may be because of modulo that both the equations aren't same)

My submission

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Change __builtin_popcount to __builtin_popcountll for obvious reasons.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

How many of you liked the new change in the contest duration? I like it a lot coz I think it'll reduce the no. of cheaters as many of them cheat in the last mins of contest.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will it change now?

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I like the shorter duration. Apart from the reduced cheaters, it's also sufficient for most participants I believe. I rarely do anything in the last hour, and it was only in place to give more time to lower divisions (3/4), and they didn't want to end the contest at different times for different divisions. I don't know why they only made this change now. But much appreciated. For a slightly harder contest, 2.5 hours duration might be better, just like they did for Starters 83 (which was rated for all).

    → Reply