witua's blog

By witua, 6 years ago, translation, In English,

DIV2-A Lucky Ticket:

In this problem everything is obvious: if all digits are lucky and sum of the digits of the first half equals to the sum of the digits of the second half, then answer is YES, in other case - NO. All this can be checked by single loop through all the digits. 

DIV2-B Lucky Mask:

You can see that, in worst case, the answer will be equal to 177777. It can't be greater. So, only thing you need is to write some function F(x) which will return mask of the x. After that you need to write such kind of code: 

x = a + 1;

while (F(x) is not equal to b)

increase x;

and x will contain the answer.

DIV2-C DIV1-A Lucky Transformation:

You need to find two numbers: c47 (number of such positions i, that ai = 4 and bi = 7) and c74 (number of such positions that ai = 7 and bi = 4). After that the result will be max(c47, c74) (because you need to obtain min(c47, c74) swaps, the rest max(c47, c74) - min(c47, c74) are editings of digits).

DIV2-D DIV1-B Lucky Number 2:

Let we have some string result s. Let then delete all repititions, i. e. while we have some pair adjacent equal digits, we delete one of them. Let call formed string a root. In root there will be no adjacent equal digits, so |cnt(47) - cnt(74)| ≤ 1. So, if |a3 - a4| > 1, then answer is "-1". Now, if we would know the root, that will be used in our result, we can create result. 

You can see, that if a3 = a4, then root must be 47474747...474 or 747474...747. If a3 < a4, then root is 74747474....74. If a3 > a4, then root is 474747...47. Length of the root must be such that it fulfill a3 and a4.

Now, when you have a root, you can build result. You just need to find first occurrence of 4 in root and insert the rest of 4 from a1 right next to that digit. To add the rest of 7, you need to find last occurrence of 7 in root.

The answer does not exits if, after constructing the root, you have used more 4 than a1 or more 7 than a2.

DIV2-E DIV1-C Lucky Different: 

As you probably know, the number of lucky numbers in range [1;109] is 1022. We use this fact to solve problem. Let C[i] - number of occurrences of i-th lucky number in array a. Now we schould calculate DP with parameters DP[pos][cnt] - what is the number of subsequences that we use lucky numbers up to pos-th and our subsequence contains exactly cnt lucky number. If we are on state DP[pos][cnt] we can do two things: do not use pos-th lucky number (and do DP[pos+1][cnt] += DP[pos][cnt]) or use pos-th lucky (and do DP[pos+1][cnt+1] += DP[pos][cnt]*C[pos], because you have C[pos] of pos-th lucky number).

Now we need to find total result. To do that we iterate through the number of lucky numbers in our subsequence i. Then you need to multiple that number by C(countunlucky, k - i) (bin. coefficient), where countunlucky - number of unlucky numbers of sequence. Sum for all such i will be the total result.

DIV1-D Lucky Pair:

The main point of this problem is that number of lucky numbers in array is  ≤ 1000. Imagine that there is array of 1000 number in range [1;1000] each, and you want to find number of such pairs that there is no equal number in both segments. How to solve this problem? Let we have fixed left point of right segment, let it be i. The you should iterate through all j (i ≤ j) - right point of right segment. If you have some fixed right segment [i;j], then there is some set S of numbers that are in that right segment. So, segment [0;i - 1] will be divided in some subsegments that don't contain any number from S. For example, let S = {1, 2, 3} and segment [0;i - 1] is [2, 4, 2, 3, 6, 5, 7, 1], then there will be such subsegments (0-based numeration): [1;1], [4;6]. Of course, any subsegment of that subsegments will be good too: they dont contain any number from S, too. So, you can keep in set (or some structure like set) all good subsegments and keep number of all good subsegments in [0;i - 1]. When you iterate j from i to n - 1, you will add some numbers to S. When you add some number in S, you should add all occurrences of that number in subarray [0;i]. Notice, that when some number is already in S, you don't need to look at that numbers. So, for fixed i you should do O(n * logn) operations - any number from a[0;i - 1] will be added at most once to set

Now, we have not only lucky numbers. So, the problem is the same, but between number there are some "bad" numbers - in this case this are unlucky numbers. But, you can notice, that if we will fix only such i that a[i] is lucky and iterate j only such that a[j] is lucky then you can calculate result in the same way that in simpler problem. But that method allow you to only count such pairs that right one contains some lucky number. So you also need to count other ones. To do so you can fix some i - left point of right segment, such that a[i] is unlucky. Let F(i) equals to minimum such j (j > i) that a[i] is lucky. Then there are F(i) - i ways to expand right segment. All such right segments doesn't contain any lucky number. So any left segment will be good. And there are i * (i + 1) / 2 of such left segments (0-based). 

DIV1-E Lucky Switch:

(with help of sjtu_pigoneand)

To solve this problem you need to handle segment tree with following information:

n4: number of 4-digits in node range.
n7: number of 7-digits in node range.
n47: maximum non-decreasing subsequence in range.
n74: maximum non-increasing subsequence in range.

When we reverse digits in some node we just swap(n4, n7), swap(n47, n74). When we update node we keep n4(father) = n4(left_son) + n4(right_son), n47(father) = max(n47(left_son) + n7(right_son), n4(left_son) + n47(right_son), n4(left_son) + n7(right_son)). Then for each count query result is n47.

Read this tutorial about segment trees.
  • Vote: I like it  
  • +76
  • Vote: I do not like it  

6 years ago, # |
  Vote: I like it +17 Vote: I do not like it
DIV1-B Lucky Number 2:
in case that a3 = a4, another root that we must be consider is 747474...7. 
because in case of 1 2 1 1, 474 root cannot fulfill the string but 747 does.
  • »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    exactly, I forgot to write that in editorial )
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it
problem E can be solve using segment tree with each node maintain the following information:
n4: number of four in the range
n7: number of seven in the range
f47: maximum non-decreasing sequence length
f74: maximum non-increasing sequence length
mask: reverse mask

when reverse the digits in the node, we just need to swap(n4, n7), swap(f47, f74) 
when update the node, n4(father) = n4(leftson) + n4(rightson), 
f47[father] = max(f47[leftson] + n7[rightson], n4[leftson] + f47[rightson], n4[leftson] + n7[rightson]);

For query, ans is f47 in the root node.

Waiting solution D. 

  • »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    "n4: number of four in the range
    n7: number of seven in the range"
    Keeping both is redundant (n4 + n7 = length of segment).
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it
in problem E
n47(father) = max(n47(left_son) + n7(right_son), n4(left_son) + n47(right_son))
will work. there is no need for checking with
n4(left_son) + n7(right_son) too.

I was getting TLE , when i remove this got accepted.
22 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can someone explain Div 2E/1C solution a little more?