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.

# | User | Rating |
---|---|---|

1 | tourist | 3581 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Petr | 3161 |

4 | LHiC | 3158 |

5 | CongLingDanPaiSh…5 | 3116 |

6 | ko_osaga | 3115 |

7 | mnbvmar | 3111 |

8 | Um_nik | 3104 |

9 | Benq | 3098 |

10 | Swistakk | 3089 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | Errichto | 163 |

3 | rng_58 | 161 |

4 | tourist | 158 |

5 | Vovuh | 150 |

5 | Um_nik | 150 |

7 | Petr | 149 |

7 | Swistakk | 149 |

9 | PikMike | 148 |

10 | 300iq | 147 |

10 | neal | 147 |

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.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2018 20:27:33 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Please check the annoucement. The writer is "semiexp and anomymous", so I have to write so.

Announcement Link

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

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.

could you please elaborate how to formuate recursion equations here

Does this work:

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.

My solution to

D — Non-decreasingin 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 bigas previous one. Let's see a few simple examples for intuition:Input:

`10 -9`

Operations:Input array after operations:

`40 71`

Input:

`-9 10`

Operations:Input array after operations:

`11 32`

Input:

`0 0 0 0 1`

Input array after operations:

`2 4 8 16 33`

Input:

`0 0 0 0 -1`

Operations:Input array after operations:

`-64 -32 -16 -8 -4`

I get the ideia now, interesting solution

Input:

Output:

Input array after performed operations: