UnstoppableSolveMachine's blog

By UnstoppableSolveMachine, history, 13 days ago, translation, In English,

The MEX Foundation Contest #1 (supported by AIM Tech) that was held in the 37th Petrozavodsk Programming Camp now available in the Gym.

The authors of the contest are UnstoppableSolveMachine, cookiedoth, egor.lifar. The problems are of a good quality, a number of participants can approve it.

Special thanks to gritukan for useful advices, LHiC for testing the contest, V--gLaSsH0ldEr593--V for inspiration and AIM Tech Members for the problem review.

The editorial

Read more »

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

By UnstoppableSolveMachine, 16 months ago, In English,

TestManager

Hello, I would like to introduce the plugin FastOlympicCoding for Sublime Text.
It provides several useful features for competitive programming.

Read more »

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

By UnstoppableSolveMachine, history, 22 months ago, translation, In English,

I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
  Node *l = NULL, *r = NULL;
  int key, priority, cnt = 1;

  Node *musorka = NULL;
}

and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
  if (!node->musorka) return;
  push(node->l);
  push(node->r);

  pair<Node*, Node*> spl = split(node->musorka, node->key);
  pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
  
  if (spl2.first) {
    node->cnt++;
  }

  node->l->musorka = spl.first;
  node->r->musorka = spl2.second;
  node->musorka = NULL;
}

then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?

Read more »

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