**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: *c*47 (number of such positions *i*, that *a*_{i} = 4 and *b*_{i} = 7) and *c*74 (number of such positions that *a*_{i} = 7 and *b*_{i} = 4). After that the result will be *max*(*c*47, *c*74) (because you need to obtain *min*(*c*47, *c*74) swaps, the rest *max*(*c*47, *c*74) - *min*(*c*47, *c*74) 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 |*a*_{3} - *a*_{4}| > 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 *a*_{3} = *a*_{4}, then root must be 47474747...474 or 747474...747. If *a*_{3} < *a*_{4}, then root is 74747474....74. If *a*_{3} > *a*_{4}, then root is 474747...47. Length of the root must be such that it fulfill *a*_{3} and *a*_{4}.

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 *a*_{1} 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 *a*_{1} or more 7 than *a*_{2}.

**DIV2-E DIV1-C Lucky Different: **

As you probably know, the number of lucky numbers in range [1;10^{9}] 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*(*count*_{unlucky}, *k* - *i*) (bin. coefficient), where *count*_{unlucky} - 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)

*count*query result is

*n*47.

DIV1-B Lucky Number 2:How do you swap(n4, n7) or swap(f47, f74) in time ?

you simply have to find segment tree nodes corresponding to your l and r in O(logn) time, then you should swap(n4, n7), swap(n47, n74) for each of those nodes in your tree and mark[node]++ (the number of operations preformed on that node) then you can shift the answer of each node you want to visit into it's children and updatie the answer for that node

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.Can someone explain Div 2E/1C solution a little more?

In div1 E last problem can u please check where i am wrong in the code,i have used the same concept but still getting wrong answer solution

The problem with your code is in lazy update, i.e marked[2*v]=true ..... and so on everytime your setting it to true, so suppose if I give you a query say

`switch 4 6`

and then again`switch 4 6`

so indices from 4 to 6 will be restored as it was and your marked array should store false as there is no update below this position but you are always setting it to true therefore after two queries of switch type your marked array will hold information that will change your segment tree when it is not needed. But that is the not the only error in your code, These are some additional problems : 1. You also need to check your lazy tree first while updating. 2. You are combining the data incorrectly you also need count of 4s and count of 7s while updating the information regarding increasing sequence. Here is my submission https://codeforces.com/contest/145/submission/59416514 (Ignore the template)DIV 1 En74: maximum non-increasing subsequence in range. Why do we need this?Okay i have got it.

DIV 1 E Can anyone please point out the mistake? Getting WA for test case 2.

My code : #here8461366

Reference code: here

THankyou very much

Never mind, i found it.

Why is 140696075 exceeding the time limit?