Please read the new rule regarding the restriction on the use of AI tools. ×

desperateboy12344's blog

By desperateboy12344, history, 3 weeks ago, In English

Guys I need your help with this weird graph problem. Given a graph N nodes and M undirected edges (N,M <= 10^5). For a connected component (A connected component is a where there's always a path between any two nodes in this component, such that the path only uses nodes in this component)

Define its value : size(C) * min_degree(C).

size(C) is the size of the connected component

min_degree(C) is the minimum degree of all of the nodes in this component. (Only nodes in this component are counted towards degree)

Find the max value over all of the components.

Example :

N = 8,M = 10 1 2

1 3

1 4

2 3

2 4

3 4

1 5

2 6

3 7

4 8

. Maximum value is 12, since we choose (1,2,3,4), minimum degree is 3, size is 4

Sorry for my broken english guys. I need you help!!!!. And thank you in advance for any help!!!!

Full text and comments »

By desperateboy12344, history, 4 weeks ago, In English

Hi guys, as the title stated, I really need your help with this problem

You have a set. Initially the set is empty. Given Q queries (Q <= 10^5) , there are two types of queries:

1 s : s is a string, add s to the set. If the set already contains s, do nothing

2 S : For all string k that belong to the set, calculate the sum of D(k) * length(k), D(k) is the number of occurrences of k in S as a substring (example, aa is a substring of aabc, ac is not a substring of aabc) and length(k) is length of k

It is guaranteed that the sum of length of these strings don't exceed 10^5

Example :

Q = 5

1 aa

2 aa

1 aa

1 ab

2 ababaa

-> output : 2 , 6

Note: After the first query, the set is {aa}, hence the answer for the second query is 2

After the fourth query, the set is {aa,ab} -> ababaa = 6 because ab appears twice, aa appear once : 2*2 + 2*1 = 6

Full text and comments »

By desperateboy12344, history, 2 months ago, In English

As my title stated, I really need help with understanding D (https://mirror.codeforces.com/contest/2002). (Sorry, I'm really dumb :<<<). So the statement is like this (D1): Given a permutation with some persistent swap queries and a dfs algorithm, check if the permutation after each swap can form a dfs order of some perfect binary tree. I really think that as long as the permutation starts with 1, we can always recreate a perfect binary tree from the permutation. Because like if we assign a pointer p = 0, when we traverse on a binary tree, when we enter a node u, we can just assign p = p + 1, and then assign a[u] = P[p] (P is the original permutation), hence it always exists (Did I misread the statement??). Help me guys I'm really dumb :<<<

Full text and comments »

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

By desperateboy12344, history, 10 months ago, In English

Like the title stated. I really need help with this problem. It's in my training camp for my country's national olympiad.
I'll simplify it for you guys.
Given three numbers X,Y,Z (X,Y,Z <= 9000),
Count all divisors of all number that is a product from three numbers a,b,c such that (a <= X,b <= Y, c <= Z) (a divisor and be counted again and again) modulo 2^30
To be more clear,a simple algorithm to solve it is:
res = 0
for i = 1...X
for j = 1...Y
for k = 1...Z
res = res + count_divisors(i*j*k)
count_divisors is a function that counts all positive divisors of an integer
It's obviously too slow
Find res modulo 2^30
Time limit is 2 seconds.
It's quite ridiculous guys. Thank you for any help!
Example : X = 2,Y = 2, Z = 2
the numbers are : 1 , 2 , 2 , 2 , 4 , 4 , 4 , 8
total divisors are 20.

Full text and comments »

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