E869120's blog

AtCoder Regular Contest 086 & AtCoder Beginner Contest 081
By E869120, 7 years ago, In English

Hello, CodeForces!

AtCoder Beginner Contest 081 (Link) and AtCoder Regular Contest 086 (Link) will be held on December 10th, 21:00 JST.

The writer is semiexp and someone.

Let's participate and enjoy. Let's discuss after the contest.

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

»
7 years ago, # |
  Vote: I like it -17 Vote: I do not like it

"someone" Are you serious? This is really rude.

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

how to solve ARC-E problem? i have idea for 400 points , maintaining a 2D DP perhaps, but no idea how to solve for n < 2e5.. any idea?! I really loved that problem..

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

    Notice that for nodes with different depths, contribution to the answer is independent. So you may build a virtual tree for nodes with every depth and run tree-dp.

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

      could you please elaborate how to formuate recursion equations here

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

      Does this work:

      • Count the number of nodes for each height(level)
      • For each level compute the answer as: 2^(levelCount[i] — 1) * 2^(n — levelCount[i] + 1)

      Where levelCount[i] is equal to the number of nodes on the level i, the first part computes the number of ways to get an odd number(and the resulting number of marbles is always one), and the second one is the number of ways there are that the rest of the tree is formed.

      EDIT: And sum the answers for each level.

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

My solution to D — Non-decreasing in case someone needs it:

https://arc086.contest.atcoder.jp/submissions/1862381

Here is how it works:

  • Find an index of maximum absolute value;

  • If an index of maximum absolute value happens to be a positive number, then add this number twice to a first number. Adding twice is needed in case first number is negative. Then add twice first number to second, add twice second to third and so on. By performing operation twice to the following elements, each element became roughly twice as big as previous one. Let's see a few simple examples for intuition:

Input: 10 -9 Operations: 

4
1 1
1 1
1 2
1 2

Input array after operations: 40 71

Input: -9 10 Operations:

4
2 1
2 1
1 2
1 2

Input array after operations: 11 32

Input: 0 0 0 0 1

Input array after operations: 2 4 8 16 33

  • If index happens to be a negative number, then it's symmetrical case, so we start updates not from beginning of array but from the end. Let's consider this simple example:

Input: 0 0 0 0 -1 Operations:

10
5 5
5 5
5 4
5 4
4 3
4 3
3 2
3 2
2 1
2 1

Input array after operations: -64 -32 -16 -8 -4

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

    I get the ideia now, interesting solution

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

      Input:

      4
3 -200 -200 1

      Output:

      8
3 4
3 4
4 3
4 3
3 2
3 2
2 1
2 1

      Input array after performed operations:

      -4389 -2196 -998 -399
      → Reply