### 259A - Little Elephant and Chess

Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.

### 259B - Little Elephant and Magic Square

Since each number is less than or equal to 10^{5}, you can loop all possible *a*_{1, 1} values, the rest of cells can be calculated from this.

### 258A - Little Elephant and Bits

It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.

### 258B - Little Elephant and Elections

First of all, lets think about the problem of finding array *c*_{i} — the number of integers from 1 to *m* such, that the number of lucky digits is equal to *i*. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].

It can be solved directly using DP, but to simplify a bit you can use brute force (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 10^{9} + 7.

Consider that you have group of size *t*, each number of which should contain *l* lucky digits. That it's pretty easy to understand that the number of assignment is equal to (*c*_{l}) * (*c*_{l} - 1) * (*c*_{l} - 2) * ... * (*c*_{l} - *t* + 1).

### 258C - Little Elephant and LCM

The complexity of the possible solution is *O*(*n* * *sqrt*(*n*) * *log*(*n*)). You can see that statement *lcm*(*b*_{1}, *b*_{2}, ..., *b*_{n}) = *max*(*b*_{1}, *b*_{2}, ..., *b*_{n}) is equal to statement "All the numbers *b*_{1}, *b*_{2}, ..., *b*_{n} must divide *max*(*b*_{1}, *b*_{2}, ..., *b*_{n})". You can iterate that *max*(*b*_{1}, *b*_{2}, ..., *b*_{n}), let it be equal to *m*. Find all divisors of *m* and sort them — *p*_{1}, *p*_{2}, ..., *p*_{k}. For each *i* between 1 and *k* you can find (using simple DP) the number of numbers *a*_{j} that *p*_{i} ≤ *a*_{j} < *p*_{i + 1} (if *i* = *k* than *p*_{i + 1} = *max*(*a*_{1}, *a*_{2}, ..., *a*_{n}) + 1), denote it as *q*_{i}. Then the reuslt is equal to 1^{q1} * 2^{q2} * 3^{q3} * ... * *p*^{qp}, because for each of the *q*_{1} numbers there is 1 way to assign, for each of *q*_{2} numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some *i* such *b*_{i} = *m*. Hance you need from the last multiplier (*p*^{qp}) subtract (*p* - 1)^{qp} — all the ways that there is no number equal to *m*.

### 258D - Little Elephant and Broken Sorting

### 258E - Little Elephant and Tree

Very useful thing in this problem is ordering all vertices in DFS order (preorped). After that any subtree can be represented as a some sequence of continuous vertices. Consider that we have some fixed vertex *v*. Which vertices should be included in *c*_{v}? Obviously, if in the path from the root to *v* is some non-empty vertex (i. e. such that has at least one integer in its list) than each vertex from substree *v* should be included in *c*_{i}, but since we now working with preorder traversal of the tree, we consider that every vertex from some segment [*l*_{v}, *r*_{v}] must be included to *c*_{i}. More generally, let for each vertex keep some set of segments (*l*_{k};*r*_{k}). If on the *i*-th operation we have two vertices *a* and *b*, we add segment (*l*_{b};*r*_{b}) to vertex *a*, and (*l*_{a};*r*_{a}) to vertex *b*. Also for each vertex *i* (*i* = 1..*n*) we add segment (*l*_{i};*r*_{i}), where (*l*_{i};*r*_{i}) is a segment in our preored traversal for subtree *i*. After that, you can see that, if we unite all segments from all vertices on the path from the root to some vertex *v*, we find the result for *v*, which will be the size of the resulting set.

So now we need some data structure that would support three operations: add(l, r), subtract(l, r), count(). The first one should add 1 to all positions from *l* to *r*, inclusive. The second should subtract 1 from all positions from *l* to *r*, inclusive. The last should count the number of non-zero element. This all can be done either with segment tree or sqrt-decomposition.

Actually, the complexity of your solution to the problem C is

O(NsqrtN+Nlog^{2}N) and it can be decreased toO(Nlog^{2}N). The reason is that the total number of divisors of all numbers between 1 andN, inclusive, isO(NlogN).I'm still unclear why the total number of divisors of all numbers between 1 and N, inclusive is O(NlogN). Can you explain it a bit more? Sorry for a naive question and my bad english!

A very naive way to think of it is this:

You can calculate all divisors of all numbers from 1 to n using a sieve whose complexity is O(nlogn). Also, in each step, you calculate exactly one divisor of a number. So, there can only be O(nlogn), The sieve can be visualized as:

thanks a lot. now I got it!

div1 c can be solved in O(nlogn). See my submission

Isn't your submission O(Nlog^2N). Aren't you basically using a modified sieve with exponentiation at every step?

You are right, I CONSIDERED pow as O(1), while in fact it is O(logn). But there is a way to make it faster, because the number of factors of N is between O(sqrt(n)) and O(logN), so when we use pow(x,y), x has a upper bound and y is not greater than n, so we can calculate pow(x,y) before(in between O(nlogn) and O(n*sqrt(n)), and I think it's more close to (nlogn) ), and when we use it, it only takes O(1) time.

Seems like there's a little typo in the explanation for Div2 E/Div1 C. It should be

The result is equal to 1since^{q1}2^{q2}...k^{qk}itakes value between 1 andk, notpBtw, thanks for the editorial. My solution for Div1 C is the same but I forgot to handle the case where the subtraction yields negative value :(

what u guys r doin after 10 years : ) "

nice problems, especially problem D div 2, just in my opinion. :)

Problem Div1-B How could the first part be calculated using dp ? explain

One of the solution is like this:

Suppose

mhasndigits andd_{i}is thei-th digit ofm. Letf(i,j, 0) be the number of integers, withidigits maximum, that have exactlyjlucky digits and are less thand_{1}d_{2}...d_{i}(that is, the firstidigits ofm) and letf(i,j, 1) be the number of integers, withidigits maximum, that have exactlyjlucky digits and equald_{1}d_{2}...d_{i},i≥j. It's easy to see thatf(i,j, 1) is either 0 or 1. Let's also assume that we already have two functions,N(x) andL(x), that compute the number of non-lucky and lucky digits less thanxrespectively.Base cases:

f(1, 0, 0) =N(d_{1})f(1, 1, 0) =L(d_{1})f(1, 0, 1) = 0 ifd_{1}is a lucky digit, 1 otherwisef(1, 1, 1) = 1 ifd_{1}is a lucky digit, 0 otherwiseTransitions:

f(i,j, 1) = 1 if there are exactlyjlucky digits ind_{1},d_{2}, ...d_{i}, 0 otherwiseIf

j= 0 thenf(i,j, 0) = 8f(i- 1,j, 0) +N(d_{i})f(i- 1,j, 1)else

f(i,j, 0) = 8f(i- 1,j, 0) +N(d_{i})f(i- 1,j, 1) + 2f(i- 1,j- 1, 0) +L(d_{i})f(i- 1,j- 1, 1)Then, the number of integers between 1 and

m(inclusive) that have exactlyklucky digits isf(n,k, 0) +f(n,k, 1), minus 1 ifk= 0 since we don't want to count the number 0 in.Div2 B can be solved in O(1) even if the range of the numbers become unlimited.

x a b c y d e f z

Note that a+b+c+d+e+f+x+y+z = 3s where s is the sum of a line. But x+y+z = s, so a+b+c+d+e+f = 2s. Aka the total sum of the numbers given is 2s. Divide by 2 to get s.

Now the rest is easy: x = s-a-b, y = s-c-d, z = s-e-f.

This is correct as long as the given numbers are indeed correct (a+f = b+e = c+d). This also proves that there is only one solution.

In problem 258A, for the catchy case (all 1,such as 111111) input data set is may be wrong. Because my friend's accepted code gives equal number of one as like as input. he hasn't handle such case. My friend's handle is "zitu_cuet" (without quote). Or you can see this link... My friend's submission's link . For input "1111" his output is "1111". But codeforces compiler gives "111". You can see pretest 10 or 31. As he didn't handle such case how can these output come ???

I think his solution is right because in codeforces any uninitialized variable becomes 0 and when he makes j=0 , p is 0 and he doesn't add the first 1. I'm not exactly sure but I think this is the only reasonable explanation.

Humm... It's clear to me now.... :) this matter was not known by me.... thanks for your reply :)...

Hey , Is there not a direct way to reach the editorials of any particular contest whether new or old . After much time searching the editorials on the site , I found the way to here by a link in Recent Actions ... There should be some other way too to reach an editorial of a particular contest . Please tell .

Some of the contests have their materials linked under the Contest Materials at the bottom right of the page, like here. Administrators, contest authors and red-rated coders can add missing links.

How to solve second part of problem B using dynamic programming? How to take into account that all parties must have distinct numbers?

Consider that the party of LE has number with

clucky digits. Than there are 6 more paries left. No you have only numbers with 0, 1, ..,c- 1 lucky digits, each group is intependent. Hence the state of DP is [current number of lucky digits (gropus that we consider)][current sum of lucky digits][current number of free (such that no number is assigned yet) parties]. Let it be [d][sum][cnt]. On such state you can iterate numberk(0 ≤k≤cnt) — the number of parties that would have number with exactlydlucky digits. You should place thatknumbers amongcntthat are left. This gives you a multiplierC(cnt,k). The number of assignment is (as in the statement)c_{d}* (c_{d}- 1) * ... * (c_{d}-k+ 1). Hance you go from [d][sum][cnt] into [d-1][sum + k*d][cnt - k] with multiplierC(cnt,k) *c_{d}* (c_{d}- 1) * ... * (c_{d}-k+ 1).How to solve div1 E ???

I wonder if it is possible for you to include links to relevant code implementations of the algorithms you've described above in your editorial please?

yup it would be great if there are links to some well commented implementations!

If it's possible, report someone solution of task D(div 1), please.

I am also very interested. The problem seems to be very beautiful and hard. Even some idea will be a good thing :)

I have solution already:)

Let's support F[i][j] = probability that a[i]>a[j].

At first. F[i][j]=1, if a[i]>a[j] and 0 else.

When we need to swap a[x] and a[y] with probability= 0.5:

It's logically that for (i!=x,y): F[i][x]=F[i][y]= 0.5*F[i][x] + 0.5*F[i][y].(Because probability that on x-th position will be a[x] or a[y] will be same).

Also logically: F[x][i]=1-F[i][x], F[y][i]=1-F[i][y]. F[x][y]=F[y][x]=0.5.

Answer=sum F[i][j] for i<j.

Thank you :)

Denote

d[i][j] (i<j) as probability ofp[i] >p[j].How can we count array

dafter swapp[a] andp[b]? (a<b)Just do the following for all 0 ≤

c<n:d[c][a] =d[c][b] =d[c][a] +d[c][b],c<a;d[a][c] =d[b][c] =d[a][c] +d[b][c],b<c;d[a][c] =d[a][c] + (1 -d[c][b]),a<c<b;d[c][b] = (1 -d[a][c]) +d[c][b],a<c<b;d[a][b] = .Nice solution :)

How can we realise segment tree such , that we can count number of non-zero elements in LogN time , also we need to increase all elements by 1 on interval or decrease by 1 also in LogN time.

Let's calculate the amount of zeros: for this you can calculate minimum on the segment and the amount of this minimum, because all values (in problem E Div1) are non-negative.

haha , I got it now ,nice way :)

What if the value in the problem can be negative, and is still asking for the amount of non-zero elements, can it still be solved??

Sorry, all my solutions in previous rev. were wrong :-(

I'm only know obvious solution using sqrt-decomposition and with complexity

O(logNsqrtN) :-(Using nsqrt(n) memory(feasible only if enough memory). per-query time can be made sqrt(n). For each block store what is number of elements =i for each i(possibly using coordinate compression in first place). Then for updates which cover entire block just update offset. Else update the entire block(only zeroing out previous elements and updating new elements in sqrt(n) time). For query directly return offset result in each block.

Have you figured out a per-query log(n) solution?

Please anyone describe the proof of solution problem div2 e/div1 c . thanks in advance.

I am not able to understand editorial for DIV 1 C anyone can explain me. Thanks in advance:)

Something about the execute time of python3 with the problem C.Actually,my solution is O(Nsqrt(N)+NlogNlogN),although I use the mutithreading by python3,I just get TLE...maybe I just don't get the better algorithm with problem C...

why still have no solution of CF258D?