draid's blog

By draid, history, 3 months ago, In English

i was tackling C. Experience the other day and had a "clever" idea (well it's perhaps the intended but whatever) to support all the queries mentioned in the problem in $$$O(\alpha(n))$$$, using both union by size/rank and path compression, i thought it was nice and didn't see it documented elsewhere so here it is, the idea is to basically notice that if we merge two teams (with union by size/rank ofc), we can set the experience of the child representative node to that of it self minus of it's parent representative experience, so basically:

now if we want the experience of B, we can traverse the tree up and sum, so $$$x-y+y = x$$$ and if we at some point added some value m to A, we'll have B equal x + A, and when path compression we'll just add experience of the recursion, let's describe what each dsu part will do:

sunion(a, b): regular union by size, but we set experience of the children representative to itself minus of it's parent

void sunion(int a, int b) {
  a = find(a);
  b = find(b);
  if(a == b) return;
  if(size[a] > size[b]) {
    parents[b] = a;
    size[a] += size[b];
    exp[b] -= exp[a];
  }
  
  else {
    parents[a] = b;
    size[b] += size[a];
    exp[a] -= exp[a];
  }
}

find(v): regular path compression, we go up the tree and move the link, but we add a twist that for each move up we sum the experience, code: (**incorrect code but the idea is there, can anyone help me figure out what's wrong? i spent two days on this :sob:**)

pair<int, int> find_backend(int v) {
  if(v == parents[v]) return {v, exp[v]};
  else {
    parents[v] = find_backend(parents[v]).first;
    exp[v] += find_backend(parents[v]).second;
    return {parents[v], exp[v]};
  }
}

int find(int v) {
  return find_backend(v).first;
}

get_exp(v): and add_exp(v, m) both trivial

int get_exp(int v) {
  return find_backend(v).second;
}

void add_exp(int v, int m) {
  exp[find(v)] += m; 
}

and yes that's it, we solved the problem in $$$O(\alpha(n))$$$! very cleanly, very nicely! i'd really appreciate some debugging help to make the code correct, sorry for my lack of implementation skills!

Full text and comments »

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

By draid, history, 4 months ago, In English

i was trying to solve this cool cses problem the other minute and i stumbled across a problem relating modulo: im pretty sure there is nothing wrong with my usage of spoiler dirichlet's hyperbola method, basically what i did was computing the first two sums modulo M then subtracting the last chunk modulo then modulo the actual result applying the rule (a mod m) — (b mod m) mod m = (a — b mod m), but there is a case when b mod m is just greater than a mod m and not b > a, i don't know what to do! can anyone please correct my usage of modulo! thanks in advance :3

#include <bits/stdc++.h>

using namespace std;
#define int unsigned long long

int G(int n) {
  return n*(n+1)/2;
}

signed main() {
  int n; cin >> n;
  int res = 0, MOD = 1e9 + 7, t = (int)sqrt(n);
  for(int i = 1; i <= t ; i++) {
    res += G(n/i)%MOD;
    res += (i * (n/i))%MOD;
    res %= MOD;
  }

  res -= (G(t)*t)%MOD;
  res %= MOD;
  cout << res;
}

Full text and comments »

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

By draid, history, 5 months ago, In English

i've spent the last 3 months doing projecteuler, learned a lot of stuff, things such as dirichlet's hyperbola method, pell's equations, generating functions... it was a wonderful journey! i just felt like sharing this, pretty proud of myself! :3

Full text and comments »

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

By draid, history, 5 months ago, In English

today, i was hit with 0 points in the finals of the national IOI selection contest, well, it was expected since im a newbie, but i wasn't ready, i spent this entire year knowing what cp is, seeing others getting higher in their cp ranks, being the one people laughed at, im arrogant, i can't accept the fact that who once i were better than, are slowly but definitely becoming better than me, couldn't participate in their discussions, i was always a "algorithm x? yeah fancy way of saying backtracking, ha!" type of person in discussions, i was, and still, an arrogant person, as of writing this im full of jealousy towards those who will go the IOI, we were just trolling together the other month, or year... i hate what i've became, depression is tearing me apart, i want to be a better, non-trolling version of myself, it's only me who can decide with actions, to be a better version, a version that others actually respect, a version that can make it to the IOI, someone told me a statement that stuck with me, "you are only 15, even if you fucked this year you still have two tries!", well, although this statement is true, i don't want to go to the IOI at my current state, i don't want to shame my country nor my self, comparing my current self to my last year self doesn't form a huge difference, although i did know what cp is and practiced lightly, i'd say apart from my physical growth, you won't be able to tell difference between the two, i have to take action and stop using my environment or whatever as an excuse for my slow progress, i have people who are waiting patiently for the day when i'll be able to provide to them, and wanting the best for me, i want to make it to the IOI sooner than later, this can only be done by proving my existence in codeforces/projecteuler (or not, but that's another debate :3), i will do my best, i promise you curious reader! i don't like stating goals so let it be... (up/down)vote this as you want, i just want this to be here, i need too, im sick of myself and i need to be not urgently, it's summer in my country, and i have 85 days left.

Full text and comments »

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