Vasiljko's blog

By Vasiljko, history, 12 months 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

Read more »

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

By Vasiljko, history, 13 months 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?

Read more »

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

By Vasiljko, history, 15 months 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

Read more »

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

By Vasiljko, history, 17 months 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

Read more »

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

By Vasiljko, history, 17 months ago, In English,

What is the idea behind this problem?

Link to the problem

Read more »

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

By Vasiljko, history, 17 months 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

Read more »

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

By Vasiljko, history, 17 months 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

Read more »

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

By Vasiljko, history, 17 months 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

Read more »

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

By Vasiljko, history, 18 months 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.

Read more »

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

By Vasiljko, history, 19 months 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.

Read more »

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

By Vasiljko, history, 23 months 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.

Read more »

 
 
 
 

By Vasiljko, history, 23 months 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)?

Read more »