### Edvard's blog

By Edvard, history, 4 years ago, translation, ,

### 622A - Infinite Sequence

Let's decrease n by one. Now let's determine the block with the n-th number. To do that let's at first subtract 1 from n, then subtract 2, then subtract 3 and so on until we got negative n. The number of subtractions will be the number of the block and the position in the block will be the last nonnegative number we will get.

С++ solution

Complexity: .

### 622B - The Time

In this problem we can simply increase a times the current time by one minute (after each increasing we should check the hours and the minutes for overflow).

Another solution is to use the next formulas as the answer: .

C++ solution 1

C++ solution 2

Complexity: O(a) or O(1).

### 622C - Not Equal on a Segment

This problem is a simplified version of the problem suggested by Mohammad Nematollahi Deemo.

This problem can be solved differently. For example you can use some data structures or sqrt-decomposition technique. But it is not required. We expected the following simple solution from the participants. Let's preprocess the following values p i — the position of the first element to the left from the i-th element such that a i ≠ a p i. Now to answer to the query we should check if a r ≠ x then we have the answer. Otherwise we should check the position p r.

C++ solution

Complexity: O(n).

### 622D - Optimal Number Permutation

This problem was suggested by Aleksa Plavsic allllekssssa.

Let's build the answer with the sum equal to zero. Let n be even. Let's place odd numbers in the first half of the array: the number 1 in the positions 1 and n, the number 3 in the positions 2 and n - 1 and so on. Similarly let's place even numbers in the second half: the number 2 in the position n + 1 and 2n - 1, the number 4 in the positions n + 2 and 2n - 2 and so on. We can place the number n in the leftover positions. We can build the answer for odd n in a similar way.

Easy to see that our construction will give zero sum.

C++ solution

Complexity: O(n).

### 622E - Ants in Leaves

This problem was suggested by Aleksa Plavsic allllekssssa.

Easy to see that the answer is equal to the answer over all sons of the root plus one. Now let's solve the problem independently for each son v of the root. Let z be the array of the depths of all leaves in the subtree of the vertex v. Let's sort z. Statement 1: it's profitable to lift the leaves in order of their appearing in z. Statement 2: denote a x — the time of appearing the x-th leaf in the vertex v, let's consider the leaves z i and z i + 1 then a z i + 1 ≥ a z i + 1. Statement 3: a z i + 1 = max(d z i + 1, a z i + 1), where d x is the depth of the x-th leaf in the subtree of the vertex v. The last statement gives us the solution for the problem: we should simply iterate over z from left to right and recalculate the array a by formula from the third statement. All statements can be easily proved and it's recommended to do by yourself to understand better the idea of the solution.

С++ solution

Complexity: O(nlogn).

### 622F - The Sum of the k-th Powers

This problem was suggested by Ivan Popovich NVAL.

Statement: the function of the sum is a polynomial of degree k + 1 over variable n. This statement can be proved by induction (to make step you should take the derivative).

Denote P x the value of the sum for n = x. We can easily calculate the values of P x for x from 0 to k + 1 in O(klogk) time. If n < k + 2 then we already have the answer. Otherwise let's use Lagrange polynomial to get the value of the sum for the given value n.

The Largange polynomial have the following form: . In our case x i = i - 1 and y i = P x i.

To calculate P(n) in a linear time we should use that x i + 1 - x i = x j + 1 - x j for all i, j < n. It's help us because with that property we can recalculate the inner product for i + 1 from the inner product for i simply by multiplying by two values and dividing by two values. So we can calculate the sum in linear time over k.

С++ solution

Complexity: O(klog MOD) ( logk appeared because we should find the inverse element in the field modulo MOD = 109 + 7).

• +90

 » 4 years ago, # | ← Rev. 2 →   0 very interesting round .. thanks a lot .. waiting for problem E
•  » » 4 years ago, # ^ |   +7 Done. F is left.
•  » » » 4 years ago, # ^ |   +3 Thanks! I've learned a lot!
 » 4 years ago, # |   -8 isn't complexity of sqrt() function O(logn)? If so, A can be done in a less time complexity
 » 4 years ago, # |   +1 Could someone help me with further optimization of my code for prob-c: not equal on segment It is giving tle on test-case 20.#includeusing namespace std;int main() {long long int n, m, l, r, x; cin >> n >> m; long long int a[n], first_on_left[n]; for(long long int i=0;i> a[i]; if(i!=0 && a[i]==a[i-1]) first_on_left[i]=first_on_left[i-1]; else if(i!=0) first_on_left[i]=i-1; else if(i==0) first_on_left[i]=-1; } for(long long int i=0;i> l >> r >> x; if(a[r-1]!=x) cout << r << endl; else if(first_on_left[r-1]>=l-1) cout << first_on_left[r-1]+1 << endl; else cout << -1 << endl; } return 0; }
•  » » 4 years ago, # ^ |   +3 Replace endl with "\n".
•  » » 4 years ago, # ^ |   0 use scanf instead of cin. I got tle with cin several times.
 » 4 years ago, # |   +1 The answer to the Infinite Sequence may be done in O(1). We may organize the sequence as: 1 (1) // That means the positions that the first one in that line is 1,2 (2) 1,2,3 (4) 1,2,3,4 (7) 1,2,3,4,5 (11) Then we would have a new sequence, which is much easier to find. 1 (1) 2 (2) 4 (3) 7 (4) 11 The number in the parenthesis are the distance between the number of the new sequence.To find the base of the number we need to solve the equation x = n(n+1)/2 + 1. Where x is the number we receive as input. We need to isolate n (get the max floor value).Then we use the n we got in the same formula, but now the result is going to be the base for the line. We only need to calculate the distance between the number we receive as input and the number we got as base.x — base + 1SOLUTION: 15944155
 » 4 years ago, # | ← Rev. 3 →   0 Can somebody help me to prove statement 3 for problem E. (SOLVED)
 » 4 years ago, # |   +2 Actually A can be done in O(1).
•  » » 4 years ago, # ^ |   0 We wanted to make the problem simple, so we gave it with the constraints for solution.
•  » » 4 years ago, # ^ |   0 as it turns out, A can be done in O(n) if you dare. My O(n) solution in C# + LINQ : 15953718
•  » » 4 years ago, # ^ |   0 plz tell me how ?
•  » » » 4 years ago, # ^ | ← Rev. 4 →   0 Let's analyse how long it takes for the sequence to enter a new cycle:C1=1 : 1C2=1 2 : (from until here)1+2=3C3=1 2 3 : (from until here)3+3=1+2+3=6Ci=1 2 ... i : SUM from 1 to i = (i+1)(i)/2So if we solve the equation (i+1)*(i)/2=n and get the floor of the positive root we can find in which cycle Ci the answer will come from.Now you need to know how many numbers were used in the cycle.(i+1)*(i)/2 is the quantity of numbers used to get past the cycle Ci.If that result is equal to n, we know that the last number of the sequence is the answer so we print i. Else, i is the cycle right before the one the answer will come from, so we print n-(i+1)(i)/2 (the quantity of numbers used since the end of the last sequence)
 » 4 years ago, # | ← Rev. 2 →   0 Why my code for porb D 15942394 TLE?
•  » » 4 years ago, # ^ |   +1 I hope for some explanations from more experienced guys, but this code doesn't get TLE in Delphi 7. 15952130
•  » » » 4 years ago, # ^ |   0 Delphi 7 = FPC ??
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Of course, not. They are two different compillers for two different languages. And your code works in D7 ~10 times faster, than in FPC.
•  » » » » » 4 years ago, # ^ |   0 thank
•  » » 4 years ago, # ^ |   0 I don't know why, but it seems that the output buffer is not fast enough in fpc.I made a little change: instead of using write() directly，save the things you want to output into a string, and finally writeln(the_string); and this way it passed all the test cases.16055326
 » 4 years ago, # | ← Rev. 2 →   0 Bonus on problem C: Add update(p, x), (ap = x ) option to query.
 » 4 years ago, # |   0 Bonus on problem E:solve the same problem for a Graph.
 » 4 years ago, # | ← Rev. 2 →   +10 We can easily calculate the values of Px for x from 0 to k + 1 in O(k) time. Actually we need O(k ln k) here due to calculating k-th power of each number.
•  » » 4 years ago, # ^ |   0 Of course you are right. Fixed.
•  » » » 14 months ago, # ^ |   0 We can also do it in $O(k)$. Using linear-time sieve we can express each $i \leq k+1$ as $i = p \cdot j$ where \$j
 » 4 years ago, # |   +1 As Far As I Know This Sequence "1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5...." Is Called "Doubly Fractal Sequence" I Appl!ed Direct Formula :) .. My Solution Was : http://ideone.com/NgIE6c
 » 4 years ago, # | ← Rev. 2 →   +8 During contest in problem C, I used segment trees to solve. Got Time Limit Exceeded on 19th test case. Only problem was cin,cout. I should have used scanf and printf.Those interested in segment tree solution of problem C :- http://codeforces.com/contest/622/submission/15960458
 » 4 years ago, # |   -9 proof of solution of prob D anyone??
 » 4 years ago, # |   0 I solved problem 622C - Not Equal on a Segment using BS + RMQ, here is my solution 15948820.
 » 4 years ago, # |   +8 Did anyone solve D without writing brute force first? if yes then how did you think until you arrived to the solution?
•  » » 4 years ago, # ^ |   +3 allllekssssa sent me that problem and I solved it without brute force)
•  » » » 4 years ago, # ^ |   0 how did you proceed??
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 The only hard part in this problem is to predict that zero sum is achievable. After that it's nearly trivial to invent needed permutation.
•  » » » 4 years ago, # ^ |   +3 I agree with you.
•  » » » » 4 years ago, # ^ |   +3 And I agree with both :)
•  » » 4 years ago, # ^ |   0 I did that.wrote a brute force first (for a given n, gives out all the possible permuations which have smallest sum).As it turns out: the minimun sum is always 0. too many possible sequences. since it's a constructive problem, we want to find a simple sequence following some patterns.Let's make some assumptions on possible sequence: there's always a required sequence, which 1 is the first one, and n is always the last one,（you can add more assumptions， since there are too many legal ones） which will lead to a very limited number of sequences. And a beautiful 1 3 5 7 ... 5 3 1 ... n may catch your eye, and now you can build one.
 » 4 years ago, # |   0 Why does this gives TLE? I think the complexity is O(n) which should satisfy the limits.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Don't mix cin/cout and scanf/printf. It's almost always bad idea. In that exact problem one definitely need to use scanf/printf due to big input.15964463 (only difference is queries input)
•  » » » 4 years ago, # ^ |   0 Thanks a lot. Can you explain a bit more why was it giving TLE just because of input functions?
•  » » » » 4 years ago, # ^ |   +3 Maximal input size in the problem C is equal to 2*10^5 * 4 * 6 = 4.8 * 10^6 characters, because there are 2*10^5 * 4 numbers and each one can be represented by 6 digits. Reading is a pretty slow operation, requiring approximately O(10) for each digit of a number, and it's particularly slow with built-in cin/cout streams. Cin/cout use various adjustments to make them more useful, e.g. there is a synchronization with scanf/printf which can sometimes come in handy, but it makes them extremely slow too. You'd want to turn it off, as it makes cin/cout much faster. Check out my codes, if you need
 » 4 years ago, # |   0 Anyone solved C with plain binary search?
•  » » 4 years ago, # ^ |   0 I wrote segment tree+binary search.
•  » » 4 years ago, # ^ |   0 I solved it using BS + DP RMQ.
•  » » 4 years ago, # ^ |   0 Pure binary search: 15971282
•  » » 4 years ago, # ^ |   0 binary search , which has a binary search inside (Complexity: O(mlog 2 n))My solution (in C# ):15936162
 » 4 years ago, # |   0 E is a very good problem :) I liked thinking the editorial solution.
 » 4 years ago, # |   0 I was at work when the contest took place so I'm just starting the problems now. I managed to solve A and B ok, I am stuck on C though. My program works but I get timelimit exceeded. Does anyone have suggestions?My Sollution
•  » » 4 years ago, # ^ |   0 _Luna has right, your solution is a Naive approach, look the test case you got TLE, 100000 numbers as input, all equal, and 100000 queries, suppose queries are all from 1 to 100000 for value 2, you will have 100000^2 operation, even that break you have inside the if will not help you. Try another approach, take into account that there are fact about the list of number that you can use to avoid sequencial search.
 » 4 years ago, # |   +5 Can anyone explain solution to problem F? I cant get the editorial.
 » 4 years ago, # |   0 P622C — Doing in O(n) but still getting TLE.import java.util.Scanner; /** * @author asif.hossain * @since 2/14/16 */ public class P622C { public static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int n = sc.nextInt(); int m = sc.nextInt(); int[] numbers = new int[n + 1]; int[] mappings = new int[n + 1]; numbers[0] = -1; mappings[0] = -1; int leftPos = 0; for (int i = 1; i <= n; i++) { numbers[i] = sc.nextInt(); if (numbers[i] != numbers[i-1]) { leftPos = i; } mappings[i] = leftPos; } for (int i = 1; i <= m; i++) { int l = sc.nextInt(); int r = sc.nextInt(); int x = sc.nextInt(); if (numbers[r] != x) { System.out.println(r); } else if (l < mappings[r]) { System.out.println(mappings[r] - 1); } else { System.out.println(-1); } } } } 
•  » » 4 years ago, # ^ |   0 Same code in C Getting TLE on 20 http://codeforces.com/contest/622/submission/16015894
•  » » 4 years ago, # ^ |   0 Ok same code and I just changed cin cout with printf and scanf and now it's accepted. Can anybody explain this ?http://codeforces.com/contest/622/submission/16016197
•  » » » 4 years ago, # ^ |   0 cout << endl flushes the output, use cout << "\n" instead.
•  » » » 4 years ago, # ^ |   0 Default setting of cin/cout is dramatically slow with such a huge input and output file.Typically, there are three ways to fix it. use scanf/printf instead add std::ios::sync_with_stdio(false); at the very beginning of your main() write fast I/O methods by your own.
 » 4 years ago, # |   +3 Could anyone tell me more about problem F? I can't understand how we use Lagrange polynomial to solve that problem. Thanks in advance!
 » 4 years ago, # |   0 How can I optimize this O(n) Haskell solution to C so that it doesn't TLE? Or is it just a limitation of the language?("build" preprocesses the values of p as described in the editorial. "solve" simply answers the queries using the array we built earlier.)
 » 4 years ago, # |   0 Can problem E be solved by dp on trees?
 » 2 years ago, # |   0 Problem C has a very elegant solution posted in the editorial, but just for the sake of learning, can someone tell me how to do it with square root decomposition ?
 » 3 months ago, # |   +22 I think it should be "Lagrange" not "Largange"