dcordb's blog

By dcordb, 4 months ago, In English

We (the setters) hope you liked the problems. Here is the editorial:

Tutorial is loading...
C++ solution
Python solution

Problem idea: dcordb

Solution idea: dcordb and Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: marX and Devil

Tutorial is loading...
C++ solution
Python solution

Problem idea: Devil

Solution idea: Devil and dcordb

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: marX

Tutorial is loading...
C++ solution

Problem idea: gilcu3

Solution idea: gilcu3 and marX

Tutorial is loading...
C++ solution

Problem idea: Devil

Solution idea: Devil and antontrygubO_o

Tutorial is loading...
C++ solution

Problem idea: marX

Solution idea: marX and Devil

Read more »

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

By dcordb, history, 2 years ago, In English

Given an array with N elements you need to choose exactly K non-consecutive elements from it such that the sum of the elements will be minimum.

Constraints:

  • 1 ≤ N ≤ 105
  • 1 ≤ K ≤ N
  •  - 109 ≤ ai ≤ 109

I know how to solve this in O(N·K) by using DP(i, m) =  minimum sum that can be obtained in prefix i taking exactly m elements.

Can it be done faster than that? Thanks beforehand.

EDIT: I had an idea that was do a binary search on the answer, let's say answer should be less or equal than x, then for a prefix i the values that m can take so that DP(i, m) ≤ x are consecutive so I transformed the DP to DP(i) =  range of the valid m values. But the problem with this is how to merge DP(i - 1) with DP(i - 2) in time.

Read more »

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

By dcordb, 3 years ago, In English

Hello.

I was doing this problem (problem G) from NEERC 2008.

The problem basically says that you are given N points and in a minute all the points connect to all the others points, forming segments, now you choose the center of each segment as new points an delete the old ones. You have to say the time where one point is generated by at least 2 segments or say is 0 if it never happens.

I realized that if N ≤ 3 the answer is 0, if two different segments cuts in the middle then the answer is 1. And by looking to the solutions I saw that the answer is 2 in other case. Why does this happen, can anybody proof this?

Thank you.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dcordb, history, 3 years ago, In English

Hi.

This problem is from a Mexican Training Camp of this year, you can find it here (spanish only). The following is the abridged statement:

Given a undirected, simple and weighted graph with N nodes and M edges you should select a set of exactly N edges (you throw away the other M - N edges) and direct each of them, such that the sum of weights will be maximum, with the restriction that each node must have out-degree equal to 1 in this new directed graph; or say that there is not solution.

Constraints:

  • 3 ≤ N ≤ 10000

  • 3 ≤ M ≤ 50000

  • The weight of edges is between  - 105 and 105

Example:

4 6 
1 2 1 
1 3 -2 
2 3 4 
1 4 -8 
2 4 16 
3 4 -32

In this case the answer is 19, you can direct edges the following way:

  • 4 to 2 (weight = 16)

  • 2 to 1 (weight = 1)

  • 1 to 3 (weight = -2)

  • 3 to 2 (weight = 4)

I thought about flow but is not clear how I would do the graph, I also thought that N - 1 edges will be from the maximum spanning tree but that is wrong as well. Anyway could you help me?

Read more »

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

By dcordb, history, 3 years ago, In English

Admins have you noticed the long queue of submissions?

Please fix it.

Read more »

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

By dcordb, history, 3 years ago, In English

I'm having problems lately with Codeforces interface, by example sometimes the editor doesn't load properly and I can't paste my code in it, also I can't do virtual participation because the form of the time is not working. I also can't write comments on blogs.

I cleaned the cache already and the problems persists. Is anyone else having the same problems?

Admins have you seen this?? I still can't create virtual contests.

Read more »

Tags bug
 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

By dcordb, history, 3 years ago, In English

Hi. I already solved this problem by noticing that the sequence x1, x2, x4, x8, ..., x2n modulo 2010 is periodic with period 10 and pre-period 2. This means that .

I would like to know a proof for this. Could you help me? You can find the problem statement here. It's the problem E.

Thanks beforehand.

Read more »

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

By dcordb, history, 4 years ago, In English

Hi everyone. My solution to problem 712D gets TLE, even though its complexity is . Where d is the difference between the score of Memory and Lexa. Note that  - 2·105 ≤ d ≤ 2·105.

The funny thing is that in my laptop (Intel Core i5, 4gb ram) my solution runs in 1.2s. What do you think about this, is CF that slow? Anyway could you help me?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dcordb, history, 4 years ago, In English

Hello everyone.

I would like to invite you to participate in the 8th COJ (Caribbean Online Judge) Round, this will be a contest with 5 problems, and three hours of duration. The problems will have Div2-like complexity and will be in English and Spanish. The contest will have ACM-ICPC format.

You can find out more about it clicking here. You can also check out the previous rounds here.

UPD1: Time of the contest has changed because of overlapping with Euro Semifinals :). The contest will start at this time.

UPD2: The contest is about to start, get in now!!.

UPD3: The contest is over. Hope you liked the problems.

Hints:

Problem A:

The last player to play wins. Note that this last player can always get what the previous player got in the previous turn plus another positive number. Watch out with n = 1 case.

Complexity:

Problem B:

You can start from the right: i = n, decreasing k with i - 1 while k ≥ i - 1 and append to a vector the number i. Then you can append the rest of the numbers (in increasing order) to the vector.

Complexity:

Problem C:

Note that the graph is a tree with a cycle. The probability to disconnect the graph in one step is and in two steps is . So the expected value is . Here c is the length of the cycle. You can do a dfs to find c.

Complexity:

Problem D:

A number is hyperdrome if it has at most 1 digit with odd frequence. So build a graph where each node is a bitmask representing the parity of the digits's frequence of a number. Add edges between node x (0 ≤ x < 2b) and nodes .

Also add a node 2b that represents the empty set, and add and edge to itself, and to 21, 22, ..., 2b - 1.

Then you can exponentiate this graph to obtain the answer.

The answer will be . Where a is the adjacency matrix of the graph.

Complexity:

Problem E:

Segment Tree. In each node save the lcp of the range, and a string that is in the range. Then to combine two nodes you can do:

lcp[x] = min (lcp[2 * x], lcp[2 * x + 1], GetLCP(str[2 * x], str[2 * x + 1]))

str[x] = str[2 * x]

Where x is a node in the segment tree and GetLCP is a function that calculates the LCP for two strings. Also you should add lazy propagation to this.

Complexity:

Read more »

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

By dcordb, history, 5 years ago, In English

Has anyone noted that there are 5+ pages of submissions in queue?
Please admins, fix it.

Read more »

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

By dcordb, history, 5 years ago, In English

sin 1 + sin 3 + sin 5 + sin 7 + sin 9 + ...
Any ideas? PD: The angle is in radians.

Read more »

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

By dcordb, history, 5 years ago, In English

Hi, i wanted to report that some fonts are looking bad in firefox 43.0. Look at this image:

Read more »

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

By dcordb, 6 years ago, In English

I'm stuck in this problem:
http://acm.timus.ru/problem.aspx?space=1&num=1989

It gives me TLE on test 15, my code uses Hashing and Fenwick Tree, so it's O(mlogn). The time limit is only 0.5s. Is there a better solution? (an O(m) solution).
Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By dcordb, 6 years ago, In English

Could you help me with this problem from the 13th POI:
http://main.edu.pl/en/user.phtml?op=showtask&task=ork&con=OI13

It seems some kind of DP, but I'm not able to get it. So far I have an idea: to keep the state of the columns and try to filling them adding a valid rectangle, but this is too slow. Could you help me? Thanks beforehand.

Read more »

Tags dp, poi
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By dcordb, 6 years ago, In English

This is a problem from COCI 2003, here I left you the link. The problem name is VOKI (it is the third in the pdf).

http://hsin.hr/2003/national/second_day/juniors/problems.pdf

So far I have a DP approach that works in O(n * m * max(n, m)) which is too slow, could you help me to improve this?

Read more »

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

By dcordb, 6 years ago, In English

Given a sequence of N numbers (a1, a2, ..., an) you have to find the minimum number of operations to get a consecutive group of size K such that all the elements in this group have the same height. To achieve this you can increase or decrease the height of any element by 1, any number of times, each modification costs 1 operation.

Constraints: 5 <= N <= 10^6 3 <= K <= N 0 <= ai <= 10^6

Example: N = 6 K = 4 10 4 5 2 5 7

Here the solution is a group from position 2 (1-based) to position 5 (1-based), which costs 4 operations.

So far I have a solution in O(Nlog^2(N)) using a binary search + segment tree, but this timed out. Could you help me to improve this?

Read more »

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