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

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

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

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
2 года назад
51

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

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

L_Wave

2 года назад, скрыть # |

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

GL&HF ^^

→ Ответить

jiangchen1234

2 года назад, скрыть # |

good luck for all！

→ Ответить

Northway_Swan

2 года назад, скрыть # |

The atcoder cannot enter for a while.Will it be extra time?Please don't unrated.

→ Ответить

YaKei

2 года назад, скрыть # |

-13

寄

→ Ответить

fuyuexuan

2 года назад, скрыть # |

how C???

→ Ответить

_Light

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # |

Probability problems are putting me to sleep

→ Ответить

adaptatron

2 года назад, скрыть # |

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

2 года назад, скрыть # ^ |

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

→ Ответить

adaptatron

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

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

→ Ответить

snowmanonahoe

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # |

← Rev. 2 →

I will be discussing how I solved the problems here

Upd: One can find my contest screencast here

→ Ответить

chromate00

2 года назад, скрыть # |

+11

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

→ Ответить

Misa-Misa

2 года назад, скрыть # |

Somebody explain F

→ Ответить

achvanov

2 года назад, скрыть # ^ |

+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

2 года назад, скрыть # ^ |

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

2 года назад, скрыть # ^ |

← 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

2 года назад, скрыть # ^ |

← 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 \lt 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- \gt 2- \gt 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- \gt 3- \gt 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- \gt 2$$$, and here $$$2$$$ takes the place of $$$2- \gt 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- \gt 3- \gt 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

2 года назад, скрыть # ^ |

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

→ Ответить

Conqueror903

2 года назад, скрыть # |

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.

→ Ответить