awoo's blog

By awoo, history, 4 months ago, translation, In English

1626A - Equidistant Letters

Idea: BledDest

Tutorial
Solution (awoo)

1626B - Minor Reduction

Idea: BledDest

Tutorial
Solution (awoo)

1626C - Monsters And Spells

Idea: BledDest

Tutorial
Solution (awoo)

1626D - Martial Arts Tournament

Idea: BledDest

Tutorial
Solution (awoo)

1626E - Black and White Tree

Idea: BledDest

Tutorial
Solution (BledDest)

1626F - A Random Code Problem

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +121
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also using two pointers can achieve %O(n)%

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please give an explanation of your solution, I couldn't exactly figure out how it works. Thanks

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is my solution in Kotlin with backward approach.

»
4 months ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did't it say x < y? there is always a number between.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I also don't understand this

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Example
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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$$$?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, thanks for the explanation!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting Tle in Problem B. How to optimize it?

143233467

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, in Kotlin I use StringBuilder instead of string concatenation to speed things up, maybe it can be the case in Java too. Second, x and ind are enough to prepare an answer, you don't have to create a new string for ans on every iteration of for-loop.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi , Can Anyone please point out what is wrong in my Approach for problem C . I have used a greedy approach while mantaining a stack that holds the index of all the monsters that i defeat by starting a spell somewhere between a[i] and a[i-1] . So if for the ith monster , lets say that it can be defeated by continuing to add 1 to the spell casted at the i-1th index until we reach the ith monster , so i directly do that , if i can defeat the current monster by starting from 1 again in between the time of the previous monster and the current , while pushing the index of the current element in the stack. So only 1 case is left where , i am not able to defeat my current monster even by adding 1 to the (i-1)th spell through the time k[i]-k[i-1] , in that case i start popping my element from the stack until i reach an index x where instead of starting my spell from 1 before x , if i had continued adding 1 from the x-1th spell , our current monster too could have been defeated . This also gives the minimum mana that we will need to defeat the current monster . I would really appreciate the help , here's my code : 143039544

»
4 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

»
4 months ago, # |
  Vote: I like it -19 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Correct Moral: read constraints carefully next time.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D seems to have weak test cases https://codeforces.com/contest/1626/submission/143296062

I tried out the same idea as of editorial but instead of precomputing left. I just looped back to get the value which should make the solution n2logn. But got AC

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this solution https://codeforces.com/contest/1626/submission/143363625 not working out for Problem C? Would love some help!

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    As I can tell, it doesn't work if there is a weak monster between two tough, because sup based on monsters next to each other. Example:

    Input:
    Expected Output:
    Your Output:

    UPD: or if there are several weak monsters before tough:

    Input:
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C can be solved in backward direction by merging the overlapping intervals in O(n).143461635

»
4 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

E.

Another solution and explanation of E.
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey all! So for problem D, the tutorial says:

"So there is a greedy idea that the second segment should be as long as possible under the constraint that it doesn't exceed the fixed value. The intuition is the following. Consider the longest possible valid segment. Now take the last element away from it. We will have to invite one more participant to the middle division. And that element will also get added to the third segment, increasing its length. So potentially, you can only increase the required number of participants to invite."

Would anyone be willing to explain this a little more? I don't quite get how the intuition works here... What if one large segment causes the third segment to not be a power of 2, but a smaller segment allows both the second and third segments to be powers of 2?

E.g. let's say segment 2 + segment 3 has to have length 12. Then if segment 2 has length 5, segment 3 must have length 7 (so you need 4 extra people), but if segment 2 has length 4, segment 3 has length 8 so you don't need extra people so that would be a better solution right?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess your example is wrong here. The middle segment should be a power of 2 and clearly 3 isn't.

    • »
      »
      »
      4 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you so much for your reply! I just have another question though, why does the middle segment's length need to be a power of 2?

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because lengths of all segments should be a power of 2 and greedily we should not use extra participants to make the second segment a power of 2.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me find the mistake in this submission 143478982 for problem D. It is giving wrong answer on test 3.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me, please. I have a problem like this problem https://codeforces.com/problemset/problem/1129/D, but i can't solve it. Can you help me?

This problem define: the specificity of a sequence is defined as the number of elements that appear exactly once in the sequence. Given a integer N and a array A. Find a subarray of A which have the specificity minimum. Among the subsequences with the same lowest specificity, find the subsequence with the longest length

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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

Here is my submission:144945360.

Spoiler