NewFlow's blog

By NewFlow, history, 6 months ago, In English,

$$$a_1 = 1$$$
$$$a_2 = 5$$$
$$$a_n = a_{n-1} + n^2(a_{n-2}+1)$$$

Prove $$$a_n=(n+1)!-1$$$
P.S. Original problem

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By NewFlow, history, 13 months ago, In English,

Given 3 permutations of equal lengths n ≤ 105, let's call them A, B and C.
Find number of such i-s that there's no such j, that (Ai > Aj and Bi > Bj and Ci > Cj)

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By NewFlow, history, 18 months ago, In English,

Question is solved, please ignore this post

Why if xor sum of segment is equal to sum of segment, this condition is also satisfied for all subsegments of original segment?
I know that it's true when all bits in numbers are unique, but is it the only case when it's true, and if it is, then why?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By NewFlow, history, 18 months ago, In English,

Given an array of n positive integers called a
For each of q queries which are described with integers 1 ≤ l ≤ r ≤ n, output xor of unique values in segment(l, r), i.e. if x1, x2, x3, ..., xk is set of unique values from al, al + 1, al + 2, ..., ar - 2, ar - 1, ar, then output x1 xor x2 xor x3 xor ... xor xk

1 ≤ n, q ≤ 106
for all i, 1 ≤ ai ≤ 109

TL: 3.5 seconds
ML: 256 megabytes

How to solve it?
If it's possible, I'd like a solution which uses some of data structures listed below:
Segment Tree
Binary Rise/Lift
Trie
Merge Sort Tree

Read more »

 
 
 
 
  • Vote: I like it
  • +12
  • Vote: I do not like it

By NewFlow, history, 18 months ago, In English,

Problem was solved!

Input is consist of 1 ≤ q ≤ 2 * 104 queries every of which are described with single positive integer n not exceeding 4 * 106.
Output is to print for each query:
Where:

x⌋ =  whole part of number, i.e. max integer which's  ≤ x
φ(x) is Euler Totient Function

OK, I can previously calculate phis of all numbers from 1 to 4 * 106 and Pi for any i, 1 ≤ i ≤ 4 * 106 in O(nlogn), but what's then? I don't know how to further optimize solution, because it is TLE with O(n) complexity per query.
Please, help me!

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it