sorry_marymarine's blog

By sorry_marymarine, history, 7 weeks ago, In Russian,

В разделе "переписка" исчезли все письма от юзера System, в том числе сообщение со ссылкой на подтверждение того, что я получил футболку. Una_Shem, MikeMirzayanov, я мануально подтверждаю, что получил футболку.

Read more »

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

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

Submission 59175457 by dorijanlendvaj
Look here:

int MOD=1000000007;
int MOD2=998244353;

Now look here:

void M998()
{
	swap(MOD,MOD2);
}

Now look here:

Now look here:

I've answered "YES!", but you should learn that he is wrong; the only evil thing here is the function void M998().

Read more »

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

By sorry_marymarine, history, 2 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By sorry_marymarine, 2 months ago, In English,

Hello! Codeforces Round #581 (Div. 2) will start on Aug/20/2019 17:35 (Moscow time). The round is rated for everyone whose rating isn't greater than 2099.

The problems were invented and prepared for you by danilz1806, baumanec and sorry_marymarine. Thanks to Anton arsijo Tsypko for the coordinating the round. Thanks to the testers for testing and giving advice:

You will be given 5 problems and 2 hours to solve them. The score distribution will be announced later is 500-750-1250-(1500+750)-2500.

The round is over! Congratulations to the winners:
1. 79brue
2. sinus_070
3. baluteshih
4. xpporzwzl
5. shahaliali1382

An editorial.

Read more »

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

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

Looking at the "Mo-based solution" of problem 1000F - Одно вхождение 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, 9 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, 9 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, 9 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, 12 months ago, In Russian,

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

Read more »

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

By sorry_marymarine, 12 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, 12 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, 15 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, 16 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, 17 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, 22 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it