bgopc's blog

By bgopc, history, 9 days ago, In English

what's wrong with the queue, 20mins have passed and my code is still in queue?

There was no contests today and no rejudging, so why so long queues

Full text and comments »

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

By bgopc, history, 7 weeks ago, In English

So I was looking for some probability problems And I stumbled upon 398B - Красим стену, I realized it had no rating, which was weird in my opinion because it was a normal Div1 without anything special, I checked the whole contest and no problems had a rating, I thought it's my get rating scripts' bug, but when I enabled tags in the setting there were no rating tags? Is this a bug? MikeMirzayanov

Full text and comments »

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

By bgopc, history, 7 weeks ago, In English

Hello, following my previous blog, I'm adding the new problems I found interesting/teaching, so let's get into the problems

Note: these problems are mostly for the range of [pupil, expert] level, an average specialist with a bit of sweat will be able to solve them all

Problems

The problems aren't in any specific order but higher problems may be a bit easier
These problems' requirements are intermediate dp, binary search, pure logic, algorithmic thinking, and math.
and I've solved all of them so feel free to check my submissions if u wanted

Full text and comments »

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

By bgopc, history, 3 months ago, In English

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

Full text and comments »

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

By bgopc, history, 4 months ago, In English
  • Vote: I like it
  • +75
  • Vote: I do not like it

By bgopc, history, 4 months ago, In English

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

problems

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

Peace

Full text and comments »

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

By bgopc, history, 5 months ago, In English

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

Full text and comments »

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

By bgopc, history, 5 months ago, In English

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

Full text and comments »

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

By bgopc, 5 months ago, In English

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

Full text and comments »

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

By bgopc, history, 5 months ago, In English

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

EDIT: Part 2 added, link

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?

Full text and comments »

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