\frac{\lfloor n/k \rfloor}{l} \right\rfloor = \lfloor \frac{n}{kl}\rfloor$,
thus the values of $F(n, points below $kl=t$. There are two cases two consider here:, /Orthogonal_convex_hull) of points under the hyperbola $kl=n$: $$
\boxed{\sum\limits_{ij \leq n, ://en.wikipedia.org/wiki/Orthogonal_convex_hull) of points under the hyperbola $
kl=n$:, Note that for $(k, l)$ to be on the rectilinear convex hull of points below $kl
=n$, it is necessary
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | Dominater069 | 131 |
| 9 | Proof_by_QED | 130 |
| 9 | AmShZ | 130 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Dirichlet convolution. Part 1: Fast prefix sum computations Hi everyone!
Suppose that you need to compute some sum of a number-theoretic function that has something to do with divisors:
$$\begin{gather}
\sum\limits_{k=1}^n \varphi(k) = ? \\
\sum\limits_{k=1}^n \sum\limits_{d|k} d^2 = ?? \\
\sum\limits_{x=1}^n \sum\limits_{y=1}^x \gcd(x, y) = ?!?
\end{gather}$$
As it turns out, such and many similar sums can be computed with Dirichlet convolution in $O(n^{2/3})$, and in this article we will learn how.
Let $f(n)$ and $g(n)$ be two [arithmetic functions](https://en.wikipedia.org/wiki/Arithmetic_function). Let $F(n)$ and $G(n)$ be their prefix sums, that is
$$\begin{matrix}
F(n) = \sum\limits_{i=1}^n f(i), & G(n) = \sum\limits_{j=1}^n g(j).
\end{matrix}$$
We need to compute a prefix sum of the [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) $(f * g)(n)$. In this article, we will consider some general methods, and show how to do so in $O(n^{2/3})$ if we can compute prefix sums of $F(n)$ and $G(n)$ in ...
2.
Hadamard product and binomial convolution of linear recurrences Hi everyone!
Let $R$ be a ring, $d_0, d_1, d_2, \dots \in R$ and $e_0, e_1, e_2, \dots \in R$ be linear recurrence sequences, such that
$$\begin{gather}
d_m = \sum\limits_{i=1}^k a_i d_{m-i}\text{ for }m \geq k, \\
e_m = \sum\limits_{i=1}^l b_i e_{m-i}\text{ for }m \geq l.
\end{gather}$$
In some applications, the following two sequences arise:
$$\begin{gather}
f_k &=& d_k e_k & \text{(Hadamard product)}, \\
f_k &=& \sum\limits_{i+j=k} \binom{k}{i} d_i e_j & \text{(binomial convolution)}.
\end{gather}$$
Today I'd like to write about the framework that allows to prove that both the sequences defined above are also linear recurrences. It would also allow to compute their characteristic polynomials in $O(kl \log kl)$, which is optimal as their degrees are $O(kl)$ in both cases.
[cut]<br>
### Umbral calculus
Generally, a linear recurrence $f_k$ can be [described and analyzed](https://codeforces.me/blog/entry/100158) with the help of the linear functional $T : ...
$O(kl \log kl)$, which is optimal as their degrees are $O(kl)$ in both cases., characteristic polynomials in $O(kl \log kl)$, which is optimal as their
degrees are $O(kl)$ in both, In the sum above, there are $2^{kl}$ summands, each of them is divisible by
either $a(d)$ or $b(e, The resulting $f(x)$ has degree $kl$, so only $kl$ terms of $\frac{A'}{A}$ and
$\exp$ are needed
3.
Exponential Length Substrings in Pattern Matching Hi all,
I would like to share with you a part of my undergraduate thesis on a Multi-String Pattern Matcher data structure. In my opinion, it's easy to understand and hard to implement correctly and efficiently. It's (relatively) competitive against other MSPM data structures (Aho-Corasick, suffix array/automaton/tree to name a few) when the dictionary size is specifically (uncommonly) large.
I would also like to sign up this entry to [user:bashkort,2024-10-04]'s [Month of Blog Posts](https://codeforces.me/blog/entry/133806):-) Many thanks to him and peltorator for supporting this initiative.
#### Abstract
This work describes a hash-based mass-searching algorithm, finding (count, location of first match) entries from a dictionary against a string $s$ of length $n$. The presented implementation makes use of all substrings of $s$ whose lengths are powers of $2$ to construct an offline algorithm that can, in some cases, reach a complexity of $O(n \log^2n)$ even if there are $O...
larger, the shade would be longer) may be ended with $\varnothing$: $shade(s,
kl) = kl\varnothing, shade would be longer) may be ended with $\varnothing$: $shade(s, kl) = kl
\varnothing$.
4.
[Tutorial][GYM] The 2019 University of Jordan Collegiate Programming Contest Hello,
The problem set is basically divided into 2 parts, very easy problems that were created for teams completely new to ICPC contests, and harder problems for experienced teams. I believe that all the problems were suitable for a div.3 contest except for problems G and L.
[tutorial:102267A]
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a >= b);
}
~~~~~
</spoiler>
[tutorial:102267B]
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
bool isp(int x){
if (x < 2)return false;
for (int i = 2; i * i <= x; ++i)if (x % i == 0)return false;
return true;
}
int main(){
int x;
scanf("%d", &x);
if (isp(x - 2))printf("%d %d\n", 2, x - 2);
else printf("-1\n");
}
~~~~~
</spoiler>
[cut]
[tutorial:102267C]
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
...
] + s[b]; } void kl(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){ if (l
== r){ if(sm + s, int dead(ll x){ int fr = s[1].fr; kl(x); return fr - s[1].fr; }, void kl(ll x, ll sm = 0, int l = 1, int r = n, int id = 1){ if (l == r){ if(sm
+ s[id].mn >= x
5.
[Tutorial] Tangents of a Polygon in O(log n) In one of the last stages of the 3rd Universal Cup, there was a not-so-nice problem (it required using fractions) that involved an algorithm for which I hadn't found a tutorial or much information on popular blogs. This approach was developed by me, and I appreciate any feedback on it or its implementation.
https://codeforces.me/gym/105657/problem/C
#### Parameters
- The polygon is convex
- The point is not strictly inside
#### What are the tangents to a polygon from a point?
The tangents of a polygon with respect to a point are the lines that pass through the point outside the polygon and touch the polygon at exactly one vertex or along one side, without crossing its interior.
<img src="/predownloaded/7a/2b/7a2bc71ba65fd9ebcf0df712893bfe96417c8dc6.png" style="width:350px; height:300px;" />
#### Why are these useful?
- Solve difficult problems
- Solve problems related to visibility or trajectory where the polygon cannot be crossed.
#### Algorithm
To descr...
= [&](int l, int r, ld w, int kl) -> int { int res = l; while(l <= r){ int m =
(l, auto tang = [&](int l, int r, ld w, int kl) -> int { int res = l; while(l <= r
6.
Is this maxflow problem? [Let's discuss interesting hard(?) problem] Hello great codeforces community, I was trying to solve [this problem](http://codechillout.sphere-contest.com/problems/onlineround/LADYBUGS), the core problem is simple: Given n lines, find maximum number line segments such that no two line segments intersect.
Formally: Given set A containing n line segments from point (Xs[i],0) to point (Xf[i],Yf[i]) inclusive for each integer (1 ≤ i ≤ n), with satisfy this condition: (1 ≤ n ≤ 200, -40000 ≤ Xs[i], Xf[i] ≤ 40000, 0 ≤ Yf[i] ≤ 40000; all n,Xs[i],Xf[i],Yf[i] are integers), let set B containing all subset of set A such that no pair of line segments in that set intersect. The problem is to find an element from set B with maximum length.
-------------------------------------------------------------
One valid example:
in the picture above there are 12 line segments: A={AB,BC,CD,EF,GH,IJ,KL,MN,OP,QR,ST,UV}
One of the solution (maximum subset of set A such that no two line seg...
,EF,GH,IJ,KL,MN,OP,QR,ST,UV} One of the solution (maximum subset of set A such
that no two line, For group {KL,MN,UV} is similar to group {AB,BC,CD}, the optimal one is not to
select MN., in the picture above there are 12 line segments: A={AB,BC,CD,EF,GH,IJ,KL
,MN,OP,QR,ST,UV}
7.
A proof of error bound of Miller-Rabin prime test I have studied the Miller-Rabin's algorithm ten years ago and never have tried to find out why it is reliable. I know the error bound (the probability that a composite number passes the test with k rounds) is (1/4)^k, but when I try to prove it, I find it is not obvious. So after several days on reading notes and materials I got it. I try to write down the proof as much detailed as possible for other people. See my website (https://randop321.com/) for other posts :D
Most of the metarials in this post are come from <a href="https://www.cis.upenn.edu/~jean/RSA-primality-testing.pdf">https://www.cis.upenn.edu/~jean/RSA-primality-testing.pdf</a> . I reorganized and rewrite some of parts for better understanding.
Sketch of Proof
<!-- wp:list -->
<ul><li>Step 1. The definition of Miller-Rabin's algorithm and the Liar Set $ L$<ul><li>our goal is proving that $ |L|$ is not very large compared with the tested number $ n$</li></ul></li><li>Step 2. The definition of group $ S$ and it...
follows that $ k \nmid 2^{i}t$, or we will get a contradiction that $ x^{2^it}
= x^{kl} \equiv 1 \mod, will get a contradiction that $ x^{2^it} = x^{kl} \equiv 1 \mod p_i$.
Following the above fact we get
8.
Свежие впечатления от V открытой олимпиады ЮФУ в Таганроге 1. День первый.<br><br>Мы с Колей пришли, зарегистрировались. Потом открытие и техническое совещание. Ничего нового не услышали =) А вот потом пробный тур, и это было существенно! Во-первых, не буду вдаваться в подробности, но пришлось приложить существенные усилия для того, чтобы можно было использовать компилятор С++ из-под фара. Во-вторых, на нашей клавиатуре пробел нажимался пример один раз из двух =) Мы заявили об этом, спросив, можно ли заметить клавиатуру? <br><br>Нам ответили, как в анекдоте: "можно, заменяйте. Только сейчас, завтра будет нельзя". Как будто мы с собой привезли клавиатуру на этот случай) Ну, в общем, пришлось обратиться к оргкомитету лично, чтобы нам заменили клаву на нормальную.<br><br><p>[cut]<br></p>2. День второй.<br>Сначала я с печалью понаблюдал, как Коля в TopSpeedCoder не успел сдать задачу D и вылетел с 10 места. Он пришёл в зал совещаний, мы успели пообсуждать задачи. Потом техническое совещание по Code Warriors Challenge. Нам рассказали суть зада...
динамика, где надо было бы вовсю попользоваться тем, что поле периодично, и
делать не за O(KL), а за
9.
Calculate length of line inside a polygon Given a non self-intersect polygon and a line. How can I calculate the total length of parts of line which are inside the polygon? I need an $O(NlogN)$ or faster algorithm, where N is the number of vertices of polygon.
For example, below is the polygon $ABCDEFGH$.
With line $y=0$, no parts inside the polygon.
With line $y=2$, the parts inside the polygon are IJ and KL, and the total length is 2.5.
With line $y=3$, the part inside the polygon is BC, which has length 1,
<a href="http://tinypic.com?ref=14myygy" target="_blank"><img src="http://i62.tinypic.com/14myygy.png" border="0" alt="Image and video hosting by TinyPic"></a>
I'm looking for your answers. Thanks for your help.
inside the polygon. With line $y=2$, the parts inside the polygon are IJ and KL
, and the total, With line $y=2$, the parts inside the polygon are IJ and KL, and the total
length is 2.5.
10.
Recieving Runtime Error I am getting below run time error in Codeforces, though code works as expected in my local compiler. Time: 0 ms, memory: 0 KB Verdict: RUNTIME_ERROR
I submitted my code for http://codeforces.me/contest/962/problem/D
Code is below.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>a(n);
map<int,set<int>>m;
for(int i=0;i<n;i++)
{
cin >> a[i];
m[a[i]].insert(i);
}
map<int,set<int>>::iterator it;
int flag=1;
while(flag)
{
flag=0;
for(it=m.begin();it!=m.end();it++)
if(it->second.size()>=2)
{
flag=1;
break;
}
if(flag==0)
break;
set<int>:: iterator it1;
set<int>s1;
s1=it->second;
it1 = s1.begin();
int val = it->first;
int gh = *it1;
s1.erase(it1);
it1++;
int kl = *it1;
s1.erase(it1);
if(s1.size()==0)
m.erase(val);
else
it->second=s1;
val*=2;
m[val].insert(kl);
}
vector<int>ans(n,-1);
int cnt=0;
for(it=m.begin();it!=m.end();...
++; int kl = *it1; s1.erase(it1); if(s1.size()==0) m.erase(val); else
it->second=s1, ; it1 = s1.begin(); int val = it->first; int gh = *it1; s1.erase(it1); it1++;
intkl
11.
need explanation on output of this program Hello all, recently I gave my C++ exam, I came across this question.
I was unable to understand the logic.
Can anyone explain what happens inside foo() ?
Thanks for your help :)
~~~~~
#include <iostream>
using namespace std;
void foo(char **p);
int main()
{
char *argv[] = {"ab","cd","ef","gh","ij","kl"};
foo(argv);
return 0;
}
void foo(char **p)
{
char *t = (p += sizeof(int))[-1];
cout << t << '\n';
}
~~~~~
[] = {"ab","cd","ef","gh","ij","kl"}; foo(argv); return 0; } void foo(char **p, int main() { char *argv[] = {"ab","cd","ef","gh","ij","kl"}; foo(argv); return
0; }
12.
При отправалении этого кода больше половини тестов с Run-time error Signal 11 (Ошибка адресации) #include <bits/stdc++.h>
using namespace std;
#define endl'\n'
typedef long long ll;
const ll INF=1000000000000000099;
ll n,m,k,kl,o,op;
set<pair<ll,ll>> s;
pair<ll,ll> p[400009];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>p[i].first>>p[i].second;
sort(p+1,p+1+n);
for(int i=1;i<=n;i++) {ll lk=0;
if(s.size()>0) {
for(auto x:s) {if(s.size()<=0) break;
ll d1=x.first,d2=x.second;//if(d1>=p[i].first) break;s.erase(x);
if(d1<1) {o-=d2;op++;s.erase(x);continue;}
if(d1>=p[i].first) break;
if(s.size()<=0) break;}}//cout<<"OP"<<op<<"OP";
if(p[i].second>o) {
kl+=(p[i].second-o)/k;lk=(p[i].second-o)/k;
if((p[i].second-o)%k!=0) {kl++;lk++;}o+=lk*k;
s.insert({p[i].first+2*m,lk*k});
}
}cout<<kl;
return 0;
}
INF=1000000000000000099; ll n,m,k,kl,o,op; set> s; pair p[400009]; int main
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 16:55:54 (g2).
Desktop version, switch to mobile version.
Supported by
