### E869120's blog

By E869120, 13 months ago, ,

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.

•
• +34
•

 » 13 months ago, # |   -17 "someone" Are you serious? This is really rude.
•  » » 13 months ago, # ^ |   +13 Please check the annoucement. The writer is "semiexp and anomymous", so I have to write so. Announcement Link
•  » » 13 months ago, # ^ |   +4
 » 13 months ago, # |   +13 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..
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 13 months ago, # ^ |   0 could you please elaborate how to formuate recursion equations here
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 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.
 » 13 months ago, # |   +8 My solution to D — Non-decreasing in case someone needs it:https://arc086.contest.atcoder.jp/submissions/1862381Here 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 71Input: -9 10 Operations: 4 2 1 2 1 1 2 1 2 Input array after operations: 11 32Input: 0 0 0 0 1Input 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
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I get the ideia now, interesting solution
•  » » » 13 months ago, # ^ |   0 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