Time limit for this test was 1 hour
150 points
200 points
250 points
My solution for 250 points (sorry for bad formatting)
Comments
Feel free to share your ideas/code on how to solve them.
Time limit for this test was 1 hour
Feel free to share your ideas/code on how to solve them.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
I think the second problem(200 points) can be solved by compressing the graph into a bridge tree and then using binary lifting to obtain the bitwise or of all nodes on the path from the component of u to the component of v.
How to solve the first problem?
Notice how for every position i in our process we end up either at i , either at i+1 ( this is because the values are <= 2 ).
let dp[i][true/false][true/false] be the number of subsets such that in the process we end up at position i in the first string ( if true ) and at position i+1 ( if false ), similarly for the third state in the second string.
How to transition ?
just take some cases , if we reach position i in the first string and s[i] = 2 then this will go to dp[i+1][false][k].
This way , we have an O(N) solution.
Problem A has been asked in Media.net previously.
Couldn't find a solution earlier too.
Problem A
Round 2 (same Problem)
Second question can be solved with help of DSU. As we can visit any vertex multiple times, so if the OR of whole component will be < w then the answer will be NO. Also problem statement was not correct, it should be greater than or equal to w to pass all the testcases.
The statement is very vague in its definition of what exactly path is, I assumed path to be one where we cannot visit edges twice, Which makes it a way tougher question for a coding test (The solution above using bridge tree seems to be correct).
codebuster_10 , how did you get these 21's in your matrix, for the 250 points question. I am getting the same matrix without the 21's along the diagonal.
21 stands for case when we choose consonants
Ahh I see, I completely forgot about considering consonants.
Was this an on campus test or off campus one?
Off campus
what was your dp state for 250 points problem? codebuster_10
UPD: got it dp[i][j] -> # of ways to get j vowels odd number of times with i as the string length
I think overall every task seems copied or classic. I have seen each one of them before.
task 1 copied from cc , task 3 copied from techgig final round 2019 or 2020 maybe , but doesn't matter due to being so classic , task 2 i have seen before but not sure where. its parade of copied task lol.
task 1] https://www.codechef.com/problems-old/CHEFTWOS
task 2] seems classic
task 3] can be solved with exponential generating functions easily,
it would be coeffiecient of x^N in the below polynomial
$$$ {(\frac{e^{x} - e^{-x}} { 2}})^5 * e^{21x}$$$
multiplied by N!
even though N! would be large but it also would be divided by some K! K would be very large too.