Hello Everyone.
I would like to invite you to participate in ACM Arabella 2019 which will be launched in GYM 29.06.2019 12:00 (Московское время)
You will be given 13 problems to solve in 5 hours, The contest difficulty is similar to Div2 Contests.
The problem-set were prepared by Hiasat , Motarack , Roze , Ayoub.Aref , Ptrq , Obada-AlAbbadi , Kilani , AbedAbuhijleh
Good luck to everyone.
Clashing with Atcoder Beginner Contest 132. Can be an hour earlier
my bad, But I think you can always do it as virtual participation
Says "Can't download contest descriptor from external storage. Are you sure you have at least one contest release?" when I try to open a question or the problemset.
yes, even i am not able to see questions.
Problem sets are not available. When those will be available?
Sorry , The contest is delayed to 1 hour later to fix the problem.
Can the masters who solved E,F,K and L please share their approach here? Or if the authors publish an editorial, that would be great too. Nice problem-set btw!
Can you tell how you solved problem B?
Looking from Kilani's view, for n=1, he wins and for n=2, he loses (irrespective of k).
Now if n<=k, then both the players can only remove 1 from the current value of n. So, the winners keep alternating. Thus, Kilani wins for odd values of n.
Else if n>k, then Kilani can chose any number from 1 to n-k and subtract it from n. We already know that if he leaves any even number less <= n for Ayoub, then the current player loses and Kilani wins. So we just check if there is any even number in the range from (n-(n-k)) to n-1. If yes then Kilani wins, else Ayoub.
Code
Thanks man :)
Our easier code was:
We can solve it using the following dynamic programming, $$$dp[i][j]$$$ where $$$i$$$ is the number of seats left and $$$j$$$ is our current location in the circle.
Think of the grid as a tree, where each cell is a node and each arrow is an edge(bottom right cell is the root).
The minimum number of times you need to start the game is the number of leafs in this tree. Let's look at each level of the tree(all nodes with same depth), choosing which nodes of this level to be leafs is independent from choosing for other levels, so we can do dp on each level, then combine results with another dp.
Edit: note that we basically want the number of different trees that represents a grid and has exactly $$$x$$$ leafs.
Assume that we start numbering from $$$0$$$ instead of $$$1$$$, then the value of cell $$$x$$$ is equal to ($$$\lfloor \frac{x}{n} \rfloor m) + (x \mod m$$$).
Which means that picking row $$$a$$$($$$0-$$$based) will give us a value of $$$am$$$ and picking column $$$b$$$(also $$$0-$$$based) will give us a value of $$$b$$$, so we can split the problem into 2 single dimensional problems.
Note that some basic number theory knowledge is needed to solve this problem.
K: Okey, I found a number of different ways to select x leaves. But it is not a number of different strategies. How to find a number of strategies?
For each level we found the number of ways to have $$$i$$$ leafs in this level for $$$0 \le i \le$$$ number of nodes in this level, so now we do another dp, $$$dp[a][b]$$$, which means the number of ways to have $$$b$$$ leafs in the tree considering the first $$$a$$$ levels. The answer will be in $$$dp[$$$total number of levels in tree$$$][x]$$$.
Let $$$z[a][i]$$$ be the number of ways to have $$$i$$$ leafs in level $$$a$$$, then $$$dp[a+1][b+i]$$$ += $$$dp[a][b] \cdot z[a+1][i]$$$.
I did it using similar dp. But then I found out that number of ways to select x leaves doesn't equal number of strategies
If the number of leafs in the tree that represents some grid is $$$x$$$, then the minimum number of times we need to play the game is equal to $$$x$$$, and since 2 trees that represents 2 grids are different if and only if the 2 grids are different, the number of different trees that represents a grid and has exactly $$$x$$$ leafs is the answer to our problem.
Ok, some strategy (1 means array down, 0 means array to the right):
Sorry, it seems my description was misleading. It's not the number of ways to choose leafs in the tree that we want, it's the number of different trees that has $$$x$$$ leafs that we want. Two different trees may have the same set of leafs as long as their structure(edges) are different.
any hint for problem D ?
Using elements of array B, we can generate all the multiples of g (the gcd of the array B). That means we can change the value of every element in A by a minimum of g. So to make the entire array A equal, we should just check the value of A[i]%g. If it is same for every i, then the answer is yes, else no.
How to solve F? I tried to use bruteforce but got wa on test 4.
Hello, I solved it by doing dp. The state is f(The chair Essa is currently at, current round) = whether Essa can win or not. With this you have only 2 transitions. Go to right length_son[current_round], or go left length_song[current_round].
Also, in order to make transitions in O(1). You need to precalculate for each round, If you are at chair with number i, and go right/left len length_song[current_round] where you end at.
Total complexity O(N*N)
Problem solved, thanks.
Awesome :D
Any hint for problem D ?
how to solve problem E？
Hello, Here I explained the first part, that is to find 2 nodes that form a diameter on a subtree (there is also the code). For the second part, we need to notice that the best place where we can join 2 subtrees is in the Radius of a Diameter (like the middle point of diameter) (it can be proven that doing this it minimizes the maximum distance for all Diameters). The problem now is that it can be an edge. But we can try the 2 adjacent nodes. So now the problem is given 2 nodes, find the center. This can be done with Binary lifting and sparse tables. Total complexity O(NlogN)
why does this solution doesn't work for 102263H - Steaks it gives me WA on test 50
Check this case: 57 83646 Answer is 10
why the answer is 10 i thought it would be 5 ? is the pans can't work parallel or what
UPD : AC Got it Now
Can anyone please say why the following solution Python code doesn't work for 102263L — Burgers. Give some failure example
Update: Not needed now, thanks