Sammmmmmm's blog

By Sammmmmmm, history, 3 months ago, In English

Given a tree of n vertices, count the number of ways to choose a connected subgraph of the tree so that all the vertices in that

subgraph consists of consecutive integers when sorted. Thanks!

N <= 3e5

Full text and comments »

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

By Sammmmmmm, 4 months ago, In English

Given an array of N integers. Count the number of subarrays so that every value that appears in the subarray appears an odd number of times. I think this can be solved using XOR hashing but do not know how. Can someone help? Thanks!

N, Ai <= 1e5

Full text and comments »

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

By Sammmmmmm, history, 5 months ago, In English

Given n cards, initial the ith card from left to right has a number i written on it. X shuffled it Q times: The ith shuffle

is given as (l, c, k) meaning: X takes cards from position (not number) l to l + c — 1 out of the deck. Then insert it before

position k. After Q shuffle, print the order (number) written on each card from left to right.

N, Q <= 1e5

Ex:

5 2

3 2 2

3 3 1

Initially: (1, 2, 3, 4, 5)

After 1st queries: (1, 3, 4, 2, 5)

After 2nd queries:(4, 2, 5, 1, 3)

Can someone help? Thanks in advance!

Full text and comments »

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

By Sammmmmmm, history, 5 months ago, In English

Count the number of binary string of length N that satisfies the following M conditions:

The conditions can be 1 of 2 type

1 l r: There exists that least 1 '0' in the range [l, r]

2 l r: there exists at least 1 '1' in the range [l, r]

N <= 1e18

M <= 1e5

Thanks!

Full text and comments »

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

By Sammmmmmm, history, 6 months ago, In English

Given an array of n integers. In 1 operation you can swap 2 adjacent elements a[i] and a[i + 1] if and only if a[i] + a[i + 1] <=

k. Count the number of possible arrays that can be created using a series of operations (possibly none). Two arrays a and b are

considered different if there exists an index i so that a[i] != b[i]

N <= 1e5

K <= 1e9

Ai <= 1e9

Thanks!

Full text and comments »

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

By Sammmmmmm, history, 9 months ago, In English

Given R red balls, B blue balls, and G green balls. Count ways to arrange them so that there are exactly k pair RB (red ball is

in front of blue ball).

K <= min(R, B) R, B, G, K <= 1e6

Thanks!

Full text and comments »

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

By Sammmmmmm, history, 9 months ago, In English

Given an array of n integers and k. Count the number of permutations of the array so that the sum of each adjacent element >= k. Two permutations are different if they are different as arrays (There exists an index i so that a[i] != b[i])

N <= 2e5; K, Ai <= 1e9

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

Given an empty graph of n vertices and q queries.

Each queries is in the form of (x, y, l) which means you add edges (x + i, y + i) for 0 <= i <= l — 1

Report the number of connected components after q queries.

If I'm not mistaken, I remember there's a trick involving creating log2(n) DSU but I can't make out the details.

Can someone help? Thanks.

N <= 1e5

Q <= 1e5

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

Given an N * N matrix consisting of k ones and the rest are 0s.Count the number of connected components that contains only zeros

N <= 1e9

K <= 1e5

Thanks!

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

Hi can someone help me with this problem? Thanks

Link: https://oj.uz/problem/view/JOI18_candies

For every k where 1 <= k <= n / 2, find out what's the maximum total value you can achieved by choosing k elements from an array of n integers, and no 2 consecutive elements are chosen.

N <= 2e5;

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

Given an array of N integers. Count pairs (i, j) so that (A[i] & A[j]) = 0

N <= 1e5;

Ai <= 1e9

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

I have been doing JOI problems lately and I really liked them! Can someone suggest me some problems to do? Thanks. It could be from open contest, finals or spring camp :))

Full text and comments »

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

By Sammmmmmm, history, 15 months ago, In English

Hi I've been looking at solutions for https://oj.uz/problem/view/NOI19_feast and I saw some kind of binary search but I don't really understand the idea behind it. Can someone help? Thanks

Given an array of n integers, split it into at most k subarray that are pair-wise disjoint so that the sum of those subarray are maximized.

N, K <= 3e5

|Ai| <= 1e9

Full text and comments »

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

By Sammmmmmm, history, 16 months ago, In English

Given two arrays a[] and w[] of n integers. The cost for a subarray [l, r] is max(w[l], w[l + 1].., w[r]) * (a[l] + a[l] +.. a[r]) Divide the array into k subarray so that the total cost is minimized. Thanks

n, k <= 2500 a[i] <= 2500 with 1 <= i <= n w[i] <= 1e9 with 1 <= i <= n

You can submit here: https://www.codechef.com/INOIPRAC/problems/INOI2301?tab=statement

Full text and comments »

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

By Sammmmmmm, history, 16 months ago, In English

Given two permutations a and b of n elements.

Find the sum of inversion for each permutation that whose lexicographical value is between a and b mod = 1e9 + 7.

N <= 200000

Thanks in advance!

Full text and comments »

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