Abito's blog

By Abito, history, 7 weeks ago, In English

Hello Codeforces. This year I participated in IOI, and I did really bad. I want to improve throughout the year and try to manage my time with studying for school since this is graduation year. I want to find optimal way to practice, since I'm feeling that Codeforces problems are not really IOI-like. I was thinking of solving OI problems, but I don't really know how to sort them so that I can find problems for my level, since oj sorting style isn't really useful. Also I'm not even sure if simply solving problems throughout the year is useful alone too. Enough of my chaotic thoughts, I want to ask people who did well in IOI, at least silver, how do you practice? What sites do you usually solve on? How do you decide where to solve problem? You get the idea. I tried searching for blogs about these stuff but I only found the one by E869120 but it only talks about his strategy and speedsolving practice, which is useful, but definitely not everthing. I appreciate any replies.

Full text and comments »

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

By Abito, history, 7 months ago, In English

Many graph problems have subtasks where the graph is a complete binary tree (edge between i and i*2, i and i*2+1), however I often struggle with them. Does anyone know a useful resource that discusses different techniques to approach such a problem/subtask?

Full text and comments »

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

By Abito, history, 7 months ago, In English

Hello! IIOT is an olympiad for teams of 4. It's going to be in Syria this year on May 10th. My team will be there onsite (unofficial participation though):

AbitoDe3b0oRyuk_999Lemoliz

Other Syrian teams:

Ahmad_OSAbdalaziz_AlshamiKaram_KallasiK.Al-Ani7 Unofficial

Haidora + 3 Unofficial

NeroZeinhocln3laaM_sawas_ Official

edogawa_somethingaminshYazanAlattarBash. Official

If you know other participating teams please share!

Contest website

Full text and comments »

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

By Abito, history, 13 months ago, In English

Sometimes I encounter a type of range queries that I don't know how to do using segment tree, so I use a merge sort tree instead. It can answer queries in $$$O(log^2 n ) $$$. I decided to share this because it can be useful to many in contests. First, we know that a node in a segment tree stores the answer for a range of length $$$2^x$$$ for some $$$x$$$, but we can also store in it all the elements in the range sorted in a vector (using merge sort algo) or set or whatever. Here I am going to give a few examples how we can use this to our advantage.

Problem 1: Static Count of Lesser Elements range queries.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has three integers $$$l_i , r_i , x_i$$$. The answer for this query is how many $$$a_j$$$ such that $$$l_i \le j \le r_i$$$ and $$$a_j < x$$$.

Solution
Code

Problem 2: Dynamic Lower Bound problem.

We are given an array $$$a_1, a_2, a_3... a_n$$$ and an integer $$$q$$$. The $$$i$$$_th of the next $$$q$$$ lines has an integer $$$t_i$$$, describing the type of query.

  • If $$$t_i = 0$$$ then you are given two other integers, $$$idx_i$$$ and $$$x_i$$$, meaning that we should make $$$a_{idx} = x_i$$$.
  • If $$$t_i = 1$$$ then you are given three integers $$$l_i, r_i, x_i$$$. You should answer with the smallest value $$$v$$$ in the range $$$[l_i,r_i]$$$ such that $$$x \le v$$$. If there is none, print -1.
Solution
Code

Final notes

There are many other things that you can do using technique. You can even solve the dynamic version of the first problem using indexed_set. However you should use this only when you're desperate because it's really slow. Yes it's $$$O(nlog^2n)$$$ but the constant factor is very high because it's segment tree + sets. If you have intereseting problems to add to the blog, or you notice some mistake please say in the comments. Good luck everyone!

Problems

SPOJ — KQUERY

CF EDU Segment Tree Step 3 C

CF — 816B

Full text and comments »

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

By Abito, history, 18 months ago, In English

Next contest should be 879. Please fix. Edit: fixed.

Full text and comments »

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

By Abito, history, 19 months ago, In English

Troll accounts are nearly unescapable. No matter what restrictions are made, there will always be troll accounts, but please at least decrease spam. Look at recent actions now, it's all the same account. I think that having a time limit between blogs, like you can post another blog only 1 hour after another is good. What do you people think?

Full text and comments »

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

By Abito, history, 21 month(s) ago, In English

Don't use sqrt because precision issues

Also here is implementation to find floor(sqrt(x))

#define int long long
int sqrt(int x){
    int l=1,r=1e9+5,ans=0,mid;
    while (l<=r){
        mid=(l+r)/2;
        if (mid*mid<=x){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }return ans;
}

It seems std::sqrt works fine in C++17 though. Also sqrtl seems to give correct results

Full text and comments »

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

By Abito, history, 21 month(s) ago, In English

Hello Codeforces! So my friend Haidora thought that in problem C yesterday it asked for the number of beautiful sets of all lengths (lol) and we were talking now about a solution for this problem and came up with an $$$O(rlogr)$$$ DP solution.

Formal Statement

A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).

You are given two integers $$$l$$$ and $$$r$$$ . Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$: You have to print their number modulo $$$998244353$$$

Solution

Let $$$dp_x$$$ be the number of beautiful sets we can build such that the minimum number in these sets is $$$x$$$. Now, how do we find $$$dp_x$$$? Let's iterate through all numbers $$$i$$$ such that $$$xi \le r$$$, which means that we'll go through all multiples of $$$x$$$ as long as they are less than $$$r$$$. Now let's add their answers to our $$$dp_x$$$. Formally:

$$$dp_x = 1 + \sum_{i=2}^{xi \le r} dp_{xi} $$$ Now our answer would be summing them all up, because we want all sets, so for all possible minimums we want to know the number of sets possible using it. Formally: $$$ans = \sum_{i=l}^{i \le r} dp_{i} $$$

Note that the $$$1+$$$ is there because choosing $$$x$$$ alone in a set is also valid.

Time complexity

Why is it $$$O(rlogr)$$$? For each $$$x$$$ you are iterating through all number $$$xi \le r$$$ which is $$$r \sum_{i=l}^{i \le r} dp_{1/i} $$$ which is close to $$$O(rlogr)$$$ Thanks to NaimSS for correcting my time complexity.

Implementation

I used recursive DP:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=998244353;
int dp[N],l,r;
int rec(int x){
    if (x>r) return 0;
    if (dp[x]) return dp[x];
    dp[x]=1;
    for (int i=2;i*x<=r;i++) dp[x]=(dp[x]+rec(x*i))%M;
    return dp[x];
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>l>>r;
    int ans=0;
    for (int i=l;i<=r;i++) ans=(ans+rec(i))%M;
    cout<<ans<<endl;
    return 0;
}

This code runs less than 100ms on C++20(64) when $$$l = 1$$$ and $$$r = 10^6$$$ , and less than 2000ms when $$$l = 1$$$ and $$$r = 10^7$$$. Tried on Codeforces custom test.

Iterative DP by Farsh_LE:

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+5,M=998244353;
int dp[N],l,r;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>l>>r;
    int ans=0;
    for (int x=r;x>=l;x--){
        dp[x]=1;
        for (int i=2;x*i<=r;i++) dp[x]=(dp[x]+dp[x*i])%M;
        ans=(ans+dp[x])%M;
    }cout<<ans<<endl;
    return 0;
}

Nearly same speed as recursive, a bit faster though.

Final Notes

This is my first blog of this kind, so feel free to share your opinions as it will help me and others for the future. Also, please point out any mistakes you find. And I have a few questions: Could there be a faster solution? Also if there is an iterative DP solution please share it, because I couldn't find any way to do it iteratively. Thanks!

Full text and comments »

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

By Abito, history, 22 months ago, In English

Last year a contest was held on Valentine's Day. Why isn't is the same this year? Do you expect us to go on dates? Please give us Valentine's Day contest :(

Full text and comments »

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

By Abito, history, 23 months ago, In English

Many people use the normal upper_bound() function, which is slow (at worst case O(n)) and get TLE. When you are using a set/multiset/map, use containername.upper_bound() This function uses Binary Search which runs at O(logn) time. Please be careful next time. This is only a reminder because I'm seeing a lot of people get TLE because of this.

Full text and comments »

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

By Abito, history, 23 months ago, In English

Hello Codeforces. I'm trying to add my wallet in magic place but it's asking for a secret code and I don't know how to find it. I'm using tonkeeper app. If anyone knows how to find it please help me. Thanks in advance!

Full text and comments »

Tags ton
  • Vote: I like it
  • -7
  • Vote: I do not like it

By Abito, history, 2 years ago, In English

Hello CodeForces, I want to solve problems of Innopolis University Open Olympiad previous years, but I only found archives pre 2019. Does anyone know where I can find problems of 2020 and 2021? Thanks in advance. Update: Theo830 shared this link.

Full text and comments »

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

By Abito, history, 2 years ago, In English

Hello everyone. So Global Rounds are made every 2 months and last one was in June, but as I can see there isn't going to be a Global Round this month. Why is that? Is it postponed to September or something?

Full text and comments »

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

By Abito, history, 2 years ago, In English

Happy Eid Codeforces! I hope you have positive delta and a happy week

Full text and comments »

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