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:
- Setters: Kanhaiya notsoloud1 Mohan, Utkarsh Utkarsh.25dec Gupta, Tejas tejas10p Pandey, Ram Gopal grayhathacker Pandey,
Testers: Nishank IceKnight1093 Suresh, Jatin rivalq Garg
Statement Verifier: Kanhaiya notsoloud1 Mohan
Video Editorialists: Garvit garvitvirmani0 Virmani, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc
Text Editorialists: Nishank IceKnight1093 Suresh
Contest Admins: Utkarsh Utkarsh.25dec Gupta, Tejas tejas10p Pandey
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!
Do codechef have any plans to bring cookoffs back in (near) future ?
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.
The plan was to decrease tourist’s rating and never let him participate in a rated contest again.
don't make any post against codechef otherwise they will start downvoting you
problem Expected Sum:-
input:- 3 4 output:- 285212674 how??
i am trying to solve it on paper and i am getting (28/35). explain
wait for the contest to end :)
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}$$$.
Any hints on unique mode ?
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.
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
Surprisingly he has put a linkedin post claiming to have gotten rank 16 to which he feels that its his amazing day!!
Check out this post. https://www.linkedin.com/posts/abhishek-chauhan-10b4991b8_codechef-top20-competitiveprogramming-activity-7013922291390537728-VgYV?utm_source=share&utm_medium=member_desktop
How to solve expected sum?
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)
Here goes my solutions to these problems, with some titbits
Upd: Fixed link.
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
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:
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.
But $$$N \leq 10^9$$$...
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.
Thank you so much and how did you converted it to a O(1) solution. Can you explain that please
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.
$$$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.