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**

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3520 |

2 | tourist | 3461 |

3 | Um_nik | 3367 |

4 | apiadu | 3351 |

5 | mnbvmar | 3332 |

6 | Benq | 3330 |

7 | LHiC | 3276 |

8 | TLE | 3271 |

9 | Radewoosh | 3251 |

10 | ecnerwala | 3241 |

# | User | Contrib. |
---|---|---|

1 | antontrygubO_o | 189 |

2 | Errichto | 188 |

3 | tourist | 180 |

4 | Radewoosh | 173 |

5 | vovuh | 166 |

6 | pikmike | 165 |

7 | ko_osaga | 162 |

8 | Um_nik | 160 |

9 | rng_58 | 155 |

10 | farmersrice | 152 |

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

Given array with *N* < = 5 * 10^{5} elements. Find number of subarrays such that every element in subarray appears even times

Given *N* < = 5000 strings. Find the number of pairs of strings such that after concatenating these strings, new string is palindrome

Given *A*, *N*, *M* . We perform this operation *N* times : *A* = (*A*+*biggestDigit*(*A*))%M . Find *A* after *N* operations. *A* < *M* < = 10^{18} and *N* < = 10^{18}

Edit: *biggestDigit*(*A*) is digit with biggest value, not most significant one

Given *N* * *N* matrix A and *Q* < = 5 * 10^{5} queries *N* < = 1000.

First query: 1 *X* *Y*, find farthest element in matrix such that its value is less than *A*[*X*][*Y*] (Manhattan distance)

Second query: 2 *X* *Y* *VAL* change element *A*[*X*][*Y*] to *VAL*

Given *N*, *М* and *K*. All nubers are < = 10^{9}

Define value of matrix in row *i* and column *j* as (*i* + *j*) *mod* *K* where *i* < = *N* and *j* < = *M*

Given *Q* < = 2 * 10^{5} 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 10^{9} + 7.

Some ideas?

Given string S of N (N<=100 000) characters (each character is digit). Also given, L and R (L <= R <= 10^{9} ). 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

List of integers is formed such that all integers that can be written in form 2^{x}3^{y}5^{z} 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* < = 10^{5}

Input

500

Output

944784

What is the idea behind this problem?

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

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

1 <= N <= 30000

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

TL: 0.6s

ML: 64MB

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

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.

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.

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)?

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/26/2020 13:07:42 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|