We will hold Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）.
- Contest URL: https://atcoder.jp/contests/abc333
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231216T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, nok0, evima, m_99, leaf1415, kyopro_friends
- Tester: Nyaan, kyopro_friends
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-550-625
We are looking forward to your participation!
RP++! I didn't join in ABC332 or I can get lots of rating !! :qaq I hope I can get good grades today!
Wish my alt can reach cyan or I'll have to use my base account to participate in AGC065.
GL&HF ^^
It may be easier than Atcoder Beginner Contest 332
Good luck to all！
good luck for all！
gl everyone
You know what I like most? Positive delta!
GL&HF for everyone!
RP+=∞
The atcoder cannot enter for a while.Will it be extra time?Please don't unrated.
RP++加油！
寄
how C???
create "disk" array of increasing repunits
for (int i = 0; i < disk.size(); i++) { for (int j = 0; j <=i; j++) { for (int k = 0; k <=j; k++) { count++; if (count == n) { ans = disk[i] + disk[j] + disk[k];you can just brute force- https://atcoder.jp/contests/abc333/submissions/48582055
Probability problems are putting me to sleep
D — Erase Leaves : Pretend that the tree is rooted at vertex $$$1$$$. The root can only be removed if if becomes a leaf vertex. To become a leaf vertex, it can have atmost one children, hence we need to clear out the subtrees of all the children except the children with the largest subtree. Hence, it's just a matter of computing subtree size of each node, which can be done via basic Tree DP (or DFS).
Code
E — Takahashi Quest : First, focus on coming up with a correct algorithm instead of an optimal one. We'll write an $$$O(n^2)$$$ solution, and then optimize it to $$$O(n)$$$ using some simple observations.
Consider $$$[x_1, x_2, x_2*, x_1, x_1*]$$$. Here, $$$x*$$$ represents query of Type 2. It's clear that for each type 2 query, we should greedily pick the rightmost available candidate (because if you pick it early, you have to bear the burden of carrying it along). Hence, a simple greedy algo is: Iterate over all queries, for each type 1 queries, record the occurrence's index. For each type 2 query, pick the rightmost occurrence of that element, say $$$idx$$$. However, you must backtrack from $$$i$$$ to $$$idx$$$ to increase the count of taken elements by one. So, let's do that. At the end of the operation, $$$taken[i]$$$ contains the maximum number of potions at any time.
To optimize it to $$$O(n)$$$, notice that you can use an adjaceny list type data structure to store indices in sorted order. Also, you require a data structure that can perform range additions. Fenwick works, of course, but the catch is that the all point queries are at the end. Hence, a difference array is enough.
Code
For E I used the stack data structure to store the positions of each potion 1 to n then simply iterate. Code
Fair enough. Both the approaches are equivalent, if you consider the fact that a vector is a stack if you are only using the
push_backandpop_backmethod.You can just start from the end of the array and keep a counter array for $$$t_i =2$$$. Code
There's a much easier way. Go through the events in reverse order, and count each type of monster you encounter. If you encounter a potion of a monster you've encountered previously, take it.
No idea why it works though. Editorial doesn't help either. Submission
It works because : by taking the first potion after a monster in reverse order, you take the latest potion before the monster in the normal order. By definition, this mean you can't hold your potion for less time than you do. Hence your solution is optimal.
I agree that the editorial is weirdly worded.
I can't believe I misimplemented it during the contest when a simple vector countOfMonsterSeenByType was all that was needed !
I will be discussing how I solved the problems here
Upd: One can find my contest screencast here
I hate probability DP......
When the G is actually beginner problem, except it is a beginner problem for Project Euler enjoyers
Somebody explain F
Let $$$dp_{l, r}$$$ be the probability that the guy with l people in front of him and r people after him will be the last one. Obviously $$$dp_{0, 0} = 1$$$ and we have some relations like $$$dp_{l, r} = \frac{1}{2} dp_{l - 1, r + 1} + \frac{1}{2}dp_{l - 1, r}$$$ and for the guy in the front $$$dp_{0, r} = \frac{1}{2}dp_{r, 0}$$$. Let's calculate all the dp states in increasing order of $$$l + r$$$ then if we treat $$$dp_{k, 0}$$$ as a variable we want to solve for we can solve the system of linear equations basically and get $$$dp_{k, 0} = A dp_{k, 0} + B$$$. Knowing $$$dp_{k, 0}$$$ we can restore all other $$$dp_{l, r} | l + r = k$$$ values. The answer is $$$dp_{0, n - 1}, dp_{1, n - 2} \ldots$$$
Thank you so much for sharing your idea. I use a slightly different apporach though. I adopt dp[i][j] to denote the probability of the j-th person surviving while there are totally i persons.
For j>1, we have dp[i][j]=1/2 * dp[i-1][j-1] + 1/2 * dp[i][j-1], and for j=1, we have dp[i][1]=1/2 * dp[i][i]. I use some mathmetics to first find out dp[i][i], and then dp[i][1], and finally dp[i][j] with j > 1.
Such a beautiful solution and concise explanation. Thank you. I could not figure out how to handle cycles in DP transition. Filling the elements in increasing order of $$$l + r$$$ was key to simplifying the problem to just one variable at a time.
I can also finally appreciate the usefulness of the Atcoder Library for modular ints.
Update: (Issue from first revision Resolved): I was dividing by 2 in each DP state. Since it was a constant, I should've precomputed the modular inverse of 2, and multiplied by it everytime to save a log factor. The solution now works in less than 100ms.
Code
Update : I also made a video editorial based on this idea.
It can be solved using dp, where $$$dp[i][j]$$$ = Probability of $$$j$$$th person is the last person remaining with initially $$$i$$$ persons initially standing in the line.
So let's say there are $$$i$$$ persons, and for all $$$j<i$$$, $$$dp[j][x]$$$ are calculated, where $$$1 \le x \le j$$$.
Now, suppose we want to calculate for 3 persons, initially standing as $$$3->2->1$$$, and now we can derive some relations:
$$$dp[3][1]$$$ = $$$1/2$$$*$$$dp[3][3]$$$, because when $$$1$$$ is standing in the front, there are two possibilites, either he is removed, then the probability of him remaining at the last is $$$0$$$ or he is moved to the last, and our line becomes: $$$1->3->2$$$, thus $$$1$$$ is taking the place of $$$3$$$ in our initial configuration, thus, the relation.
$$$dp[3][2]$$$ = $$$1/2*dp[2][1] + 1/2*dp[3][1]$$$, because we know, $$$1$$$ is standing in the front, and we can either remove him or put him in the back. If we remove him, our line becomes: $$$3->2$$$, and here $$$2$$$ takes the place of $$$2->1$$$, thus $$$dp[2][1]$$$, and with $$$1/2$$$ probability, so $$$1/2*dp[2][1]$$$, or if we put him in the back our line becomes: $$$1->3->2$$$, thus taking the place of $$$1$$$ in our initial line, thus $$$1/2*dp[3][1]$$$.
And similary, $$$dp[3][3] = 1/2*dp[2][2] + 1/2*dp[3][2]$$$.
Thus, we have 3 equations and 3 variables, so we can easily solve the equations and find the values.
Generalising it, we can calculate for any $$$n$$$, in $$$O(n^2)$$$.
Video explanation of Problem A to F: link
this example is so so helpful, couldnt find this helpful explanation anywhere thanks a lot
Hey anyone , some help for problem E somehow only 25 of the testcases were passing , I basically used a multiset and iterated the the testcase in reverse order , and inserting in the multiset if the first value is 2, the required_potion there is a monster for the case i will need a potion of this type to defeat the monster.And if the first value is 1 , I will check if there is a monster needed to be defeated by this type of potion , if yes , i will mark that index , using a map.Now after iterating the loop , if size of required potion is not 0 it means , all monster cannot be defeated , so i printed -1 , otherwise move forward
Then i iterated through the loop once again , i will use another multiset potion_carried , i am maintaining the potions i will carry , so if first value is 1 , then i will check if it is marked or not , if it is marked , i will insert it into multiset potion_carried and using answer variable try storing max value of this multiset throughout.If the first value comesout to be 2 , i will erase the potion from multiset . and just for precaution , I checked here too , if for a monster if potion is not there then i will print -1.
I think this logic should work , if there is any flaw in the logic kindly let me know .
Code link : https://atcoder.jp/contests/abc333/submissions/48592453
Sorry for any bad grammatical errors.
required_potion.erase(potion) erases all occurrences of value potion
replace it with required_potion.erase(required_potion.find(potion))
oh yeah thanks bro , got it
If G can somehow be solved with
limit_denominatorin Python...Saw apiad's submission... RIP
https://atcoder.jp/contests/abc333/submissions/48596082
999 bytes with C++ XD
Why is there no SPJ for G? It's annoying to make sure $$$\dfrac pq < r$$$
Can someone tell me what is 8 Kyu in my atcoder profile? I'm new on atcoder.
You will need to solve this problem to understand.
why is this blog downvoted
why can use greedy way to solve the problem E?
We can use greedy to solve the problem in nlogn. The approach is till bit tricky. you have to start from the back. if you find a monster save it in multiset. if you find a potion then check whether there is an monster or not. If there is, you save it as 1, else if it is no then 0. After computing, if there is an monster left, answer -1, or else find the maximum K using the taken potion.
Here is the code: https://atcoder.jp/contests/abc333/submissions/48618194
Maybe i know this solution how to work, thanks to you。
I'm disappointed :(
The main Editorial has no link to Official Editorial C — Repunit Trio and no English version.
The problem is easy. Just brute force and generate. combination given below.
1 11 111 1111 11111 111111 1111111 11111111 111111111 1111111111 11111111111 111111111111
hi everyone! i was solving E, and for some reason my decision to catch RE on two tests, i will be glad if someone helps and explains to me
https://atcoder.jp/contests/abc333/submissions/48681677
I found out a test case which shows the RE:
I thought so, thanks!
I understood why I did not pass another test -> if the number of ti = 1 coincided with the value of N, then everything fell