Vasiljko's blog

By Vasiljko, history, 4 years ago, In English

I was solving 446C - DZY Loves Fibonacci Numbers today where it's needed to add geometric sequence to the segment but the ratio is always the same. So I was wondering how to solve the problem where we are given queries of type $$$L,R,A,B$$$ and we need to add geometric sequence $$$A,AB,AB^2,AB^3,... AB^{R-L}$$$ to the segment $$$[L,R]$$$? There is also a sum query for some range.

Full text and comments »

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

By Vasiljko, history, 4 years ago, In English

I've been solving 1311C - Perform the Combo and when i used memset I received TLE 73574138 but when I changed to iterative method I received AC 73575826. This is not the first time happening. What the reason behind this?

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By Vasiljko, history, 6 years ago, In English

I'm preparing for Team Selection Competition and these are some problems that I want to know how to solve. Problems are from previous competitions

Problem 1
Problem 2
Problem 3
Problem 4

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given N, М and K. All nubers are  <  = 109
Define value of matrix in row i and column j as (i + j) mod K where i <  = N and j <  = M

Given Q <  = 2 * 105 queries of form Li, Lj, Ri, Rj and you need to find sum of elements in submatrix with upper left corner (Li, Lj) and lower right corner (Ri, Rj) module 109 + 7.

Some ideas?

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given string S of N (N<=100 000) characters (each character is digit). Also given, L and R (L <= R <= 109 ). Find maximum sum that is possible to obtain cutting the string in such a way that every part has value <=R and >=L.

Input: N L R S

Test case:
8 13 997
81196054

Output: 1825

Explanation: These are all possible cuts. Last cut is best
1. 81|19|60|54
2. 81|196|054
3. 811|96|054
4. 811|960|54

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

List of integers is formed such that all integers that can be written in form 2x3y5z are sorted in increasing order. So, list look like this: 1, 2, 3, 4, 5, 6, 8, 9, ... What is n-th element (0-indexed) in list?
0 <  = n <  = 105

Input
500
Output
944784

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

What is the idea behind this problem?

Link to the problem

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given array A of N elements. We are allowed to do one operation: merge two elements A[i] and A[i+1] into A[i]+A[i+1]. We need to find sequence of exactly K elements with maximum possible GCD.

1 <= K < N <= 10^5
A[i] <= 10^6
sum of all A[i]'s <= 10^6

Input: 6 3
12 7 3 2 15 15

Output:
6
12 12 30

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given array of N elements. Find number of coprime pairs.

1 <= N <= 30000
1 <= A[i] <= 10^8

TL: 0.6s
ML: 64MB

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given convex polygon with N points (clockwise and there are no 3 collinear points). Also given M vertical line segments. Find out how many edges of polygon are intersected by at least one line segment.
Note that if line segment is going through one of the N points, then both edges are counting.

Points are represented as Xi Yi.
Line segments are represented as Ai Pi Ki which means that starting point is at (Ai,Pi) and ending point is at (Ai,Ki)

3 <= N <= 10^5
1 <= M <= 10^5
-10^7 <= Xi,Yi,Ai,Pi,Ki <= 10^7
TL: 1s
ML: 64MB

Full text and comments »

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

By Vasiljko, history, 6 years ago, In English

Given graph with N vertices and M edges. You need to find if there is a way to partition the graph in two parts in such a way that these parts are connected with at least m/2 edges. Division is integer division. If there is solution print it out, else print -1. Input: first two numbers are N and M. Next M lines are pairs of integers (X,Y) representing edge between vertices X and Y. Output: If there is no solution, print -1. Else, in the first line print size of two groups (N1,N2) , in second line print N1 numbers representing vertices in first group, same for second group.

5<= N <= 1000
1<= M <= 10000
TL : 0.2s
ML : 64MB

Input:
8 10
1 2
1 5
1 6
5 6
2 6
3 8
3 7
3 4
4 8
7 8

Output:
4 4
5 6 7 8
1 2 3 4

Your help would be appreciated.

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

By Vasiljko, history, 6 years ago, In English

Given N. We can make equality with K numbers (can be repeated) like this:

(a1+1)*(a2+1)*...(aK+1) = N*a1*a2*...*aK

Find the smallest possible value of K for which there are integers that satisfy above equality

Sample 1: Input:4 --> Output:2 --> Explanation: Integers a1 = 1 and a2 = 1 are satisfying equation.

2 < n < 1000 TL: 0.1s ML: 64MB

I thought that the answer is phi(n), but that's just a guess.

Full text and comments »

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

By Vasiljko, history, 7 years ago, In English

I was doing one problem and thought of maximum number of divisors. What I want to say is : We iterate from 1 to N (N<=10^9) and define S(i) number of divisors of number i. What is maximum S we can get? I think it is about 100 or maybe less but if someone can prove.

Full text and comments »

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

By Vasiljko, history, 7 years ago, In English

Given two arrays A and B of size N. Let's take A={4,2,8} AND B={2,7,3}. All possible absolute values are 1: |4-2|+|4-7|+|4-3|=6 ; 2: |2-2|+|2-7|+|2-3|=6 ; 3: |8-2|+|8-7|+|8-3|=12; Sum of all these is 6+6+12=24;

Constraints : 1<=N<=10^5 , |Ai|,|Bi|<=10^6, so Ai,Bi can be negative

Any help with solution with time complexity O(nlogn)?

Full text and comments »

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