sorry_marymarine's blog

By sorry_marymarine, history, 5 weeks ago, In English,

Looking at the "Mo-based solution" of problem 1000F - One Occurrence in editorial, I noticed the author used some sqrt-decomposition to find any element in the set, but the author could do this in O(1) time using the data structure i'll describe right now.

The set which can contain integers from 1 to $$$n$$$ is stored as two arrays of length $$$O(n)$$$:

type set struct {
    index []int
    val []int
    size int
}

func newSet(n int) set {
    return set{make([]int,1+n),make([]int,1+n),0}
}

func (s *set) Size() int {
    return s.size
}

Inserting into the set:

func (s *set) Insert(x int) error {
    n := len(s.index)-1
    if x<1 || x>n {
        return errors.New("inappropriate value to insert")
    }
    if s.index[x] != 0 {
        return errors.New("value already exists in the set")
    }
    
    s.size++
    s.val[s.size] = x
    s.index[x] = s.size
    
    return nil
}

Erasing from the set:

func (s *set) Erase(x int) error {
    n := len(s.index)-1
    if x<1 || x>n {
        return errors.New("inappropriate value to erase")
    }
    if s.index[x] == 0 {
        return errors.New("value already doesn't exist in the set")
    }
    
    i := s.index[x]
    if i == s.size {
        s.val[s.size] = 0
        s.index[x] = 0
        s.size--
    } else {
        y := s.val[s.size]
        s.val[s.size] = 0
        s.index[y] = i
        s.val[i] = y
        s.index[x] = 0
        s.size--
    }
    return nil
}

Finding an element in the set:

func (s *set) Find (x int) bool {
    n := len(s.index)-1
    if x<1 || x>n {
        return false
    }
    return s.index[x]>0
}

Iterating over the set:

func (s *set) ToArray() []int {
    return s.val[1:1+s.size]
}

func (s *set) ValueAt(i int) int {
    return s.val[i-1]
}

However this set doesn't store values in the ascending order like the standard RB-tree set does.

Read more »

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

By sorry_marymarine, history, 5 months ago, In English,

Sometimes I am asked after solving a problem: what were your approaches? how did you come to the solution? I'll write some blogs about different problems where i'll discuss my thought process.

Problem: 101611F - Fake or Leak?
Submission: submission

Spoiler

thanks for reading!

Read more »

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

By sorry_marymarine, history, 6 months ago, In English,


Consider some object that can be represented as a sequence of something with some magic property. Magic property means we consider two such objects equal if one object can be obtained from another using some given permutation. For example, look at these equal necklaces of 8 elements with magic property "we consider two necklaces equal if one can be obtained from another with rotating":

equal necklaces

The corresponded special permutations are: 12345678, 23456781, 34567812, 45678123, 56781234, 67812345, 78123456, 81234567

Or look at these equal binary trees of size 7 with a magic property "we consider two trees equal if we can obtain one from another with permuting children of some vertexes":

equal trees

The corresponded special permutations are: 1234567, 1234576, 1235467, 1235476, 1326745, 1326754, 1327645, 1327654.

Now we are given a problem: we have such an object with a magic property, and in how many ways we can paint elements of its sequence in k colours if we count equal paintings as one? According to burnside's lemma for this case, the answer is , where G is the set of special permutations, C(π) is the number of cycles in permutation π.
Let's try to solve this problem for reviewed binary tree with 7 vertexes:

G = (1234567, 1234576, 1235467, 1235476, 1326745, 1326754, 1327645, 1327654)
C(1234567) = 7: 1, 2, 3, 4, 5, 6, 7
C(1234576) = 6: 1, 2, 3, 4, 5, 6 - 7
C(1235467) = 6: 1, 2, 3, 4 - 5, 6, 7
C(1235476) = 5: 1, 2, 3, 4 - 5, 6 - 7
C(1326745) = 4: 1, 2 - 3, 4 - 6, 5 - 7
C(1326754) = 3: 1, 2 - 3, 4 - 6 - 5 - 7
C(1327645) = 3: 1, 2 - 3, 4 - 7 - 5 - 6
C(1327654) = 4: 1, 2 - 3, 4 - 7, 5 - 6
So the answer is

Read more »

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

By sorry_marymarine, history, 6 months ago, In English,

Consider two persons: me, who was able to easily solve div2 A and B when I had just started cp (my only preparations were math background and knowledge of languages) and noname grey/green coder who have participated in 10-20 contests but sometimes still stucks at div2 A. For me, it means the talent exists and is rather important in sports programming.

Can hard work and learning help to reach expert/cm? Is there an universal method to improve yourself? I think no. If yes, then 90% cf users could solve div2 ABC, but it is not true. The hard work and learning is required to get better when you can at least solve div2 AB; div2 A requires only some thinking and div2 B requires only some basics, but without a talent it is useless to try, it is better to do something else.

Downvote if you sure any person can be grandmaster.

Read more »

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

By sorry_marymarine, history, 8 months ago, In English,

A: add 0 at the beginning and 1001 at the end of the array. Find the longest subarray [l, r] such that r - l = a[r] - a[l]. Output maximum of 0 and its length minus 2.

B: if n = 1 then answer is 1 0; else factorize n, let the p is equal to the largest power of a prime divisor in factorization; the minimum number is the multiplication of all distinct prime divisors, and the number of steps is log2(p)⌉; also you need one more step if not all the prime divisors have the power equal to 2log2(p)⌉

C:reduce the problem to answer the queries "count the maximum value if you have s0 zeroes and s1 ones"; it is always optimal to take the most enjoyable part, so you need to eat all the 1s and then all the 0s; after eating all 1s your enjoyment is 2s1 - 1 and the remained s0 parts have enjoyment equal to this number; after eating them, you will gain additional (2s1 - 1)(2s0 - 1) enjoyment.

D: consider the graph with vertices 2, 3, ..., n and  - 2,  - 3, ...,  - n and edges between two vertices if one divides another and their absolute values are different; it is obvious that this graph has an eulerian cycle. So the answer is the sum of all transformation points; the number of transformations with points equal to i is 4 * (n / i - 1).

E: for each query, find with binsearch the least L such that lca(l, l + 1, ...L) = lca(l, ..., r) and the biggest R such that lca(R, R + 1, ...r) = lca(l, ..., r); try to exile the vertices L and R and choose the best answer. To count both lca of two vertexes and the segment of vertexes, use sparse tables.

thanks for testduk

congratulations to vbobrov for becoming a master!

Read more »

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

By sorry_marymarine, 8 months ago, In Russian,

Подробности здесь
Насколько это повлияет на качество задач и решений?

Read more »

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

By sorry_marymarine, 9 months ago, In English,

Recently, thedarkKnightrisesagain made a submit(44400925) and got Judgement failed. This verdict disturbs us. So we need to repair Codeforces.

Read more »

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

By sorry_marymarine, history, 9 months ago, In English,

Recently, There seems to be so many respected fake accounts.
We should not respect them. If we respect all accounts, then we respect some person twice (by respecting his main and alt accounts). It is unfair for those who doesn't have fake accounts, because they gain our respect only once. So we should stop respect them.

Read more »

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

By sorry_marymarine, history, 12 months ago, In English,

Seems like there are 4 pages of unjudged submissions ...

Read more »

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

By sorry_marymarine, history, 13 months ago, In English,

How to use FFT with 998244353?

Read more »

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

By sorry_marymarine, history, 14 months ago, In English,

Hi, Codeforces!

If two or three problems in div1 round have near the same difficulty and the next problem is much more difficult than that 2 or 3, than results are unfair: participants that solved these problems are sorted according to luck, not to their real skill. Examples:

Also hacking is near impossible in div1 rounds because participants are rather clever to make mistakes.

So I think that div1 rounds should be extended with div2 problems or div1 participants should compete with div2 contestants,

What is your opinion on this ideas?

Read more »

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

By sorry_marymarine, history, 19 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it

By sorry_marymarine, history, 22 months ago, In Russian,

Почему некоторые записи в блогах исчезают?

Например

Read more »

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