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

Автор awoo, история, 3 года назад, По-русски

1626A - Равноудаленные буквы

Идея: BledDest

Разбор
Решение (awoo)

1626B - Небольшое сжатие

Идея: BledDest

Разбор
Решение (awoo)

1626C - Монстры и заклинания

Идея: BledDest

Разбор
Решение (awoo)

1626D - Турнир боевого искусства

Идея: BledDest

Разбор
Решение (awoo)

1626E - Черно-белое дерево

Идея: BledDest

Разбор
Решение (BledDest)

1626F - Случайный код

Идея: BledDest

Разбор
Решение (BledDest)
  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

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

it was a really cool round! it's a pity that he was unrated :(

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

For problem C, you don't have to worry about half-intervals. Here is my (badly written) code for C with segments that can be of length 0.

143049989

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

Can anybody please tell me how this code is working for problem D : 143147171.

Is this logic correct or are the test cases weak?

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

    I suppose the logic is correct. It uses a greedy approach as mentioned in the editorial. The fact that lengths can only be the power of 2 is used to reduce the time complexity of nested loops.

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

Same solution of B, but with regex (with code pattern): Perl — 143030768, (13+).

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

Can somebody explain how binary search implemented in problem D?

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

Can somebody please explain me how Binary search is applied on problem D????

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

C can be solved in $$$O(n)$$$, walking though array backwards or using stack.

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

D can be solved in $$$O(n)$$$. the submission.

The steps of the algorithm is:

  1. Calculate if we want to choose at most $$$i$$$ smallest numbers, how many numbers can we choose.

  2. Calculate if we want to choose at most $$$i$$$ largest numbers, how many numbers can we choose.

  3. Go through $$$i,j$$$ in the powers of two. $$$i$$$ means the number of the first division after inviting extra participants. $$$j$$$ means the number in the third division. Then we can know how many original participants will be in the second division. So it's easy to find the number of participants in the second division. For every $$$i,j$$$, we choose the smallest sum of three divivions, and minus it with $$$n$$$. It will be the answer.

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

    what about the case when i smallest numbers and j largest numbers are not disjoint there is some overlap ?

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

    For example: n=2 a={1,2}. Let i=1 and j=1, which means there is one person in the left segment while one person in the right segment. However there is no way to add another person to the middle segment since there is no integer between 1 and 2. In short, your code gives the right answer in a wrong way.

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

In Problem D,

I am not getting why the length of the middle segment should be power of 2 for the optimal solution.

Can someone help?

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

    I also don't understand this

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

    It's not the middle segment that should be a power of $$$2$$$. We iterate on the size of the middleweight category, which has to be a power of $$$2$$$.

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

Can anyone please explain C in further depth, I'm unable to understand

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

My Solution for problem D works in O(log(N)^4) It works as followed: Let the goal number of people for each 3 chunks be A=2^x,B=2^y,C=2^z We iterate on x=0..log(N)+1, y=0..log(N)+1, z=0..log(N)+1 We want a[1]+...+a[x] <= A, a[x+1]+...+a[y]<=B, a[y+1]+...+a[N]<=C We also want each of them as close as to their goals. We can then binary search the best x and y. The optimal solution must exists in one of these configurations.

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

I have a little problem about problem F: Why should we add $$$k\cdot n^{k-1}\cdot x\cdot L$$$ to the answer instead of $$$n^k\cdot x\cdot L$$$?

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

    The multiplier $$$k \cdot n^{k-1}$$$ is the total number of times an element is chosen over all ways to choose elements on the iterations. It can be treated as the number of occurrences of some integer $$$i$$$ in all $$$k$$$-element vectors, where each element is in $$$[1, n]$$$. It is $$$k \cdot n^{k-1}$$$ since the total number of integers in these vectors is $$$k \cdot n^k$$$, and each of $$$n$$$ integers occurs the same number of times.

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

E was really nice.

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

Can someone please explain for Problem E, I tried this test case - for the solution mentioned in editorial

input —

13
1 0 0 0 0 0 0 0 1 0 0 0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

the output is —

1 1 1 1 1 1 1 1 1 0 0 0 1 

As per my understanding, according to the problem st. shouldn't it be, only black nodes and the ones adjacent to it, i.e. 1, 13, 9, 2, 12, 8

1 1 0 0 0 0 0 1 1 0 0 1 1

Can someone explain this?

Upd: Sorry I gave wrong input.

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

    It doesn't have to be only black nodes and the ones adjacent to it. Consider an edge which links two white nodes. If the number of black nodes on the left side of this edge (in the entire tree) are 2 or more, then we can go from right to left along this edge, and similarly for left to right. The adjacent-black-node condition is only needed when the number of black nodes on one side of an edge are less than two.

    Example: If your tree is 1-2-3-4-5 and 1,2 are black nodes. Then from 5 you can select 1 and move the chip to 4. Then you can select 2 and move the chip to 3, and so on. So, whenever you have 2 or more black nodes on one side of the edge, you won't get forced back as you move along the edge in that direction.

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

Problem C is a lot simpler using stack, when we introduce a new segment, we pop the stack for the segments that were overlapping, then in the end answer is simply derived from the segments left in stack as they are all non overlapping.

Here is my code for the same 143004113

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

In Problem D, I ran 3 nested loops i, j, k for the power of 2 the first second and third segment needs to be, and checked if it was possible to divide the array into these groups, if it was possible, simple store the minimum for every iteration of i, j, k. answer in any iteration will be 2^i+2^j+2^k-n.

Here is my code for the same 143024306

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

    got the same idea as you!

    it's cool to solve it in $$$O(n + \log^4 n)$$$ instead of $$$O(n \log n)$$$

    can even solve in $$$O(n + \log^3 n)$$$ after some optimization

    143025919

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

question statement of problem B says "You are given a decimal representation of an integer x". Initially, I didn't get that the input in problem B is a string or an integer....?

firstly, I have tried my solution with an integer and got runtime error in test case 3 and later have tried with a string as input and my solution got accepted.

Moral: a decimal representation of an integer x is a String.

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

C has a tag of binary search, can someone please share/explain a binary search based solution if they have implemented it?

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

E.

Another solution and explanation of E.
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem E was not that tough, I have solved it with in out dp; Solution link

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

Problem C can be solved with $$$\mathcal O(n)$$$.

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

Hi everyone, I want to share my solution for C which is $$$O(n)$$$.

Here is my submission:144945360.

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

It’s interesting to notice that in D’s solution the while loop has the condition of “mid <= n” instead of “len1 + mid <= n”. Actually I can prove “len1 + mid / 2 <= n” will not miss cases but cannot prove the other two condition’s correctness.

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

D can be solved with dp + segment tree in $$$O(nlog^2 n)$$$.

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

Dumb rerooting solution for problem E: link .

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

In problem E if there were 3 black vertices why shouldn't the answer be 1 for all vertices