We will hold freee Programming Contest 2023（AtCoder Beginner Contest 310）.
- Contest URL: https://atcoder.jp/contests/abc310
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230715T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, MMNMM, evima, ynymxiaolongbao
- Tester: nok0, PCTprobability
- Rated range: ~ 1999
- The point values will be 100-200-300-400-450-500-550-625.
We are looking forward to your participation!
Best of luck to all contestant!
Looking forward to participating!
give your best
How to solve D ?
I used backtracking.
In many of the solutions like this https://atcoder.jp/contests/abc310/submissions/43606894
They are calling dfs by using dfs(k-1,max(top,i)) which I am not able to understand why. Whats the use of using max here ?
As I understood, you must control the number of non-empty teams. This number can stay the same or increase by one if i = top + 1 (when the new player is added to the new team).
I thought of it as coloring a graph using exactly t colors such that no two adjacent nodes are of same color. This can be solved using bitmask dp and inclusion exclusion.
Can you give any resource of your mentioned coloring graph problem solution??
shit just don't know what cases that need to be handled for D. im extremely sleepy now, gonna get another -ve delta, holy fuck!!!
In F in the first sample, why is the denominator 18? Shouldn't it be 1 * 7 * 2 * 9 = 126?
The probability of the results of the N dice satisfying the condition is 11/18.There are $$$77$$$ possible combinations that are good (can't list them all, sorry). There are $$$1 \cdot 7 \cdot 2 \cdot 9 = 126$$$ possible combinations in total. This means that the probability is $$$\displaystyle\frac{77}{126}$$$.
$$$\displaystyle\frac{77}{126} = \frac{7 \cdot 11}{7 \cdot 18} = \frac{11}{18}$$$.
The probability is shown as an irreducible fraction, because that is used in the definition of probability mod prime.
i am getting only 47 possible combinations.here is the code for that
https://ideone.com/zwityB
what did i do wrong ?
From the statement:
There is a way to choose some (possibly all) of the $$$N$$$ dice so that the sum of their results is $$$10$$$.
We don't need to choose all dice. For example $$$[1, 7, 2, 9]$$$ is good since $$$1 + 9 = 10$$$.
yeah and that is why i have started iterating from 0 indicating they are not being considered
Ah, I see, but that's still wrong. Let's look at an easier example:
There are a lot of good combinations similar to $$$[10, 11], [10, 12], \dots, [10, 50], \dots [10, 99], [10, 100]$$$, but your code will not count these separately as it only counts these in $$$[10, 0]$$$.
i missed that
thank you !!
bitmask dp is best dp
explain SOS.
What does "the doubling technique" mean in the editorial for problem G? I've only found the solution using functional graphs.
Can someone explain D?
First, go through all $$$2^n$$$ possible subsets of players, calculate if the subset is good and store the results in a separate array (using bitmasks as indicies). This can be easily done in $$$O(2^n \cdot n^2)$$$.
After that, let $$$dp[i][j]$$$ equal the number of ways to pick $$$i$$$ peaceful teams of the people in $$$j$$$ ($$$j$$$ is a bitmask). The transitions should be pretty simple. If we want to calculate $$$dp[i][j]$$$ for specific $$$i$$$ and $$$j$$$, we can iterate over a bitmask $$$k$$$ representing one of the teams. Since $$$k$$$ is a team of the people in $$$j$$$, $$$k$$$ must be a submask of $$$j$$$ (i.e. $$$j | k = j$$$). If the team represented by $$$k$$$ is good (can be checked from the array calculated in the first part), the rest of the people must form $$$i-1$$$ teams and be from the set $$$j \oplus k$$$. The number of ways to do this is $$$dp[i-1][j \oplus k]$$$ by definition.
Now, the answer will be $$$dp[t][2^n - 1]$$$, but notice that we've overcounted the answer. The statement doesn't care about the order of the teams, but our method will calculate all orders of adding the same teams as different solutions. Thus, we need to divide the answer by $$$t!$$$.
There are $$$2^n \cdot t$$$ dp states, and for each state we need to calculate up to $$$2^n$$$ transitions. Thus, the total time complexity of the dp is $$$O(4^n \cdot t)$$$ (or $$$O(3^n \cdot t)$$$ if you know how to directly iterate over submasks). This is slower than the first part, so the total complexity of the solution is $$$O(4^n \cdot t)$$$.
that's exactly what I did , can you tell me please why we can go down with O(3^n * t), because I can see O(4^n * t)
Can I see your code first?
Yes sure: my submission
What you're doing in your recursive dp call is you're iterating over all $$$2^n - 1$$$ possible non-empty bitmasks
iand checking if the current bitmask is a submask ofbitmaskwith a loop something like this:This can be replaced by
This iterases over all submasks of
bitmaskin decreasing order, and it doesn't iterate over anyithat are not submasks ofbitmask.Let $$$b = \text{bitmask}$$$.
We need to show that for any submask $$$i$$$ of $$$b$$$, the value $$$(i - 1)\ \&\ b$$$ is the largest submask of $$$b$$$ less than $$$i$$$.
Consider the integer $$$i$$$ in binary and find the last $$$1$$$-bit:
$$$i = \dots1000$$$.
Now, we know that
$$$i-1 = \dots0111$$$
and nothing inside the $$$\dots$$$ is different.
Because $$$i$$$ was a submask of $$$b$$$ and no bits higher than the lowest $$$1$$$ changed, they will also not change when performing the bitwise and $$$(i - 1)\ \&\ b$$$. The bitwise and will remove all $$$1$$$-bits from the ones at the end which are not in $$$b$$$.
This means that if $$$b$$$ looked like
$$$b = \dots1101$$$,
$$$(i - 1)\ \&\ b = \dots0101$$$.
Since we applied the bitwise and operation with $$$b$$$, the result is most definitely a submask of $$$b$$$.
Now, consider any integer $$$j$$$ strictly between $$$i$$$ and $$$(i - 1)\ \&\ b$$$. Any such integer between these must have all the same higher bits than the lowest $$$1$$$-bit in $$$i$$$ as $$$i$$$ and $$$(i - 1)\ \&\ b$$$. We know that $$$j > (i - 1)\ \&\ b$$$ and thus, $$$j$$$ must have a $$$1$$$-bit that is not in $$$(i - 1)\ \&\ b$$$. But this bit would have to be one of the last zeros that were made zeros because they weren't in $$$b$$$. This means that that integer $$$j$$$ wouldn't be a submask of $$$b$$$. Thus, there are no submasks of $$$b$$$ strictly between $$$i$$$ and $$$(i - 1)\ \&\ b$$$. $$$\square$$$
Now, we can show that the time complexity of the following code is $$$O(3^n)$$$:
Let $$$b = \text{bitmask}$$$.
First, we are iterating over all $$$b$$$ in range $$$[0, 2^n - 1]$$$.
For each $$$b$$$, we are iterating over all of $$$b$$$.
If some integer $$$b$$$ has $$$k$$$ $$$1$$$-bits, it has $$$2^k$$$ submasks. Thus, iterating over its submasks takes $$$O(2^k)$$$ time.
For each integer $$$0 \le k \le n$$$, there are exactly $$$\displaystyle\binom{n}{k}$$$ values $$$b$$$ with $$$k$$$ $$$1$$$-bits.
Thus, the total number of iterations is $$$\displaystyle\sum_{k=0}^n 2^k\binom{n}{k}$$$.
Let $$$\displaystyle f(n, k) = 2^k\binom{n}{k}$$$.
$$$f(n, k)$$$
$$$\displaystyle f(n, k) = 2^k\binom{n}{k}$$$
$$$\displaystyle f(n, k) = 2^k\left(\binom{n-1}{k-1} + \binom{n-1}{k}\right)$$$
$$$\displaystyle f(n, k) = 2^k\binom{n-1}{k-1} + 2^k\binom{n-1}{k}$$$
$$$\displaystyle f(n, k) = 2 \cdot 2^{k-1}\binom{n-1}{k-1} + 2^k\binom{n-1}{k}$$$
$$$\displaystyle f(n, k) = 2f(n-1, k-1) + f(n-1, k)$$$
We need to show that $$$\displaystyle\sum_{k=0}^n 2^k\binom{n}{k} = \sum_{k=0}^n f(n,k) = 3^n$$$. $$$(*)$$$
Consider a proof by induction:
Base case $$$n = 0$$$:
$$$\displaystyle\sum_{k=0}^0 f(0, k) = 2^0 \cdot \binom{0}{0} = 1 \cdot 1 = 3^0 = 3^n$$$
which concludes the base case.
Suppose $$$(*)$$$ is true for $$$n = m$$$. Consider the case $$$n = m+1$$$:
$$$\displaystyle\sum_{k=0}^{m+1} f(m+1,k)$$$
$$$= \displaystyle\sum_{k=0}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m+1} f(m,k)$$$
$$$= 2f(m,-1) + f(m, m+1) + \displaystyle\sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$
$$$\displaystyle = 2\cdot 2^{-1}\binom{m}{-1} + 2^{m+1}\binom{m}{m+1} + \sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$
If $$$b < 0$$$ or $$$b > a$$$, $$$\displaystyle\binom{a}{b} = 0$$$:
$$$\displaystyle = 0 + 0 + \sum_{k=1}^{m+1} 2f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$
$$$\displaystyle = 2\sum_{k=1}^{m+1} f(m,k-1) + \sum_{k=0}^{m} f(m,k)$$$
Re-indexing the first sum:
$$$\displaystyle = 2\sum_{k=0}^{m} f(m,k) + \sum_{k=0}^{m} f(m,k)$$$
$$$\displaystyle = 3\sum_{k=0}^{m} f(m,k) = 3 \cdot 3^{m} = 3^{m+1}$$$
which concludes the induction step. $$$\square$$$
Shorter calculations:
$$$\sum_{k=0}^n 2^k \binom{n}{k} = \sum_{k=0}^n 2^k \cdot 1^{n-k} \cdot \binom{n}{k} = (2+1)^n = 3^n$$$
For problem B editorial, if we are going through a list of n numbers, inserting them into a BIT, and reversing, aren't we doing a time complexity of O(n log(n) |S_i|)?
O(n) for the for loop, O(log(n) for each insertion, and O(|S|) for string reversal? Sorry for noob question as I'm a beginner.
I was solving problem C when I couldn't find any better approach then applying a DSU plus a O(N^2) to find equal elements. I am pretty sure this wasn't supposed to pass, but I got AC with 83 ms. What is the reason for this?
Submission here: Submission
Can someone tell me the approach to solve E?
first of all notice that the order of NANDS matter (Ai NANDS Ai+1) NAND Ai+2 != Ai NANDS( Ai+1 NAND Ai+2 ) -> you need to get calculate the values with the correct order.
notice that for every index i, you have i segments that starts from i notice also that the values are either 0 or 1. so we can for every i as we are going from 0 to n maintain the number of segments that are 0 and that 1 (notice that if we do this with this order, the order of the formula will be correct). say now that value of i =1 -> this will add 1 to the sum , will also add to the sum the number of current subarrays that are 0 and that are coming from i-1, this will also make all subarrays that are 1 and that are coming from i-1 to 0 (1 NAND 1==0) , and you update the number of 0 subarrays and 1 subarrays.. and you continue the loop
-> O(n) solution
is problem F a classic dp problem?
in editorial of problem D
can someone explain this part ? why we always taking a player with the minimum integer ?
upd: seems the answer is just dp.back().back() there is no division by (t!), is it somewhat related to always taking minimum ?
Although I didn't solve it before contest ended, I think I could give some explanation.
Suppose that we have divided players into different teams, and now we are going to find a way to uniquely distinguish each of them, in order to avoid counting the same pattern more than once.
For each team, we sort the number of players in an increasing order, and choose the minimum one as the "leader", and then sort all teams in an increasing order of leaders. For instance, n=3, and t=2, and we have (2) and (3,1) as two teams. Then, we sort them as (1,3),(2). We can prove that this uniquely determine exactly one way to form teams. Thus, we have the solution as follows.
First, we choose t leaders in an increasing order, which has C(n, t) ways. Then, we divide the left n-t players into t teams, and must make sure that, within each team, they can't have smaller numbers than leader and they are peaceful, which has (n-t)^t. Total complexity is C(n,t)*(n-t)^t*n.
You can check my codes if you like https://atcoder.jp/contests/abc310/submissions/43648524
Can someone provide an explanation for problem D, and not the link of the editorial as I can't understand it?