By radoslav11, history, 11 months ago,

We invite you to participate in CodeChef’s May Lunchtime, this Saturday, 30th May, from 7:30 pm to 10:30 pm IST.

3 hours, 5 problems.

We will also be hosting a live problem discussion sessions where our panelist, RestingRajarshi will discuss the Lunchtime problems. Find more details here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining me on the problem setting panel are:

• Setters: Vivek Vivek1998299 Chauhan , Raj Khandor , Vinit Vitz Solanki , Shahjalal YouKn0wWho Shohag , Ritesh Gupta

• Admin : Teja teja349 Vardhan Reddy

• Editorialist: Taranpreet Discombobulated Singh

• Post-Contest Streaming: Rajarshi RestingRajarshi Basu

• Statement Verifier: Jakub Xellos Safin

• Mandarin Translator: Gedi gediiiiiii Zheng

• Vietnamese Translator: Team VNOI

• Russian Translator: Fedor Fedosik Korobeinikov

• Bengali Translator: Mohammad solaimanope Solaiman

• Hindi Translator: Akash Shrivastava

Prizes:

Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

• +95

By radoslav11, history, 11 months ago,

Hi!

So recently I saw that quite a lot of people have created YouTube channels related to competitive programming and as I had nothing to do today an idea of me doing the same came to my mind. So as I wanted to do something that might be just a bit useful, I decided to do a tutorial on Virtual/Auxiliary Trees as my first video (which is a concept that can be used in some problems related to trees). I chose this as a topic, because I couldn't find a decent tutorial on it.

Here is a link to the video and my channel. I hope you'll enjoy it.

Any feedback will be appreciated, even if it's in the lines of "pls don't ever create a new video". Also if there are some concepts that you might be interested in me covering, feel free to comment/message me. Actually, any video ideas will be very much appreciated!

Right now I'm thinking of covering Burnside lemma (with problems) as I couldn't find a good tutorial on that too. Also I will probably upload some screencast with commentary.

• +218

By radoslav11, history, 15 months ago,

Greetings Codeforces Community! CodeChef invites you all to join us at CodeChef’s January serving of the Cookoff. Crafted out of the very best ideas, our set of curated problems will take your codebuds for a delightful trip. This 2.5 hours contest will have five challenging problems.

Further the January Cookoff will be the perfect opportunity to improve your CodeChef ratings and rankings. Also if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas.

I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Setters: Commando_ (Ahmad Salah), adarshagr8 (Adarsh Agrawal), KMAASZRAA (Kasra Mazaheri), chemthan (Nguyen Ngoc Trung), rishup132 (Ritesh Gupta), KharYusuf (Yusuf Kharodawala)
• Editorialist: raja1999 (Raja Vardhan Reddy)
• Statement Verifier: Xellos (Jakub Safin)
• Admin: teja349 (Teja Vardhan Reddy)
• Mandarin Translator: UoA_ZQC (Qingchuan Zhang)
• Vietnamese Translator: Team VNOI
• Russian Translator: Fedosik (Fedor Korobeinikov)
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava

#### Contest Details:

• Start Date & Time: 19th January 2020 (2130 hrs) to 19th January 2020 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 performers in Global and top 10 performers in the Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344 Good Luck!
Hope to see you participating!!
Happy Programming!!

• +53

By radoslav11, history, 22 months ago,

Greetings Codeforces community!

The June Long Challenge, sponsored by ShareChat, is almost here and brings with itself happy programming tidings. Our curating chefs have been hard at work in their kitchens, and have created an engaging array of problems for you to crack.

Everyone is invited to participate in this long contest, starting from 7th June to 17th June. Here’s your chance to put your superior programming skills to test, to compete with the best of the best, while working hard to improve your ratings and climb up the ladder to glory.

And if that weren’t enough, ShareChat — India’s fastest growing social network — is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Visit the contest page for more details.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

#### Contest Details:

• Start Date & Time: 7th June 2019 (1500 hrs) to 17th June 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

• Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

• Prizes: Top 20 performers in Indian category and top 10 performers in Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. Know more here: https://goodies.codechef.com/ (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!
Happy Programming!!

• +82

This year's Bubble Cup first round ended recently. The marathon/challenge problem was GUESSN5 from SPOJ. What were your approaches?

Also does someone know how the checker was created, as trying all possible lies would be too slow?

• +32

By radoslav11, history, 2 years ago,

Hello!

During yesterdays round I solved (or tried solving) problem D with suffix automaton — it's very simple after copying SA's code (link to code). But unfortunately it TLE like the majority of solutions. So I just thought "Eh, I guess solutions aren't supposed to pass". But today I actually realized that I'm not sure if my solution is actually — in the part where we create the "clone" node, we copy the adjacent nodes of the given node to the adjacency list of the clone. This might actually result in O(Σ) complexity and if this happens many times the solution will obviously be slow. But I cannot find a sample, where we happen to copy large adjacency lists many times. Can you help me with that?

So generally my question is:

If we use suffix automaton on large alphabet what is the worst time complexity?

PS: We can achieve if we use persistent trees to keep the adjacency lists, but I find this to be a very ugly approach.

• +34

By radoslav11, history, 3 years ago,

Hello!

IOI 2018 is just around the corner and so I decided to propose the push-up challenge. The Bulgarian team has been doing it for the past couple of years and in a way it is very fun. If someone isn't familiar woth the rules, he can check the blog post of this challenge from 2015 (link).

So feel free to share your coefficients if you are going to join!

PS: Although I suggest you do the push-up challenge, if you are too lazy for it (and you can legally drink), you can do the drinking challenge instead (the rules are similar but with drinking C ml of 40% alcohol instead).

• +98

By radoslav11, history, 3 years ago,

Hello!

Recently I relearned link cut trees and now I'm curious how to do subtree updates/queries as I have seen comments in the past that it's possible. So can someone share how to do it and also can we perform both subtree and path queries/updates simultaneously?

Also can someone share some interesting (and hard) problems with link cut trees which you have encountered and liked.

• +16

By radoslav11, history, 3 years ago,

Hello!

Bubble Cup 2018 Round 2 just finished, so I decided to ask about a correct solution problem NEO. I guess a lot of people passed it in with the C++ pragma optimizations or with some greedy optimizations. My team also passed it like that.

In this blog I'll share my idea. If someone has solved it in a similar way I will really appreciate if he shares his code because honestly the idea is really annoying to implement. If anyone has another solution, which is better than I will really love to know the idea.

So the solution I had in mind is or depending how we implement our query. First we will have the standard DP: dpi = maxj < i(dpj + sumi * i + sumj * j - j * sumi - i * sumj) which can be reformed to dpi = sumi * i + maxj < i((dpj + sumj * j) + ( - j * sumi) + ( - i * sumj)). Well we can still reform this equation the the following: .

Now basically we only need to implement a data structure for the following operations:

1. Add a vector to our DS.

2. Given a vector, find the one with the largest dot product, when multiplied with it.

I found a paper which claimed that the following operations can be implemented with a 3D convex hull and another one which claimed that these operations can be converted to dynamic furthest point search, but unfortunately I cannot find the latter again (this happens when you do not bookmark anything). Also both presented data structures/algorithms were really annoying to implement.

So has anyone solved this problem in a legit way and if yes, can he share his solution. Thanks in advance :)

• +50

By radoslav11, history, 3 years ago,

Hello,

A friend of mine gave me and a couple of friends a problem which he couldn't solve. In the end, it turned out he misread it and it appeared to be quite easy. But now I'm curious if there is a polynomial solution to the first problem. Here is the problem statement:

We have 2 sequences a and b. We can preform a operation set(l, r, v) on the first sequence. By applying it, all elements of a in the range [l;r] become equal to v. The cost of each operation depends on the length of the interval we apply it to. In other words, we have an array c, such that the cost of operation set(l, r, v) is c[r - l + 1]. The question is:

What is the minimum sum of costs to convert sequence a to sequence b.

Note that there are no constraints for the costs. For example c[1] might be greater than c[5] and less than c[7].

We can get rid of sequence a by doing this dp:

DP[l][r] — answer for subarray [l;r].

We try fixing l ≤ mid ≤ r, such that a[mid] = b[mid].

We make DP[l][r] = min ( DP[l][mid-1] + DP[mid + 1][r]).

Now we are left with one more case — we cover every element of a with at least one set() operation. Then we don't care about array a. If we have created another array P[l][r] such that this value is equal to the minimum cost to create the corresponding subarray of array b, then we simply need to preform DP[l][r] = min(DP[l][r], P[l][r]) and we will solve the problem.

So does anyone have an idea about the solution of the problem or is anyone able to prove that the problem has no polynomial solution?

• +46

By radoslav11, history, 3 years ago,

Just a reminder that the registration for this year's deadline24 is going to close in about 4 days. If you are going to participate you should register in the next few days.

The qualification round will be held next Sunday (February 25, 2018, 9:00-14:00 (CET)). Let's discuss the problems here after it.

UPDATE: The registration will end in about a day and 4 hours.

• +31

By radoslav11, history, 3 years ago,

When one tries to access problemset or any past contest, this shows up:

MikeMirzayanov

• +56

By radoslav11, history, 3 years ago,

Hello,

During the last educational round I had a solution with treaps for which I cannot construct a sample to make it TLE. It seems to me that the solution is or something like that but I cannot prove it. So can someone either provide a counter sample or help me prove it. Thanks in advance!

Here is a link to the submission.

• +63

By radoslav11, history, 4 years ago,

Hello everyone!

I have been collecting (from different places) and writing codes for some time now and I decided to share them with you. Here is a link to the coding library which I have been using.

The coding library contains Online MO's algorithm, different variations of segment trees, Dynamic Convex Hull trick, variations of LiChao segment tree and many other.

Tomorrow I'll probably add my implementations of Link/Cut tree, K-D tree, some other dp optimizations and persistent treap.

I really hope that the coding library will be helpful for some of you.

• +213

By radoslav11, history, 4 years ago,

Hello.

Today I was looking the problems from AtCoder Grand Contest 18. In problem D you were asked to find the length of the largest Hamilton Path in a complete graph with edges between two vertices equal to the length between these two vertices in a given tree. In the problem you need to find just the length of the path and the solution which I found to the problem can do this. But unfortunately it can just give the length of the path, not the order in which we visit the vertices (my solution is similar to the one in the editorial). So is there a solution with which the order we visit the vertices is easily recoverable (well actually even if it's not easy I would appreciate if you share your idea) and also is still fast enough (something like or faster).

• +4

By radoslav11, history, 4 years ago,

Hello!

My question is simple. Can someone give me a test sample for maximum matching in bipartite graphs on which Kuhn's algorithm preforms badly (something like O(N * M) in time). Thanks in advance.

• +30

By radoslav11, history, 4 years ago,

Hello!

Some time ago I thought of the following problem:

We have a bracket sequence with length n (n ≤ 105) and we have q (q ≤ 105) queries for finding the length of the longest correct bracket substring (with consecutive elements) in a interval [l;r] (1 ≤ l ≤ r ≤ n).

Sample:

6
((()()
3
1 6 -> Answer is 4 (substring from 3rd to 6th position)
1 2 -> There is no correct bracket substring so the answer is 0
1 4 -> Answer is 2 (substring from 3rd to 4th position)

So I found a solution with MO's algorithm but I am curious if there is an online solution. So if anyone has one, please share it. Thanks in advance.

• +20

By radoslav11, history, 4 years ago,

Hello everyone!

Today I was solving a problem and I reduced it to finding a maximum of a function. So in short what I need is the following:

, where M, a, b ≤ 109.

It's obvious that iff , but I cannot find an easy way to get the maximum if . I will appreciate any help on the problem.

PS: a, b and M are given as queries so I need an algorithm to answer up to 105 queries.

UPDATE: It's actually pretty simple. actually has values of form . Then it's obvious that the solution will be .

• +40

By radoslav11, history, 4 years ago,

Hello everyone!

I was solving a problem (from a Bulgarian competition) which is about the game Lights Out — https://en.m.wikipedia.org/wiki/Lights_Out_(game). In the problem you are given a NxM table (N*M<=1000) — the initial configuration of the game. You whant to make all the cells equal to zero. You should print a way to do this.

The problem can be solved with meet in the middle and bitmask dp, with the given constraints. Another way is using Gauss elimination modulo 2 with N*M equations for each cell. But this approach is O((N * M)3). It actually can be reduced to with a bitset.

In the editorial of the problem it is said that there exists a solution for much larger data — N,M<=500, using Gauss elimination but it isn't explained. If someone knows it can he/she explain it. I will appreciate your help!

• +18

By radoslav11, history, 4 years ago,

I decided to look the new blog posts on codeforces. I logged in and saw that I'm a candidate master but with 1899 rating. After failing yesterday's contest because of bug in my Div2 E, I ended 243. So my rating increased by +7. But it was shown that I'm expert with 1906 rating.

So now what is my current rating 1899 or 1906, because I'm curious if I can participate in the today's codeforces round.

PS: I also saw that a couple of my submissions are gone (the last ones).

• +28

By radoslav11, history, 5 years ago,

Hello!

Today, at 08:00 UTC will be held Deadline24's qualifying round.

Let's discuss problems here, after the contest of course!

• +26

By radoslav11, history, 5 years ago,

Hello!

I was solving problem Minxor from second day of RMI 2014. In short the problem is:

You have 3 types of queries.

1 x -> inserts x into the set
2 x -> deletes x from the set
3 -> asks for the smallest xor of any two numbers in the set

I solved the problem offline using a trie + divide and conquer. My solution is similar to link. Again in short: compressing all updates as "number x appears from time I to time J". Here is the code. The complexity is O(M * log(M) * 32);

So my question is:

Is there a solution which runs faster than that or/is online. Thanks in advance :)

• +9

By radoslav11, history, 5 years ago,

While solving Goodbye 2015, E i was getting TL on test 11. Now after the contest I decided to see what was the problem.

After some debugging I found that when you do lower bound on an empty set it gives TL:

The only difference is if(s.size() == 0) break;

So I want to ask if there are similar issues with the std::set.

PS: This was a good lesson for me. Next time I wont try debugging one solution for 2 hours and will solve the other problems.

• +8

By radoslav11, history, 5 years ago,

Hello codeforces,

I was solving this problem:

You are given a graph, and you have to answer queries of type:
1) Delete edge from U to V
2) Add edge from U to V
3) See if vertexes U and V are in the same connected component.

I couldn't come with an online solution, but I think I found an offline one.

So first I compress all queries of adding or removing and edge as: edge from U to V is available in time [i; j], where i is the time of adding and j is time of removing. Now we can do divide and conquare with dsu. This will be like that:

Rec(L, R, dsu)
{
Look for all queries that are q.L <= L and R <= q.R
([L; R] lies in [q.L; q.R]) and add unite q.U and q.V in dsu

IF L == R -> if query[L] is of type 3 then answer it and stop (and also undo changes to dsu).

Mid = (L + R) / 2;
Rec(L, Mid, dsu);
Rec(Mid + 1, R, dsu);

Undo changes to dsu
}


So this solution is O(M*logM*Cost_of_dsu). But the problem is in the DSU (the undoing of operations). I couldn't find how to do persistent DSU or DSU with restoring/undoing/backtracking. So if someone knows how to do this I will really appriciate if he helps! :)

PS: By DSU I mean disjoint set union

• +11

By radoslav11, history, 5 years ago,

Hello codeforces,

I was solving IZHO problems from past years but I couldn't solveIZHO 201problem E — "K blocks" (link; the second problem). I wrote the O( N * N * K ) dp solution, but I'm not sure how to reduce it to O( N * K ). I tought of Convex hull trick, but unfortunately i don't know how to apply it.

So can someone share his solution? Thanks ;)