tejas10p's blog

Invitation to CodeChef Starters 71 — 28th December, rated for Divs 2, 3 & 4
By tejas10p, history, 22 months ago, In English

We invite you to participate in CodeChef’s Starters 71, this Wednesday, 28st December, rated for Divs 2, 3 & 4.

Time: 8 PM — 11:00 PM IST

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
  • +20
  • Vote: I do not like it

Comments Comments (21)
| Write comment?
»
22 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Do codechef have any plans to bring cookoffs back in (near) future ?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    As far as I know,cookoffs and lunchtime are handled by antontrygub and mhq. And it seems that Div1 round will not be held in very near future.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    The plan was to decrease tourist’s rating and never let him participate in a rated contest again.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    don't make any post against codechef otherwise they will start downvoting you

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem Expected Sum:-

input:- 3 4 output:- 285212674 how??

i am trying to solve it on paper and i am getting (28/35). explain

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

    wait for the contest to end :)

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

    The expected value is equal to $$$\lceil \frac{N}{2} \rceil \cdot (1 \cdot \frac{A}{N} + 0 \cdot \frac{B}{N})$$$ (with $$$N=A+B$$$), which is equal to $$$\lceil \frac{N}{2} \rceil \cdot \frac{A}{N}$$$. So you just have to calculate the modular inverse of $$$2 \cdot N$$$.

    For $$$A=3$$$ and $$$B=4$$$ the expected sum is $$$\frac{12}{7}$$$.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints on unique mode ?

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

    Think about all subarrays with each mode. First count the ones with mode 1, then 2 and so on. Obviously, only count those who have 1 maximum.

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Can someone tell me how ppl end up with same solutions? Also please someone tell if these 2 solutions will fall under plag?

I seriously want my rank 69, currently at 71 but if these 2 submissions are caught under plag then I might get rank 69. [Edit 1 : These 2 submissions have just a difference of 1 variable name change of array. He has matrix and other person has named it mat. That's all!! So I think it falls under plag since rest all things are same] Smh these weren't caught under plag.

https://www.codechef.com/viewsolution/83717025 https://www.codechef.com/viewsolution/83719372

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve expected sum?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Solve it as if chef was picking (A+B+1)/2 cards. (That's whole number division, so 5/2 = 2), but ignore the fact that the card gets removed as it doesn't matter for the final answer.

    Let K=(A+B)/2. Then the expected value is K*A/(A+B)

    → Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Here goes my solutions to these problems, with some titbits
Upd: Fixed link.

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

    Sir, you wrote a dp solution for expected sum. Can you share it please. For 3, 4 how to calculate the output? Can you share code plz

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

      Other than dp, there exists a combinatorics solution too. Suppose, you want a score of $$$x$$$ at the end of game, so you have to choose $$$x$$$ times 1 and rest times 0. In a game of $$$n$$$ moves, you have total $$$t = \frac{n + 1}{2}$$$ moves, so the probability comes out to be:

      $$$ p(x) = \Large{\frac{{{a}\choose{x}} {{b}\choose{t - x}}}{{n}\choose{t}}} $$$

      So, to calculate expected moves, you need to compute the sum $$$\sum{x \cdot p(x)}$$$, which can be done in $$$\mathcal{O}(n)$$$ time.

      AC + RTE submission, though not WA.

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

        But $$$N \leq 10^9$$$...

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

          Yeah, I know. I just shared a naive solution which @BoringDay had asked to calculate/check answer for basic examples.

          My actual solution uses a constant-time formula, but it doesn't give insight on the mathematical approach.

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

            Thank you so much and how did you converted it to a O(1) solution. Can you explain that please

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

              I just did observation. When a+b is even, then it's easy to observe that the ans is a/2. When a+b is odd, then by fixing a, I observed a pattern in fractions, and got it reduced to a simple expression.

              → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      $$$dp[O][Z]$$$ denotes the expected first player will get if we start with $$$O$$$ ones and $$$Z$$$ zeros.

      Base cases -
      $$$dp[O][0] = (O+1)/2$$$, and
      $$$dp[0][Z]=0$$$

      First player will chose $$$0$$$ with probability $$$Z/(O+Z)$$$ and $$$1$$$ with probability $$$O/(O+Z)$$$.
      Therefore, $$$dp[O][Z-1]$$$ with be the expected value the second player will get with the probability $$$Z/(O+Z)$$$, $$$dp[O-1][Z]$$$ with probability $$$O/(O+Z)$$$.

      We also know that since the sum of the expected values of both players is $$$O$$$. Hence,
      $$$dp[O][Z]=O-dp[O][Z-1]*Z/(O+Z)-dp[O-1][Z]*O/(O+Z)$$$

      To get these values as fractions, I have used fractions lib in python
      Overall, it's an $$$O(O*Z)$$$ solution, I have used it to print values and guess the formula.

      → Reply