Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） Announcement

→ Обратите внимание

До соревнования
Codeforces Round 995 (Div. 3)
01:27:35
Зарегистрироваться »

→ Трансляции

Codeforces Round 995 Solution Discussion

aryanc403

До начала 03:47:34

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя atcoder_official

Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） Announcement

Автор atcoder_official, история, 12 месяцев назад, По-английски

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!

atcoder

atcoder_official
12 месяцев назад
51

Комментарии (32)

Показать архивные | Написать комментарий?

L_Wave

12 месяцев назад, # |

Wish my alt can reach cyan or I'll have to use my base account to participate in AGC065.

GL&HF ^^

→ Ответить

jiangchen1234

12 месяцев назад, # |

good luck for all！

→ Ответить

YaKei

12 месяцев назад, # |

-13

寄

→ Ответить

fuyuexuan

12 месяцев назад, # |

how C???

→ Ответить

_Light

12 месяцев назад, # ^ |

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];

→ Ответить

electric_boogaloo

12 месяцев назад, # |

Probability problems are putting me to sleep

→ Ответить

adaptatron

12 месяцев назад, # |

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

→ Ответить

omsincoconut

12 месяцев назад, # ^ |

For E I used the stack data structure to store the positions of each potion 1 to n then simply iterate. Code

→ Ответить

adaptatron

12 месяцев назад, # ^ |

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_back and pop_back method.

→ Ответить

not_ahmed_hamed

12 месяцев назад, # ^ |

You can just start from the end of the array and keep a counter array for $$$t_i =2$$$. Code

→ Ответить

snowmanonahoe

12 месяцев назад, # ^ |

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

→ Ответить

A4n0n4

12 месяцев назад, # ^ |

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 !

→ Ответить

aryanc403

12 месяцев назад, # |

← Rev. 2 →

I will be discussing how I solved the problems here

Upd: One can find my contest screencast here

→ Ответить

chromate00

12 месяцев назад, # |

+11

When the G is actually beginner problem, except it is a beginner problem for Project Euler enjoyers

→ Ответить

Misa-Misa

12 месяцев назад, # |

Somebody explain F

→ Ответить

achvanov

12 месяцев назад, # ^ |

+19

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$$$

→ Ответить

SummerSky

12 месяцев назад, # ^ |

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.

→ Ответить

adaptatron

12 месяцев назад, # ^ |

← Rev. 4 →

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.

→ Ответить

sroid_03

12 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

ustaad_bismillah

12 месяцев назад, # ^ |

this example is so so helpful, couldnt find this helpful explanation anywhere thanks a lot

→ Ответить

krishrb2517_

12 месяцев назад, # |

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.

→ Ответить