radoslav11's blog

By radoslav11, history, 7 weeks 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 winners@codechef.com)

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

Read more »

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

By radoslav11, 3 months 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?

Read more »

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

By radoslav11, history, 9 months 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.

Read more »

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

By radoslav11, history, 11 months 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).

Read more »

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

By radoslav11, history, 13 months 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! :)

Read more »

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

By radoslav11, history, 14 months 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 :)

Read more »

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

By radoslav11, history, 15 months 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?

Read more »

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

By radoslav11, history, 17 months 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.

Read more »

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

By radoslav11, history, 17 months ago, In English,

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

MikeMirzayanov

Read more »

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

By radoslav11, history, 19 months 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.

Read more »

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

By radoslav11, history, 23 months 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.

Read more »

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

By radoslav11, history, 2 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 :)

Read more »

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

By radoslav11, history, 2 years ago, In English,

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.

Read more »

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

By radoslav11, history, 2 years ago, In English,

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.

Read more »

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

By radoslav11, history, 2 years ago, In English,

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 .

Read more »

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

By radoslav11, history, 3 years ago, In English,

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!

Read more »

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

By radoslav11, history, 3 years ago, In English,

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

Read more »

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

By radoslav11, history, 3 years ago, In English,

Hello!

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

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

Read more »

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

By radoslav11, history, 3 years ago, In English,

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

Read more »

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

By radoslav11, history, 4 years ago, In English,

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:

http://codeforces.com/contest/611/submission/15127498 — AC
http://codeforces.com/contest/611/submission/15126396 — TL11

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.

Read more »

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

By radoslav11, history, 4 years ago, In English,

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

Read more »

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

By radoslav11, history, 4 years ago, In English,

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

Read more »

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

By radoslav11, 4 years ago, In English,

On 25-26 April The Bulgarian National Olympiad in Informatics took place. Here are the tasks:

Junior Task 1:

There is a sequence of stones numbered 0,1,...,10^9 from left to right respectively. A chameleon is placed on the stone with number 0. There are N (1<=N<=10^5) flies on the other stones and more than one fly can share the same stone. To reach the i-th stone with his tongue, the chameleon loses i unities of energy. When he reach the i-th stone, he eats one of the flies on the stone. The flies on stones 1,2,...,i-1 moves one stone to the left, the flies on stones, i+1,... moves one stone to the right and the remaining flies on the i-th stone don't move. Given the number of flies N and their positions on the stones 1<=a1,a2,...,aN<=10^9, you are to find the minimum energy the chameleon will lose in order to eat all flies.

Junior Task 2:

Given a dictionary of consisting of N (1<=N<=2000) words with length up to 20 lowercase letters and a string with up to 100 lowercase letters. It's known that the string is a sentence consisting of words from the dictionary written without spaces, you are to find the minimum number of words we need to use in a sentence so that writing it without spaces results in the given string. You need to print the actual sentence. If there are multiple solutions, print the one where the first word have minimum length. If there are still multiple solutions, print the one where the second word have the minimum length and so on and so on.

Junior Task 3:

Just a short description of it. You need to write a compiler for a programming language called "EASY". The language uses 10 variables R0,R1,...,R9 and integer numbers from 0 to 999 inclusively. R0 is the value that the main function is called with and R9 contains the returning value. There are operations like MOV, ADD, SUB, MUL, DIV, MOD that you need to implement with the given variables or integer numbers from 0 to 999 inclusively. There are operators IFEQ(if equal), IFNEQ(if not equal), IFG(if greater), IFL(if less), IFGE(if greater or equal), IFLE(if less or equal) and an ENDIF operator for each of them. There are operators CALL and RET. CALL calls the main function recursively with a new value and RET returns a value. All R0,...,R8 are local, only R9 isn't since it stores the answer(the returned value). So it is all about coding and having strong nerves.

Senior Task 1:

In this task you are given a string. You can mark a prefix of it and then by clicking a button your mark moves to the next occurence of the marked substring that does not overlap the current marked part. If there is no such an occurence, the mark stays at its place.

Some examples:

1 2312312312 -------> 123 1 2312312

12 312312312 -------> 123 12 312312

123 12312312 -------> 123 123 12312

1231 2312312 -------> 123123 1231 2

12312 312312 -------> 123123 12312

123123 12312 -------> 123123 12312

Your task is to find the length and the starting position of the longest substring such that after pressing that button the marked part to move.

In 15% of the tests 0 < n < 1000

In 25% of the tests 999 < n < 10000

In 60% of the tests 9999 < n < 1000000

Where n is the length of the string.

Senior Task 2

You are given a numeric system in base N where the first digits are: 1, 2, 3, ... N. Let them be c1, c2, c3, ... cN. You can write only 2-digit numbers. The task is to find the number of strictly increasing sequences in witch every digit is written twice and every number's first digit is less than its second. For example if N = 3 there is only 1 sequences of this type: c1c2, c1c3, c2,c3. Find the answer modulo 987654321.

Senior Task 3

You are given a matrix NxM. You need to delete all elements in the table. You can delete any side of the matrix. This operation will cost you the maximum number in the row/column. You need to find the minimum cost to delete the matrix. Example:

Input:

3 4
6 8 7 2
3 0 9 1
4 2 9 1

Output:

24

Explanation: One way you can delete the matrix for minimal cost: up, right, right, left, down

8 + 1 + 9 + 4 + 2 = 24

Read more »

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