minimario's blog

By minimario, history, 6 weeks ago, In English,

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

Read more »

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

By minimario, history, 7 weeks ago, In English,

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!

Read more »

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

By minimario, history, 2 months ago, In English,

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

Read more »

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

By minimario, history, 3 months ago, In English,

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 (v1|v2|v3)&(v4|v5)&(v6), 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

Read more »

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

By minimario, history, 3 months ago, In English,

Hi :')

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

Relevant link: Official Website

Read more »

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

By minimario, history, 3 months ago, In English,

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

Read more »

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

By minimario, history, 3 months ago, In English,

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

Read more »

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

By minimario, 8 months ago, In English,

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(N2) (which is amazing, since single LCS problem is O(N2)), 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

Read more »

Tags lcs, dp
 
 
 
 
  • Vote: I like it  
  • +39
  • Vote: I do not like it  

By minimario, history, 9 months ago, In English,

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

Read more »

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

By minimario, history, 9 months ago, In English,

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

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

Read more »

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

By minimario, history, 10 months ago, In English,

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

Read more »

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

By minimario, history, 11 months ago, In English,

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!

Read more »

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

By minimario, history, 11 months ago, In English,

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

Read more »

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

By minimario, history, 12 months ago, In English,

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

Read more »

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

By minimario, history, 12 months ago, In English,

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)

Read more »

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

By minimario, history, 13 months ago, In English,

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

Read more »

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

By minimario, history, 19 months ago, In English,

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

Read more »

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

By minimario, history, 20 months ago, In English,

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

Read more »

Tags dp
 
 
 
 
  • Vote: I like it  
  • +14
  • Vote: I do not like it  

By minimario, history, 20 months ago, In English,

621A - Мокрая Акула и чётность

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 - Мокрая Акула и слоны

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 - Мокрая Акула и цветы

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 [li, ri]. How many numbers in this interval are divisible by p? Well, it is easier if we break the interval [li, ri] up into [1, ri] - [1, li - 1]. Since 1, 2, ..., x contains numbers divisible by p, the interval [li, ri] contains numbers divisible by p.

Now, consider two numbers and , with . Let ai be the number of integers divisible by p in the interval [li, ri], and define aj similarly. Now what's the probability that fi·fj is divisible by p? We can count the opposite: the probability that fi·fj is not divisible by p. Since p is a prime, this means neither fi nor fj is divisible by p. The number of integers in [li, ri] not divisible by p is ri - li + 1 - ai. Similar for j. Therefore, the probability fi·fj 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 - Крыса Квеш и сыр

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 xyz and xyz. We cannot directly compare them, 200200200 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 yz can still be 200200, 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. yz 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 xa 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 - Мокрая Акула и блоки

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.

Read more »

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

By minimario, history, 22 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -1
  • Vote: I do not like it  

By minimario, history, 23 months ago, In English,

Hello all :)

Can anyone give some idea or help me to solve this problem here?

It seems like straightforward SP problem, but the constraints are too large to be able to draw the graph. And I'm not really sure, how to use information of intervals to solve the problem.

So if anyone has some idea, please contribute!

Thanks,

minimario

Read more »

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

By minimario, history, 23 months ago, In English,

Today, I came back from some class, and I found, like 10 of my post, on the front page. I didn't think I had do anything wrong, perhaps I had accident click something that cause all blog post to be revive. That made me some sort of worried. I spent a while, asked some people, what may be I did wrong that cause so many of my past post to appear on the front page...

But then I check my email, and what I found?

I found, 13 messages of this form in my inbox~~! Then I realise, what has happened: Tanya_Romanova_loves_me comment on each of my old post, then he immediately delete all his messages... So this cause 10 of my post to be on Recent Actions, make me look like crazy man to revive so many post!! So, I guess there is down-side to delete comment function on Codeforces.

So, now, I hate this user. He has made attempt, make me look bad to the Codeforces community. Now I see why, even he make his username Tanya_Romanova_loves_me, Tanya Romanova still does not love him. I think nobody love him, nobody will ever love him~~~

Read more »

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

By minimario, history, 23 months ago, In English,

Hello, Codeforces:

I worked on problem 346B for a long time, and I could not come up with solution. Even when I read editorial and comments, the solution is still unclear to me. I know, it is KMP + DP, but I cannot see what KMP should be used on, DP transitions, etc. I know in the dp[i][j][k], i and j represent indices in str1 and str2, and k represents the longest match of the current subsequence and virus, but I cannot really get anything else.

I have worked for a few hours, but I don't have really much progress, and editorial/comments doesn't really help. So if anyone could give a clear explanation of this problem, it would be great and I would much appreciate it.

Thanks,

minimario

Read more »

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