### bgopc's blog

By bgopc, history, 4 weeks ago,

As we all have noticed it's been a while that tourist wasn't doing as well as before in the contests and had dropped to the rank 13, but yesterday he crushed the Div1 solving to E2 and got the rating change of +125.
When I started cp he was the first in cf, and seeing him dropped was a weird thing, tourist the legend of legends dropped to 13th, but he proved us again that is the best by re-getting first.

Congratulations

• -17

By bgopc, history, 2 months ago,
• +75

By bgopc, history, 2 months ago,

Hello cf community, in this blog I tried to gather binary search problems that are worth solving and maybe makes you learn it better, if there exist any blog tell me I'll remove this

These problems are mostly specialist/expert level based but everyone can solve them, have fun and Hope you enjoy them

Peace

• +14

By bgopc, history, 3 months ago,

In a weird high school, there are $n$ students, and the school principal Mr. X wants to make students happy so he decides to throw a couples' party.
In this high school, between every 2 person, there can be 4 types of relationships:
1: they love each other
2: The first loves the second but the second doesn't
3: The second loves the first but the first doesn't
4: they don't like each other

At this party, people will be grouped into Pairs of couples.
The relationship between them determines the happiness of a pair:
type 1: happiness 2, type 2,3: happiness 1, type 4: happiness -1
if a person gets left out(I.E n is odd) there will be a -2 happiness for him

Since Mr. X is a happy person he wants to maximize the sum happiness of the party. Since he is a busy person He asks you to do that

Input Format
In The First Line, there will be one integer $n$: $n$, ($1 \leq n \leq 10^5$) the number of people at the party. In the Second line will be $m$, the number of people who love a person ($1 \leq r \leq 10^5$)
In the following $m$ lines there will be a format: two indexes $i$, $j$ meaning the person $i$ loves the person $j$. (Two-sided love will be given in 2 separate lines, if there isn't a directed edge between 2 people their relationship is type 4)

Output Format In the only line of the output, print the maximum happiness of the party

So today I came up with this problem and actually got stuck in solving it. Appreciate any helps

• -20

By bgopc, history, 4 months ago,

Hello, In this blog, I've tried to share my opinion on how to get good at dp problems, so stick to the end
in my opinion, dp is 85% thinking on paper, 10% thinking in your brain and 5% implementation.
so if you approach a dp problem always have pencil and paper and USE THEM another thing is just solving the DP problems in combinatorics.
What do I mean?

Question. 1 Given $n$, generate the set $s$ s.t $s = {1, 2, 3, 4, ..., n-1, n}$ then
count the number of subsets, where those elements in the set have at least 1 element in between them;
for example, $n = 8$ then $s = {1,2,3,4,5,6,7,8}$, one valid subset would be ${1,4,8}$.

Solution

Question. 2 Same as Question 1 but should have at least 2 elements in between them

Solution

Question. 3 Same as Question 1, Let's stop it
Let $a_n$ be the number of binary strings with ab, s. t no three consecutive characters are a.
find a recursive formula for $a_n$.

Solution

Since the problems I've are in Persian and translating them would be a pain, Message me and I'll send them to you if you want but the translation is on you

Hope this Helped

• -33

By bgopc, 4 months ago,

Hello, CF community, I found this 1700*-ish problem, can somebody help?

Given $n$, $d$ positive integers, and the array $a$ with length $n$
for each $i$ s. t $1 \leq i \leq n$
Find the maximum j s. t $\vert{a_i - a_j}\vert \leq d$

Input format:
Integers n,d: $1 \leq n \leq 1e5, 1 \leq d \leq 1e9$
In the next line given $n$ integers representing $a_1$, $a_2$, ..., $a_{n-1}$, $a_n$

Output format:
In single line for each $1 \leq i \leq n$ output the corresponding $j$
if there is no corresponding $j$ output -1

I'd appreciate a solution without any kind of advanced data structure(___Trees, ___Arrays, etc)
Thanks for any help

• -19

By bgopc, history, 4 months ago,

Hello CF community, in this blog post I tried to gather the Questions I've solved and enjoyed them most of them are really teaching and worth spending hours of time on them Hope you enjoy

Note that to solve these problems you need no knowledge except:
9th grade math, a little bit number theory, sorting, elementary dp, elementary bs, set, stack, queue, map

Good luck and hope you enjoy them

EDIT: I added maybe a few problems, I ran out of beautiful problems, unfortunately, maybe suggest in the comments and I'll add them

Guys a question: do u want me to include recent contests as well?

• +74