atcoder_official's blog

Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） Announcement
By atcoder_official, history, 12 months ago, In English

We will hold Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）.

We are looking forward to your participation!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

GL&HF ^^

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck for all！

→ Reply
»
12 months ago, # |
  Vote: I like it -13 Vote: I do not like it

寄

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how C???

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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];
    → Reply
»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Probability problems are putting me to sleep

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 !

      → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I will be discussing how I solved the problems here

Upd: One can find my contest screencast here

→ Reply
»
12 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Somebody explain F

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    required_potion.erase(potion) erases all occurrences of value potion

    replace it with required_potion.erase(required_potion.find(potion))

    → Reply
»
12 months ago, # |
  Vote: I like it +26 Vote: I do not like it

If G can somehow be solved with limit_denominator in Python...

→ Reply
»
12 months ago, # |
  Vote: I like it +37 Vote: I do not like it
ABC333G
→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what is 8 Kyu in my atcoder profile? I'm new on atcoder.

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is this blog downvoted

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found out a test case which shows the RE:

    Spoiler
    → Reply