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

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

We will hold AtCoder Beginner Contest 133.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

Thanks for organizing!

I hope this will be my last (rated) ABC. :)

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

How to solve F?

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

How to solve E?

I solved F with sqrt-decomposition but didn't find any ideas in E

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

How to solve Problem D??

  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +14 Проголосовать: не нравится

    It was a system of linear equation. We had equations in the format. x1+x2=a1 x2 +x3=a2 . . . xn + x1=an But if you add and subtract first n-1 terms alternately. You will always get x1-xn = alternate sum of n-1 terms. Using this and last equation we can get x1 and now x2 and x3 and so on till xn can be ascertained

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +6 Проголосовать: не нравится

    Let's denote the water in dams from 1 to $$$n$$$ as $$$x_1,x_2...x_n$$$ and the water on each mountain as $$$y_1,y_2...y_n$$$.Then the equations read as $$$x_1=(y_1+y_2)/2$$$, $$$x_2=(y_2+y_3)/2$$$, . . . $$$x_n=(y_n+y_1)/2$$$ Now see that $$$x_1-x_2+x_3-x_4+...x_n=y_1$$$ From $$$y_1$$$ we can successively find $$$y_2,y_3$$$ so on by substituting in the original equations.

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

Two things.

  1. Since in the last few ABCs some people have volunteered for editorials it would be nice if you can add the link of such editorials in the announcement.

  2. Was E a case of coincidence?

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

I got C wrong, Test case 16, stride_zero_01. I dont get it. Can somebody tell me what is wrong? Thanks

result

  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится
    2 2020
    

    Your answer is 2, but the correct answer should be 0.

    I guess that you can't just swap l and r after l %= 2019 and r %= 2019.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    Swapping l and r if l > r is incorrect. 6 2024 is a countercase: your solution prints 30; the correct answer is 0.

    Adding 2019 to r in this case should fix the error.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    Modulos is circular. After taking modulo of l and r with 2019, if r > l then also answer can be zero. For ex. lets take l = 2 and r = 29 and taking mod with 5 , then after taking modulo with 5 , r = 4 and l = 2 , but here answer will be 0 as r became 4 after 3 or 4 round of modulo circle.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +2 Проголосовать: не нравится

    Your code gives 2 as output for l=1 and r=2023, ans should be 0(i=1,j=2019) The problem is

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

    I have a simple solution. If the distance between l and r is greater than 2019 then it will certainly contain a factor of 2019 and hence the answer will be zero. Otherwise we can calculate by brute force.

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

How to solve Problem F??

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

Can some explain F in simple words i know about sqrt decomposition but was unable to come up with the solution

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

Can anyone explain the logic behind E.

  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 5  
    Проголосовать: нравится +5 Проголосовать: не нравится

    I will try to phase it so that everyone can understand. We will use multiplication principle of counting. Step number one consider any node(preferably 1) as root. We can color it in k ways. Now if I consider its children they cannot be colored in the same color as its parent(as a matter of fact no child can be colored with the same color as its parent). Now for any node, if it has sibling(same parent), it will have a distance of 2 from its sibling. So if a parent can be colored in $$$m$$$ ways, its first child can be colored in at least $$$m - 1$$$ ways(I will come to why more), second child at least $$$(m - 2)$$$, third $$$(m - 3)$$$ ways and so on. If you consider a set of nodes with same parent, the nodes among themselves cannot be colored with same color because they have a distance of 2 within them but their children, will have distance 3 from the other sibling hence, will be independent. To understand, this point consider following connections:

    1 2

    1 3

    2 4

    Here 2 and 3 children of 1 cannot have same color but 3 can have same color as 4 which is 2's child. So how to consider this in multiplication principle? Simple when you call dfs on unvisited children keep track of how many new nodes you found, if you found $$$c$$$ new nodes, then if you call the dfs on the $$$(c + 1)^{th}$$$ new node, you send that information onto it as a function parameter in a variable $$$siblingExplored$$$, so that when you call the child of the node it can get the correct multiplication factor. Let's run our example on an example. n = 5, k = 4 edges: 1 2

    1 3

    3 4

    4 5

    1 can be colored in 4 ways.

    2 can be colored in remaining 3 ways.

    3 can be colored in 2 ways(different from 1 and 2)

    now when we explored 3 we said can be colored in 2 ways, that doesn't mean 4 will be colored in only 1 way, but since we explored 1 child node of parent node 1, we went onto 3, we noted that 2 affects one but we sent that information(of having explored 1 sibling before) onto 3, so the multiplication factor of 4 remained 2 because 2 no longer affects it. And for nodes with height greater than 2 we will not reduce the multiplication factor by 1. Why because even though the number of possible colors are decreasing by 1 but at the same time, the dependecy on parent 3 levels up is also vanishing.

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

can anyone solve problem B without brute force or use any nice property. Thanks...

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

Official editorials are available here