Franklyn_W's blog

By Franklyn_W, history, 4 years ago, In English

Hi,

Today I wanted to read the accepted codes for educational codeforces round 2, by going here: http://codeforces.com/contest/600/status. However, I couldn't find anything, since it seems like I can't access any of the code.

Read more »

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

By Franklyn_W, history, 4 years ago, In English

Hi Codeforces,

I'm currently working on a problem related to network flows. Does anyone know how to implement constraints of the following type into a system?

Edges 1 and 2 go into the vertex, and have capacity one. Edges 3 and 4 go out and have capacity one. How can one force a constraint to the effect of (edges 3 and 2 can't have a sum of flows greater than one)? 

UPD: I should note the context involves min-cost flow, so perhaps we can leverage the costs of the edges.

Read more »

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

By Franklyn_W, history, 5 years ago, In English

Hi all,

For a research project I am conducting, I have come across an algorithms problem. I would like a solution which runs in at most 1 hour or so. Can someone give me an idea? Thank you!

Find all permutations a such that a has 28 elements and:

a has 8 cycles of length 3 and 4 fixed points b is ({1,2,3...,7}, {8,9,10...,14}, {15,16,17...,21}, {22,23,24,...,28}) cycle structure a * b has 14 cycles of length 2.

Read more »

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

By Franklyn_W, history, 5 years ago, In English

Problem 629D - Бабай и пирог на день рождения asks for the heaviest strictly increasing subsequence of a set of volumes. When I saw this problem (in practice) I immediately recognized that this was probably a well-known problem, so I looked up code. I found some code from StackOverflow, but it occured to me that this code only found the heaviest nondecreasing subsequence. Not willing to change the code too much, I came up with the following idea. If taking the array one by one is like:

l = []
for r in range(n):
    k = int(input())
    l.append(k)

then in order to make the heaviest strictly increasing subsequence roughly equal to the heaviest nondecreasing subsequence, do something along these lines. This should work, because the epsilon is small enough such that the relative order should not be changed, but equal terms will have a difference: terms which come closer to the front will be ever so slightly larger than equal terms closer to the end.

l = []
for r in range(n):
    k = int(input())
    l.append(k + (n-r)*0.000001)

I submitted this idea, 16347971, but it did not succeed. Why? Because floats do not have sufficient precision, and the numbers in the array can range from 1e15 to 1. Hence, this will have negligible difference under this. The naive way to fix this is just to increase the precision of the numbers, like this:

l = []
for r in range(n):
    k = int(input())
    l.append(Decimal(k) + Decimal((n-r)*0.000001))

I tried this too, but it turns out that we in fact get TLE when we try this, even when we water down the precision: 16348275. And who can blame this? We clearly have to undergo a paradigm shift, because this is bad: since the numbers change so much: a fixed error for each term is not acceptable. How about instead of an absolute error, we use a relative error?

This would look like:

l = []
for r in range(n):
   k = int(input())
   l.append(k + (n-r)*k*0.00000001)

The reason this works is that equal terms are still larger when they come at the front. However, this method has its own flaws: for instance, there is a chance that if k is large enough, this term will become larger than k+1. Furthermore, the sum of all terms in the subsequence will have a significant difference with the original value. This can be fixed, however, by using a small enough epsilon, as seen below:

l = []
for r in range(n):
   k = int(input())
   l.append(k + (n-r)*k*0.00000000001)

Surely enough, this gets AC! 16348026

Hopefully this brightened up your day!

Read more »

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

By Franklyn_W, history, 6 years ago, In English

http://codeforces.com/predownloaded/db/71/db71b835b400d96d1a046c43b07dccaf4d297a23.png

How did this even happen?

It says that the constraints are 0 ms and 0 MB?

Read more »

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

By Franklyn_W, history, 6 years ago, In English

Hi all,

Today I was unable to solve this problem: http://usaco.org/index.php?page=viewproblem2&cpid=213. My code is as follows, exactly following the official solution, yet, WA 7, 8, 9.

http://ideone.com/cV0eKj is my code. Thanks!

Read more »

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

By Franklyn_W, 7 years ago, In English

The contribution Leaderboard says that user Endagorion has contribution 135, but clicking on his page says that he had contribution 136. Why does this occur?

In fact, now it is one hundred thirty seven

EDIT: It has finally been updated!

Read more »

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