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

Автор Hiasat, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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!

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you tell how you solved problem B?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Our easier code was:

      if (n % 2 == 0 and (n == k or n-1 == k)) cout << "Ayoub\n";
      else cout << "Kilani\n";
      
  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
    Quick solution summary for F
    Hint for K
    Hint for L
    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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}
              
              • »
                »
                »
                »
                »
                »
                »
                »
                5 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    any hint for problem D ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Any hint for problem D ?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve problem E?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;
»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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