Hi all,

I've recently come across this http://main.edu.pl/en/archive/pa/2010/fra. The problem statement is as follow: given up to n = 5000 disjoint intervals of the form [a_i, b_i], we let S be all the integers in these intervals (a₁, a₁ + 1, ..., b₁, a₂, ..., b₂, .., b_n Now, we have up to q = 500000 queries of strings, count the total number of times a string s will appear in the numbers of set S.

The only thing I can solve is if n = 1 or something, and I barely can see a way to approach this problem, especially since we can't iterate through all the intervals for each query.

If somebody could help, that would be great!

Best,

minimario

Hello again :)

Recently I was solving problem with integers a[i] which involved two operations a[i] //= 2 and a[i] -= 1. And I read that it is equivalent that when we are performing these operations, to consider a[i] as a double, transforming a[i] //= 2 to a[i] / 2, and then at the end taking the floor.

This is a little obvious, but nevertheless very surprising to me. Can someone prove it?

Hi :)

I've often seen many threads such as Grand Prix of Moscow, Siberia, Asia, etc.

But I've never figured out what these mean? From somewhere I have a vague idea, that they are problems from onsite contests that had nobody solve? But maybe that's something else, and my memory is lacking...

Best,

-minimario

Hi again,

For a few weeks I have tried to solve the task here (Toll). I have still not been able to come up with a solution, but I have garnered some ideas:

1. We will brute force over all 2^K subsets of edges to add.
2. Let's add the edges in Kruskal order, except with the K edges as weight -inf. (So if none of the K edges form a cycle, all of them will be added.) Now, all the edges (except the K edges) will be in EVERY MST. So now for each subset of edges we choose in step 1, we can calculate which edges will be in the MST in O(K) time. What I am not so sure about is how to find the length of the K edges.

If anyone could help me continue in this way, or provide a different solution, I would be very appreciative. I have read some blogs like these, but it's still not so clear to me as I don't know Chinese too well.

Thanks,

-minimario

Hi all,

I was solving this problem: Link. It's fairly easy, so if you don't really want to solve it, I'll go ahead and write the dp recurrence here:

A pretty obvious Convex Hull Trick (CHT) problem. But I'm getting TLE on the last test case. I opened some AC codes, and I didn't see much difference between our codes, so I'm wondering what makes mine so slow and the other one so fast!

436 ms code

My submission

If anyone has some insights, please comment (or PM me) with details!

(P.S.: If anyone has a fairly fast implementation of CHT that would like to challenge the 436 ms, go ahead and submit it :))

Thanks so much,

-minimario

Hi,

The task is something like this: given some files with N<=1000 triangles, piece them together to make a rectangle. (Tests are given beforehand, there's no TL).

I couldn't find the solution anywhere, and I'm shocked a task like this would have a solution at all. I can't even imagine any heuristics to use to solve this problem.

So does anyone have any ideas? :) For convenience, tests can be downloaded here

Thanks,

minimario

Hi,

Is there any program that can test a program on a large set of .in files against a large set of .out files? I heard about Ineffable, but I also heard it's really buggy.

Thanks!

Hi all,

Apparantly there is way to find SSSP from a single point, but I have tried a while and could not come with it. Can anyone help?

There is article here, but I have to buy it for USD$31.50.

So anyone can tell me about the algorithm for free?

Thanks,

-minimario

Hi, I've been struggling with this problem recently: BOI06_BITWISE

If you're lazy, I'll summarise: We have an expression in the form (v₁|v₂|v₃)&(v₄|v₅)&(v₆), which is AND of OR operators. Each variable appears once, and there are at most 100 variables. We have a range for each variable (range is contained in [0, 2e9]). Calculate the maximum value of the expression.

I've only got obvious ideas: check if 1st bit can be 1, then if so, check if 2nd bit can be 1, etc. But it's nothing substantial.

So if anyone has some ideas, that would be great :^)

Thanks!

-minimario

Hi :')

I'll keep it short...where can I upsolve Baltic BOI 2017?

Relevant link: Official Website

Hi all :')

I've recently solved 2017 Baltic BOI Day 1 #1 Political Development (D here

The algorithm to find the max clique here is as follows:

while (graph not empty):
     pick any vertex with min degree
     if the vertex and some subset of neighbors of it form a clique, check if it's larger than the ones we found so far
     remove the vertex

But I propose an alternate solution to finding max clique:

while (graph not empty):
     pick any vertex with min degree
     if the vertex and all neighbors of it form a clique, check if it's larger than the ones we found so far
     remove the vertex

I know it's wrong (because it's a polynomial time), but every time I try to find a counterexample, I can never do so.

Can someone provide a counterexample for my 2nd algorithm to the max clique problem (or prove it, then we have P=NP!)

Thanks,

minimario

Hello :')

Recently I've solving this: link, and I've read solution here.

When the solution says, we can infer the following recurrences:

A[n][i][j] = D[n-1][i][j-1] + D[n-1][i+1][j-1] +…+ D[n-1][n-1][j-1]
D[n][i][j] = A[n-1][1][j-1] + A[n-1][2][j-1] +…+ A[n-1][i-1][j-1],

Is this only valid for i<j? Because the solution says, that when renumbering, we remove i and relabel everything greater than i. But if i>j, then the recurrence will not be D[n-1][smth][j-1], but rather D[n-1][smth][j].

But if both A and D are valid for only i<j, then do the formulas really work? Because in the sum for A[n][i][j], we will add some D[n-1][i'][j'] such that i'>j'. Then the recurrence wouldn't really work.

Can anyone provide some explanation or clarification on this?

Thanks,

-minimario

Hi friends!

Recently one of my friends shared with me the following problem: Given 2 strings A and B of length n, for each substring (there are n(n - 1) / 2 of them) of A, find its longest common subsequence with B.

I heard it's solvable in O(N²) (which is amazing, since single LCS problem is O(N²)), but I'm not sure of the solution! It's a really short and amazing problem, but I couldn't come up with anything. If you guys could help, that would be great!

Thanks,

-minimario

Part I

Let me tell you,
I don't know what to do,
When I see three posts of mine,
Appear out of the blue...

Three posts of mine,
All there in a line,
I don't know why,
Someone just wanna die...

I'm not to blame,
It's all the same,
You'd think how can I accuse him,
If I don't even know his name...

He's Tanya_Romanova_loves_me,
It's false from what I see,
With his little comment "hack",
I see once again he's back!

It's his re-appearance,
Just a form of interference,
Even changed, his name,
Just like it's a game!

Tanya_Romanova_loves_me,
New account I see,
Even if you're my fan,
I wanna getcha a ban!

(Disclaimer: My poetry life ends here, back to CP...)

Hi, everyone!

Recently I was solving problem Plot Purchase from OI 15 and Parcels from OI 9. Then, Errichto shared with me a great article with a similar problem here.

Unfortunately, I am no pole, and even with Google Translate I was not able to understood the idea of the solution mentioned in the blog. Here is the problem mentioned in the blog: Given a N by N square grid of 0s and 1s, compute an array A[N][N], where A[x][y] denotes the number of rectangles of all 0s with height x and width y. The blog solves the task in O(N²).

I'm wondering if anyone (Polish or not), can understand the solution in this blog (I guess there's pseudocode at the end, but I couldn't understand it either) or invent a solution of your own to solve the task. I've thought about it for a few days, to no success.

Thanks!

-minimario

Hi, today I bring to you a question about something different, and perhaps completely useless anyways... :P

After user logicmachine's brilliant SSE solution to some problem (Link), I wonder how much SSE instructions really help program run speed. From the comments in that thread, it helps cut the speed by a factor of approximately 1/4, but is it really true?

I personally am not familiar with these things, but if they will really cut the speed of a program, that would be something curious to look into (maybe fit the TL with O(N^2) for N=1e5 ;))

Now you think, just get better, who needs these magic tricks, they're not even fair :P. But there are always some cases where I have some program, and it's barely over TL, and microoptimizations like these would (maybe?) bring it down to the TL. There's been some case where I've changed all the ints to shorts just to fit the TL... xD

So just for fun, if anyone can provide some light on SSE instructions (do they really help?), that would be pretty cool!

Thanks,

minimario

Hi guys!

Does anyone have some problems that are modifications of Dijkstra's algorithm? I feel that the scope of Dijkstra problems I can solve is pretty small. Here are the types of problems I am referring to... (these are kinda easy)

1. 715B - Complete The Graph (precisely the type I want)
2. 449B - Jzzhu and Cities (really easy, but still a Dijkstra with modif)
3. 59E - Shortest Path
4. 2nd Shortest Path Problem (Find the 2nd shortest path from A to B)

Please, if somebody can provide some more (more difficult) Dijkstra problems, that would be really helpful!

I was looking back on some previous contests, and I got to this problem.

I know the algorithm, which can be found on editorial: check each edge, and add min of subtree sizes when this edge is broken. But how do we extend this to find the pairs that we want to match? This algorithm gives the distance, not the pairs to be matched, and the editorial claims "not many modifications required".

However, I can't see it. If anyone could help, I would be really appreciated!

Thanks,

minimario

Here's the problem: here.

My submission got an AC, sure, but it ran in O(N^2 log(10^6)), and it took >2000 ms to run (even with optimised MOD). But there are so many submissions, which I think are the same complexity, which run so fast!

For example, just look at the first 2 here!

The first one, I don't understand, I think it uses some magic instructions (wtf, 100'000 instead of 100000 and mod_t!!?) (by ordcoder). The second one, by mmaxio is even in Java, and I'm almost completely sure it's the same O(N^2 log(10^6)) algorithm as everyone else.

So how did these people (or anyone else with some fast submission) get their runtime down so low?

Can someone elaborate?

Edit 1: Thanks to ned_chu, I've replaced the inverse modding to be linear. My new submission is here

Thanks,

minimario

Hi Guys!

I'm back, with another problem! Link! I have tried to debug for 3 days now to no avail :'( ... so I'd be a really happy if some of you could help :D

Anyways, on to the algo:

I first toposorted the data, and maintained 2 DPs:

dp[i][0] = minimum length to make all paths from topo[i] to topo[n] the same length without any tolls (on any path)
dp[i][1] = minimum length to make all paths from topo[i] to topo[n] the same length with at most 1 toll (on some path)

So the transition seems something like this:

dp[i][0] = dp[j][0] if all the d(i, j) + dp[j][0] are the same (j is a child of i)
dp[i][0] = MAX otherwise (impossible)

Now, for dp[i][1], let's consider j's that are children of i. For some j, if dp[j][0] is not MAX (it's possible to do), then let's add (dp[j][0], 0) to a vector. Otherwise, if dp[j][1] is not MAX, let's add (dp[j][1], 1). Now, let's sort the vector and find the maximum dp value. This represents the final length of the road. But for the other values, if the dp value is less than the final length and it came from a dp[some][1], then we stop, and dp[i][1] = INF. Else, dp[i][1] = the max dp value.

I have the code here, but it's wrong:

Code

I am aware that if there is a solution, the overall price for each path will be the longest path from start to end in the graph. I used this to try to debug, but it didn't help.

I have some test cases here, but the ones that fail are really big. (Also, I just completely ignored the "printing fares" part, because my calculation of the final path length is incorrect for many cases)

Hello,

I'm trying to solve some IOI 2016 problem, but I make submission, it's WA. Could somebody kindly post the test cases or tell me where I could find them?

Thanks,

-minimario

Hello all,

Today I will bring you some interesting problem: Oh, I forgot to mention I cannot solve it...Dx

So here is the problem. I guess I have some observation: that we have to consider the cycles in the graph. For example, in this graph here, we have 4 regions, and each region has an edge the other regions don't use. (Regions are coloured)

However, if I put new node 9 here, and try to colour like this:

But look it the problem here: if we try to use all 3 blue loops, then we cannot use the orange loop. So there is something tricky here.

So if anyone has any ideas or can provide some hints, I would really appreciate!

Thanks,

minimario

(P.S. If anyone want to continue solving Timus problem with me starting from 1077 and going down by difficulty, send me a message :))

Hello all,

Today I will bring you some interesting problem: Oh, I forgot to mention I cannot solve it...Dx

So here is the problem. Well, the first observation I have is that we can divide the numbers 1 to n into groups based on digit sum. Since two numbers with same digit sum have to differ by 9 or more, there can only be at most one number that does not change position after the sorting. So there are at most 81 different digit sum. (1 to 9 x 9)

So now there is new idea. This is part I am quite fuzzy with. It is not too bad to find the number of integers in the range 1...n with some digit sum k. (Some classical digit DP) But how this will help us? In particular, maybe there is a way to find the position of a number in a sorting in some good complexity, then apply some binary search method? I'm not sure, I have been working this problem for a while.

So if anyone has any ideas or can provide some hints, I would really appreciate!

Thanks,

minimario

621A - Wet Shark and Odd and Even

First, if the sum of all the numbers is already even, then we do nothing. Otherwise, we remove the smallest odd number. Since, if the sum is odd, we need to remove a number with the same parity to make the sum even. Notice it's always bad to remove more odd numbers, and it does nothing to remove even numbers.

621B - Wet Shark and Bishops

Let's start with two bishops (x1, y1) and (x2, y2). Notice that if (x1, y1) attacks (x2, y2), either x1 + y1 == x2 + y2 OR x1 — y1 == x2 — y2. So, for each bishop (x, y), we will store x + y in one map and x — y in another map.

621C - Wet Shark and Flowers

Let f(x) be the probability that the product of the number of flowers of sharks x and is divisible by p.

We want the expected value of the number of pairs of neighbouring sharks whose flower numbers are divisible by p. From linearity of expectation, this is equal to the probabilities that each pair multiplies to a number divisible by p, or f(0) + f(1) + ... + f(n). (Don't forget about the wrap-around at n)

Now, for each pair of neighbouring sharks, we need to figure out the probability that their product is divisible by p. Consider an interval [l_i, r_i]. How many numbers in this interval are divisible by p? Well, it is easier if we break the interval [l_i, r_i] up into [1, r_i] - [1, l_i - 1]. Since 1, 2, ..., x contains numbers divisible by p, the interval [l_i, r_i] contains numbers divisible by p.

Now, consider two numbers and , with . Let a_i be the number of integers divisible by p in the interval [l_i, r_i], and define a_j similarly. Now what's the probability that f_i·f_j is divisible by p? We can count the opposite: the probability that f_i·f_j is not divisible by p. Since p is a prime, this means neither f_i nor f_j is divisible by p. The number of integers in [l_i, r_i] not divisible by p is r_i - l_i + 1 - a_i. Similar for j. Therefore, the probability f_i·f_j is not divisible by p is given by . Therefore, the probability it is can be given by . Now, just sum over this for all i.

621D - Rat Kwesh and Cheese

The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for competitors though. Especially the part about taking log of a negative number.

We need a way to deal with x^yz and x^yz. We cannot directly compare them, 200²⁰⁰²⁰⁰ is way too big. So what we do? Take log! is an increasing function on positive numbers (we can see this by taking , then , which is positive when we are dealing with positive numbers). So if , then x ≥ y.

When we take log, But y^z can still be 200²⁰⁰, which is still far too big. So now what can we do? Another log! But is it legal? When x = 0.1 for example, , so we cannot take another log. When can we take another log, however? We need to be a positive number. y^z will always be positive, so all we need is for to be positive. This happens when x > 1. So if x, y, z > 1, everything will be ok.

There is another good observation to make. If one of x, y, z is greater than 1, then we can always achieve some expression (out of those 12) whose value is greater than 1. But if x < 1, then x^a will never be greater than 1. So if at least one of x, y, z is greater than 1, then we can discard those bases that are less than or equal to 1. In this case, . Remember that , so . Similarly, .

The last case is when x ≤ 1, y ≤ 1, z ≤ 1. Then, notice that for example, . But the denominator of this fraction is something we recognize, because 10 / 3 > 1. So if all x, y, z < 1, then it is the same as the original problem, except we are looking for the minimum this time.

621E - Wet Shark and Blocks

First, let us build an X by X matrix. We will be applying matrix exponentiation on this matrix. For each modulo value T from 0 to X — 1, and each value in the array with index i between 1 and n, we will do: matrix[T][(10 * T + arr[i]) % X]++. This is because, notice that for each block we allow one more way to go between a modulo value T, and (10 * T + arr[i]) % X. We are multiplying T by 10 because we are "left-shifting" the number in a way (i.e. changing 123 -> 1230), and then adding arr[i] to it. Notice that this basically simulates the concatenation that Wet Shark is conducting, without need of a brute force dp approach.

Hi, I am back to blue...

So this is regard the problem Lipshitz Sequence. I think I have solution to the problem with complexity, but it is getting TL. So I wonder, it is my complexity calculation that is wrong, or it is something with the implementation? For reference, code is here.

What I did, is first I took array of differences, for example 4 1 2 -> 3 1. Then, problem is basically asking for sum of minimum of all subarrays. Then, query [i, j] maps to the sum of minimum of subarrays of [i-1, j-2].

I'll demonstrate this method in first example, then it may be clearer for you to understand it :) Let's take first sample and fir st query.

10 4
1 5 2 9 1 3 4 2 1 7
2 4
...

First we take the difference array: 4 3 7 8 2 1 2 1 6. Then, since i=2, j=4, we take sum of minimum of subarrays of [1, 2], which is 3 7. Now it's clear, subarrays are [3], [3, 7], [7], sum is 3+7+7=17. So it's clear that problem has been transformed.

For each number, we can count how many times it is counted. Say we are considering subarray x...y. We will consider how many times maximum is added to the sum. Say a maximum occurs, the position pt (variables same as in the code, look at f function). In the code, f(x, y) find the answer for subarray x...y. So how many subarrays that maximum at position pt is included in? Well, if we pick any index x...pt and any index pt...y, it will be included. Therefore, there are a total of (pt - x + 1) * (y - pt + 1) occurrences of element at position pt. Then, we can break the subarray into two smaller subarrays (divide and conquer method) x...pt-1 and pt+1...y and recurse on those.

The querying maximum (number and index) from i to j, inclusive can be found using a segment tree in O(log n).

So, total complexity for each query satisfies T(N) = 2T(N/2) + O(log N), solution is O(N). (If you don't believe me, look here and scroll all the way down :P)

So total complexity should be O(N log N + NQ). (Initial N log N for segment tree build). But if this is right, why it is giving the TL verdict?

Thanks,

minimario