radoslav11's blog

By radoslav11, history, 2 years ago, In English

We invite you to participate in CodeChef’s July Cook-Off, this Sunday, 3rd July , Rated for All. Time: 8:00 PM — 10:30 PM IST

Joining me on the problem setting panel are:

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. Hope to see you participating.

Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s March Lunchtime, this Saturday, 19th March, rated for all.

Time: 8:00 PM — 11:00 PM IST

Bangalore-based credit management app giant CRED is on board to hire candidates from the Chef's pool.

Who can apply?

Anyone with 1-3 years of experience in product development, architecture, and design. In short, 2019/2020/2021 graduates are eligible to apply.

Where is the application form?

Visit the March Lunchtime contest page to check the JD & application form.

Joining me on the problem setting panel are:

Prizes:

  • Top 10 global Division One users will get $100 each.

  • Top 25 Indian Division One coders to get Amazon Vouchers worth Rs. 1500 each.

Also, announcing Scholarship for CodeChef Certification in Data Structure & Algorithms — More than 100 Indian participants in Divisions 1, 2, and 3 will win scholarships for the CodeChef Certification exam (discounted prices). Scholarship criteria can be found in the respective contest pages.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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. Hope to see you participating.

Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s November Lunchtime, this Saturday, 27th November, rated for all.

Time: 7:30 PM — 10:30 PM IST

Joining me on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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. Hope to see you participating.

Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s October Lunchtime, this Wednesday, 27th October.

Time: 7:30 PM — 10:30 PM IST.

PS: Note the change in the date. The contest will be on a Wednesday this month instead of the usual Saturdays. The contest will be rated for all three Divisions. Joining us on the problem setting panel are:

Prizes:

Global Rank List:

Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR.

Indian Rank List:

Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.

However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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.

Hope to see you participating.

Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s September Lunchtime, this Saturday, 25th September.

Time: 6:30 PM — 9:30 PM IST. PS: Note the change in the timings.

The contest will be rated for all three Divisions.

Joining us on the problem setting panel are:

Prizes: Global Rank List: Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR. Indian Rank List: Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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.

Hope to see you participating. Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s July Lunchtime, this Saturday, 31st July.

Time: 6 PM — 9 PM IST.

The contest will be rated for all three Divisions. We also have a new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

Prizes: Global Rank List: Top 10 global Division One users will get $100 each. Non-Indians will receive the prize via money transfer to their account. Indian users will receive Amazon vouchers for the amount converted in INR. Indian Rank List: Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each. The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each. First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system. The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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.

Hope to see you participating. Good Luck!

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s June Cook-Off, this Sunday, 20th June, 9:30 PM — 12 AM IST.

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 us on the problem setting panel are:

Prizes:

The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Hope to see you participating. Good Luck!

Update: Problem POLYRT has been rejudged so that it also accepts solutions that considered the answer modulo $$$10^9+7$$$. We once again apologise for the inconvenience caused by the wrong statement.

Full text and comments »

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

By radoslav11, history, 3 years ago, In English

We invite you to participate in CodeChef’s May Cook-Off, this Sunday, 23rd May, from 9:30 PM — 12:00 AM IST

The May Cook-Off will have Junglee Games as the official contest recruiter! They are looking for SDE II & III Backend, SDE II & III Data, and SDE II Frontend roles for their fast-paced environment.

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:

Prizes:

The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Important Update

Did you create multiple usernames with CodeChef in the past? If yes, here's an update. We now have a portal where you get to see all your usernames so that you can delete all and keep the best one for you.

Hope to see you participating. Good Luck!

Full text and comments »

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

By radoslav11, history, 4 years ago, In English

We invite you to participate in CodeChef’s April Lunchtime in collaboration with Dream In Code — IIIT, Lucknow, this Friday, 30th April.

Time: 7:30 PM — 10:30 PM IST.

The April Lunchtime is going to have Amazon as the official contest recruiter! Amazon is hiring for Software Development Engineer 1, Software Development Engineer 2, and Support Engineer roles for its fast-paced environment.

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 us on the problem setting panel are:

Prizes:

The winners will receive certificates and CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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

Full text and comments »

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

By radoslav11, history, 4 years ago, In English

We invite you to participate in CodeChef’s April Cook-Off, this Sunday, 18th April.

Time: 9:30 PM — 12:30 AM IST. Please note the change in contest duration.

The April Cook-Off is going to have Amazon as the official contest recruiter! Amazon is hiring for Software Development Engineer 1, Software Development Engineer 2, and Support Engineer roles for its fast-paced environment.

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 us on the problem setting panel are:

Prizes:

The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

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

Full text and comments »

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

By radoslav11, history, 4 years ago, In English

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

  • Tester: Radoslav radoslav11 Dimitrov

  • Editorialist: Taranpreet taran_1407 Singh

  • Post-Contest Streaming: Rajarshi RestingRajarshi Basu

  • Statement Verifier: Jakub Xellos Safin

  • Mandarin Translator: Gedi gediiiiiii Zheng

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Fedor Mediocrity 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!

Full text and comments »

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

By radoslav11, history, 5 years ago, In English

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.

Update: made a new video about Li Chao trees. Here (https://www.youtube.com/watch?v=-StmrE2gY44&t=16s) is a link if someone is interested.

Full text and comments »

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

By radoslav11, history, 5 years ago, In English

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:

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
  • Contest link: http://bit.ly/COOK114-Codeforces
  • 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!!

Full text and comments »

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

By radoslav11, history, 5 years ago, In English

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

  • Contest link: https://www.codechef.com/JUNE19

  • 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 [email protected])

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

Full text and comments »

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

By radoslav11, 6 years ago, In English

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?

Full text and comments »

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

By radoslav11, history, 6 years ago, In English

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.

Full text and comments »

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

By radoslav11, history, 6 years ago, In English

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).

Full text and comments »

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

By radoslav11, history, 6 years ago, In English

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.

Thanks in advance! :)

Full text and comments »

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

By radoslav11, history, 6 years ago, In English

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 :)

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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?

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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.

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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

MikeMirzayanov

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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.

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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.

Full text and comments »

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

By radoslav11, history, 7 years ago, In English

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).

Thanks in advance :)

Full text and comments »

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