Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

WIL's blog

By WIL, history, 9 years ago, In English

I found the problemset of "ACM ICPC 2010-2011 NEERC Moscow Subregional" and I have tried to solve this problems but i can't found an online judge where this context is, if someone can help me, i be grateful, thanks in advance!!!

Full text and comments »

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

By WIL, history, 9 years ago, In English

I recently studied this data structure, and resolved some problems, but I would like to solve other, if anyone can give me some problems, I would be grateful.

This are some problems that i solved by kdtree:

Full text and comments »

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

By WIL, history, 9 years ago, In English

I need some hins for this problem "City houses", please help.

Full text and comments »

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

By WIL, history, 9 years ago, In English

Usually, for solve problems where we have to know the number of element least that some value X, is ease use some data structure of binary search tree (like treap). But in competition is it's heavy copy this code, and usually i use for similar thing the set structure. But after some time of searching, I don't find out, how can i know for a set, the position of an element in the sorted list. Example:

//If i have in my set.
set<int>s;
s.insert(1);
s.insert(4);
s.insert(3);
s.insert(2);
//know the sorted position of 4.

if i search with some method (**find**,**lower_bound** or upper_bound) this return an iterator of the element, but it's posible know it's sorted position.

if I use a treap, I make an function where i keep the number of element to the left and finally when i find the element, the number of elements least that X is the number of elements to the left of X in the tree. An example in my treap:

class treap {
  struct node {
    int value, key, size,cc;
    node(int v, node *n):value(v){
      c[0] = c[1] = n;
      size = 1; key = rand() - 1;
      cc=1;
    }
    void rz() {
      size = c[0]->size + c[1]->size + cc;
    }
    node*c[2];
  }*root, *null;
  void rot(node*&t, bool d) {
    node*c = t->c[d];
    t->c[d] = c->c[!d];
    c->c[!d] = t;
    t->rz(); c->rz();
    t = c;
  }
  void insert(node*&t, int x) {
    if (t == null) {
      t = new node(x, null);
      return;
    }
    if (x == t->value){
        t->cc++;t->rz();
        return;
    }
    bool d = x > t->value;
    insert(t->c[d], x);
    if (t->c[d]->key < t->key) rot(t, d);
    else t->rz();
  }
  int Upper_bound(node*&t,int x,int izq){//For know the number of element <= X
      if(t==null)return izq;
      if(x==t->value)
          return t->c[0]->size+izq+t->cc;
      bool d=x>t->value;
      if(d)return Upper_bound(t->c[d],x,izq+t->c[0]->size+t->cc);
      return Upper_bound(t->c[d],x,izq);
  }
  void Delete(node*&t, int x) {
    if (t == null) return;
    if (t->value == x) {
      if(t->cc>1){
        t->cc--;t->rz();
        return;
      }
      bool d = t->c[1]->key < t->c[0]->key;
      if (t->c[d] == null) {
        delete t; t = null;
        return;
      }
      rot(t, d); Delete(t->c[!d], x);
    } else {
      bool d = x > t->value;
      Delete(t->c[d], x);
    }
    t->rz();
  }
public:
  treap() {
    null = new node(0, 0);
    null->size = 0;
    null->key = oo;
    root = null;
  }
  void ins(int x) {
    insert(root, x);
  }
  void del(int x) {
    Delete(root, x);
  }
  int busq(int x){
      return Upper_bound(root,x,0);
  }
};

It's posible make this in a set structure???

Full text and comments »

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

By WIL, history, 9 years ago, In English

Recently i found a problem about geometric, that ask for how many pair of points of the set of points, are good pair, and a good pair is a pair (a,b) of points where the max distance between both points to any other c point it is greater or equals at the distance between the firsts two points ( a and b).

as a formula: distance(a,b)<=max(distance(a,c),distance(b,c))

Can be at most 2000 points.

Is ease see, that can be solve for some O(n^2) whit some factor logn for search a point that invalidate a pair of points, but right now i don't see how search this point. If some one can help me, thank in advance???

UPD: here is the problem: link

Full text and comments »

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

By WIL, history, 9 years ago, In English

I need to know how many points are at most at a distance of 5 units, and can be 10 ^ 4 points. If anyone can help, I'd be grateful. thanks in advance.

Full text and comments »

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

By WIL, 9 years ago, In English

I'm looking for tutorials and good documentation about Matching in general graph, and if it's posible some problems that can be solve by this algorithm. Thank in advance?

Full text and comments »

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

By WIL, 9 years ago, In English

Recently i saw the following fragment of code in some solutions here in codeforce and another online judges, and my question is. What is this code?

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif

thank in advance!

Full text and comments »

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

By WIL, 9 years ago, In English

Recently I learn the dominator tree algorithm and I will like to solve some problem about this topic, if someone can help me with some link related to that, I be grateful. Thank in advance!!

UPD1: I found this problem disjoint water supply from 2013 ACM-ICPC Latin American Regional Contests maybe can be usefull, and thanks to marat.snowbear for this problems, very nice the second one.

Full text and comments »

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

By WIL, 9 years ago, In English

I like to know about interesting applications of flow algorithms, if anybody know please share your knowledge.

Full text and comments »

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

By WIL, 9 years ago, In English

I was seeing the solution of this 518D - Ilya and Escalator in the tutorial, and i don't know why after calculate the dp the answer is for j from 0 to n dp[j][t]*j. What mean the multiplication?, i don't understand this. Thank for your time!!!

Full text and comments »

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

By WIL, 9 years ago, In English

The problem is Fence the vegetables from "2014 Caribbean Finals of the ACM-ICPC" in caribbean online judged.

I think that the minimum perimeter, is equals to:
(maxX-minX+1)*2+(maxY-minY+1)*2
But i dont know how find the minimum area with this perimeter. Thank for the help!!!

Full text and comments »

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

By WIL, 9 years ago, In English

Hi everybody, i need some help with this problem from Ural Championship 2015 on timus judge. If someone can help with the main idea to solve this problem, because i dont see how calculate a tree from a graph where the difference between the minimum and maximum edge are the minimum posible. Thank for the help!!!

Full text and comments »

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

By WIL, 9 years ago, In English

For quite some time, I had the doubt about how many digits had an mathematical operation like this: A*B or A!, and searching in internet, i found how to do this using log, but i found the problem Python Brute Force, that ask for the number of digit to the following operation: 1*1!+2*2!+....+N*N!. I don't know how to count the number of digit to the sum of terms, like A+B. Maybe this problem is just transform the operations, but i don't see how to do that. thank for the help!!!

Full text and comments »

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

By WIL, 9 years ago, In English

I don't understand why the answer is find all uncovered position, because in example:

7 2
ioi
1 3

The text that can be formed is:

i o i o i _ _ (with two space in blank or uncovered position)

And the answer if we do that tutorial said, then will be:

26*26=676

But, the string ioioioi is obtained to in that combination, and then the first assumption it's no true, because the string ioi is matched in one more place that input.

thank??

Full text and comments »

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

By WIL, 9 years ago, In English

I'm looking for a good tutorial about matrix exponentiation, where explain how can i solve a recurrence like this: f(n)=f(n-1)+n*2

I know how to use matrix exponentiation to solve a recurrence where are used anterior terms, but i don't know when the recurrence have one term that depend to the position of the term.

thank you!!!

Full text and comments »

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

By WIL, 9 years ago, In English

My doubt is in problem "Riding the Fences" from Usaco site. I don't know the main idea for solve this problem. I know, is base in eulerian graph, but i don't see how solve it. Thank you for the help.

Full text and comments »

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