Hiasat's blog

[Gym] ACM Arabella 2019
By Hiasat, history, 5 years ago, In English

Hello Everyone.

I would like to invite you to participate in ACM Arabella 2019 which will be launched in GYM Jun/29/2019 12:00 (Moscow time)

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.

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

Comments Comments (31)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Clashing with Atcoder Beginner Contest 132. Can be an hour earlier

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

    my bad, But I think you can always do it as virtual participation

    → Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem sets are not available. When those will be available?

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Sorry , The contest is delayed to 1 hour later to fix the problem.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

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

    Can you tell how you solved problem B?

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

      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

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

      Our easier code was:

      if (n % 2 == 0 and (n == k or n-1 == k)) cout << "Ayoub\n";
else cout << "Kilani\n";
      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it
    Quick solution summary for F
    Hint for K
    Hint for L
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

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

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

        Dp transition
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

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

            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.

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

              Ok, some strategy (1 means array down, 0 means array to the right):

              Strategy #1:
1 1 1
0 0 1
0 0 

Strategy #2:
1 1 1
0 1 1
0 0

In both strategies leaves are: {1,1}, {1,2}, {1,3}, {3,1}
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

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

    any hint for problem D ?

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

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F? I tried to use bruteforce but got wa on test 4.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hint for problem D ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem E？

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

    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)

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why does this solution doesn't work for 102263H - Steaks it gives me WA on test 50

ll n, k,ans=0;
	cin >> n >> k;
	n *= 2, k *= 2;
	ans = (n + k - 1) / k;
	ans *= 5*1ll;
	cout << ans;
→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply