Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### rhezo's blog

By rhezo, history, 20 months ago, ,

Hello Codeforces,

HackerEarth July Easy '18 will start at 10 pm IST on 1st July, 2018 (25 minutes after the CF round ends. Hope you can participate). The duration of the contest is 3 hours.

You will be given 5 algorithmic problems of various difficulty levels. All problems will have partial scoring. You'll get points for each test case passed. Don't hesitate in scoring partial points in order to score as many points as possible if you want to get to the top.

Problems were prepared by me. They have been thoroughly tested by jtnydv25 and r3gz3n.

Prizes : Programmers with a HackerEarth rating of 1600 or less before the challenge starts will be eligible for prizes and t-shirts.

First prize: $100 Amazon gift card First runners up:$75 Amazon gift card

Second runners up: $50 Amazon gift card. Good luck and have fun! Read more » • +31 By rhezo, 2 years ago, , Hello Codeforces, HackerEarth November Easy '17 will start at 10 pm IST on 1st November, 2017. The duration of the contest is 3 hours. You will be given 5 algorithmic problems of various difficulty levels. All problems will have partial scoring. You'll get points for each test case passed. Don't hesitate in scoring partial points in order to score as many points as possible if you want to get to the top. Problems were prepared by AlexandruValeanu. They have been thoroughly tested by _AJ_, rhezo and reality. Thanks to _AJ_ who helped in preparation of the contest and making the contest in a good shape. Prizes : Programmers with a HackerEarth rating of 1600 or less before the challenge starts will be eligible for prizes and t-shirts. First prize:$100 Amazon gift card

First runners up: $75 Amazon gift card Second runners up:$50 Amazon gift card.

Good luck and have fun!

• +49

By rhezo, history, 3 years ago, ,

Hello CF community,

IndiaHacks Wildcard round will start at 8 PM IST on 23 / 7 / 17. Click on the link to see the starting time in your timezone.

For all those who didn't participate in one of the earlier rounds (IndiaHacks Qualifier and Wave 1.0) or failed to qualify in them, then this is a chance for you to qualify to the next round Wave 2.0.

Top 250 in this round qualify for Wave 2.0.

The problemset was created by Akash r3gz3n Sharma, Saurabh Apptica Joshi and Rishi rhezo Vikram. Konstantin zemen Semenov was the tester.

You'll be given 5 problems to solve in 6 hours. Hope you like the problemset. Good luck and have fun.

• +29

By rhezo, history, 3 years ago, ,

Suppose I have a cost function w(i, j) whose value depends on some f(j) and value of w(i, j) increases as |j — i + 1| increases. Also we can't compare between w(i, j) and w(p, q) even when |j — i| = |q — p| since that depends upon f(j) and f(q).

The cost function of land aquisition problem from USACO is similar and in the below link it claims that it satisfies quadrangle inequality. Check problem link from example 2 in below link.

So, does my original cost function satisfy quadrangle inequality? I'm confused!

• 0

By rhezo, history, 3 years ago, ,

How to solve this problem?

Statement: Given N nodes of a tree, answer Q queries of 2 types(update value of some node or find the number of distinct numbers on the path from U to V).

There is a solution with Mo's algorithm with updates and I don't understand that as well. Can anyone explain any other approach or even this one?

• +10

By rhezo, history, 3 years ago, ,

How do I find this for large N? (N ≤ 1011).

Numbers can be either of the form P * Q or P3, where P and Q are primes.

• +4

By rhezo, history, 3 years ago, ,

Hello CodeForces community,

We are delighted to invite you to the Inter University Programming Contest organised by The LNM Institute of Information Technology – Jaipur, during the two day Techno-Management-Literary Fest Plinth'17 to be held from 18th–19th January, 2017.

There will be 3 rounds to decide the winner.

1. Online round that will be held on 6th January, 2017 on HackerEarth at this time.

2. First onsite round, that will be held at The LNM Institute of Information Technology, Jaipur. More details will be announced later.

3. Second and final onsite round, that will be held at The LNM Institute of Information Technology, Jaipur. More details will be announced later.

Problem Setters: rhezo. More setters will be added soon.

Prizes: Prizes worth INR 40,000!

Rules:

1. Team with maximum of 2 members is allowed.

2. Registration closes 2 hrs before the start of the contest. Registration link is provided below.

3. Plagiarism by any means will lead to immediate disqualification of the team.

Good luck and have fun.

Update: Due to clash with Codeforces Round #390, we have increased the time and duration of contest. It now starts at 11 pm IST and runs for 12 hours. There will be 8/9 interesting prolems :) Check the time in link above.

Update: Starts in about 8 hours!

Update: Starts in 39 minutes!

Update: The contest is over, hope you had a good one. I'll update the names of winners and those who qualified for onsite round soon. !

Update: We have started sending mails to all teams who are selected for the onsite round. You will get a mail in 1 to 2 days.

• +31

By rhezo, history, 3 years ago, ,

Can anyone explain the centroid decomposition solution?

• +3

By rhezo, history, 3 years ago, ,

I need to do integer division, that is floor of A/B. Eg: 5/2 = 2.

Now consider the modulo to be prime, multiplying A with inverse of B and taking modulo is wrong.

What I said above is true because , 6 * inverseOf(2) = 3. But 5 * inverseOf(2) is not equal to 2.

So how can I do this?

• +2

By rhezo, history, 3 years ago, ,

Hello Codeforces Community,

HackerEarth December Easy '16 will start at 9:30 pm on 1st December, 2016. The duration of the contest is 3 hours.

You will be given 6 algorithmic problems of various difficulty. All problems will have partial scoring, that is, points for each test case passed. Don't hesitate in scoring partial points in order to score as many points as possible if you want to get to the top.

Problems were prepared by me (rhezo). They have been thoroughly tested by Xsquare. Editorials written by me will be provided at the end of the contest. The problems are interesting and I hope you like the problemset. This is the first contest prepared by me, and I would love some feedback! I would like to thank belowthebelt who helped in preparation of the contest and making the contest in a good shape.

Prizes: T-shirts (for top 5 first year and second year students) and Amazon gift cards.

Good luck and have fun!

UPD: The contest starts in around 4 hours!

UPD 2: 15 minutes remaining!

UPD 3: Contest is live. All the best :)

UPD 4: Thanks for participating :)

Here are the top 5:

Any discussion on the problems is welcome. :)

• +67

By rhezo, history, 3 years ago, ,

I started learning Suffix Tree and understood the construction from this beautiful post. This is a very popular post and most of you must have learnt it from here. Does anyone have an implementation in C++ that follows what is written in that particular post?

• +20

By rhezo, history, 3 years ago, ,

Hi, I need some help in MINMAGIC problem on Codechef.

The problem statement in short: There are N segments, and Q queries. Each query is of the form (A, B). For each segment we need to choose a point on it, say X and find min(abs(A - X), abs(B - X)). We need to add this minvalue for all such segments and report the answer.

What I did: It is easy to find the answer for all segments whose right end point is less than A and whose left end point is greater than B. The minvalue is 0 for intervals that contain either A or B.

So the problem essentially boils down to this: Given 2 points (A, B) and some N segments all between A and B. For each segment we either choose its left end point or right end point and find the minvalue as above and add it for all the segments.

I don't know how to do this part. I am also not able to understand this solution by I_love_Tanya_Romanova. Also this solution is very clean but still can't understand the last part.

Can anyone help me in this? There are also some solutions by Treaps, I would appreciate if anyone can elaborate on that too.

• +8

By rhezo, history, 3 years ago, ,

He mentioned 2-3 lines down below to solve QTREE4 using HLD. I didn't understand it, can some explain it to me, please?

Here is the link to the problem.

I read elsewhere, that it can be solved by Centroid Decomposition too, but I need to understand the HLD approach.

EDIT: Now I'm wondering if he wrote those 2-3 lines under QTREE4 by mistake. Because just below it, he says that QTREE5 is a "bit hard", and it is almost the same problem (maximum -> minimum).

Anyone? :|

• +34

By rhezo, history, 4 years ago, ,

Can anyone suggest me some Treap problems on CodeForces? I want to solve those problems that have solutions and editorials open.

I just can't implement a bug free Treap and most of the problems of Treaps I know are from SPOJ. Also I can't find Treap tag in problemset, I think these problems are under Data Structures tag, but how do I find them?

• +30

By rhezo, history, 4 years ago, ,

The problem is that we need to put sum of all individual sub arrays in an array, and sort the array. Then there are at most 20 queries of the form [L, R], we need to report the sum between the indices L and R in the sorted array.

• +11

By rhezo, history, 4 years ago, ,

Given 2 sorted arrays with distinct elements, one sorted in increasing order and other sorted in decreasing order. Can we find the element which is present in both of them in O(logN) or O((logN)2)?

• -12

By rhezo, history, 4 years ago, ,

I was solving this problem. I have a function go, which returns a boolean true or false. When I replace "|" with "||", I get AC, otherwise I get TLE on test 6. I get AC with "||" and "or", but TLE with "|". Can anyone tell me the difference between the three?

• +14

By rhezo, history, 4 years ago, ,

Suppose we have a number X, and we need to find the modulus of it with N numbers, A1, A2, ..., AN.

Then is it true that if we know the modulus of X when divided by LCM(A1, A2, ..., AN), then we can know the individual remainders when X is divided by these numbers (A1, A2, ..., AN).

Can anyone give me a proof? And also the method of how to find the individual remainders.

I read this on a editorial on HackerEarth.

• +9

By rhezo, history, 4 years ago, ,

How is the test case given in the image for this problem correct? The only possible sets are {9,10,11} or {9,10,12}. None of them have exactly n/2 terms even or odd. The test case is : {4, 321, {6, 12, 2, 3, 9, 8, 10, 5}, {0, 3, 0, 0, 1, 0, 2, 0}}. Please help!

• +5

By rhezo, history, 4 years ago, ,

How to solve BAT2-SPOJ?

My idea is that you need to find all increasing subsequences from left (1->n), and all increasing subsequences from right (n->1). Since n can be <=100, this will take 2^100 time, which is too slow. How can it be done efficiently? Or am I thinking in the wrong direction?

• +1

By rhezo, history, 4 years ago, ,

How to solve this 552C ?

Can anyone help with this, I am not able to come up with the idea and editorial is not very descriptive. Thanks!

• 0

By rhezo, history, 4 years ago, ,

Hi, The LNM Institute of Information Technology, Jaipur is delighted to invite you to the "Inter University Programming Contest", during the three day Techno-Management-Literary Fest Plinth'16 to be held from 22nd – 24th January, 2016.

The contest shall be a great opportunity for students to whet their programming aptitude. This national level programming contest shall assess the intelligence through various rounds: the first round will be held online on January 3rd, 2016 and further onsite rounds will be held during Plinth'16 (22nd – 24th January, 2016).

The key details of IUPC'16 are as follows:

1. The first online round of the contest will be held on 3rd January-2016 (Sunday) 2 PM onward.
2. Contest duration will be 3 hours.
3. Team with maximum of 3 members is allowed.
4. Contest will be held on HackerEarth
5. Registration closes 2 hrs before the start of the contest. Registration link is provided below.
6. Plagiarism by any means will lead to immediate disqualification of the team.

Prizes worth INR 50,000/- for grabs!!

See you at the contest arena.

Good Luck!

• +8