Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

pabloskimg's blog

By pabloskimg, history, 4 weeks ago, In English,

Problem Statement. I read somewhere else (here) that the linear version of the problem is much easier if you manage to find a split in the circle. I have no idea on how to find such a split, and I have no idea either on why the linear version should be "easy". Any insights will be appreciated.

Read more »

 
 
 
 

By pabloskimg, history, 4 weeks ago, In English,
 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

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

Basically the title. The problem statement can be found here. No idea how to solve it efficiently.

UPDATE 1: why the downvotes?

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents k1, k2, ..., kr (ki ≥ kj for all i < j) such that and k = 2k1 * 3k2 * 5k3 * 7k4 * 11k5 * ... < 263. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?

UPDATE 3: pshishod2645 says there are around 2 * 106 valid combinations of exponents, where did he get that number from?

Read more »

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

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

There are at most N = 10^4 strings, each string is at most MAXLEN = 1000 characters long, but the length of the concatenation of all strings is at most 10^6. What would be the more efficient way to build a DAG as described in the title? The naive way would be comparing each pair of strings (X,Y), which leads to O(N^2) comparisons, and then for each pair to check whether X is substring of Y in O(MAXLEN^2). The naive solution could be improved by first sorting strings by length so that each string X can only be substring of strings to the right, and also we could use Rolling Hashing to reduce the complexity of substring search to O(MAXLEN). Is it possible to do even better? I've got the feeling that Suffix Array could be of help, but I'm not sure of exactly how. The motivating problem is this one

Read more »

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

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

Based on some spoilers I "know" that the problem Game of Tiles from 2012 ICPC Latin America Regional Contest should be solved using maxflow / bipartite matching. However, I still haven't been able to figure out a correct solution for it based on bipartite matching. Does anybody know how to apply bipartite matching, or any algorithm for that matter, to solve the problem? If so, would you kindly share the logic behind your solution?

Read more »

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

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

I'm trying to solve the problem Routing from ACM ICPC World Final 2006, and I don't have any ideas on how to solve it. Since the number of nodes in the graph is at most 100, I guess a Floyd-Warshall preprocessing should be no problems and could probably help, but after that I really don't have any ideas on what to do next.

Any tips will be appreciated.

Read more »

 
 
 
 

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

Given a lot of points and circles, you have to find all points that are either inside a circle or surrounded by a closed loop of circles (a sequence of circles of some length N such that circle i intersects circle (i+1)%N). For example, in the picture below, all red points would be points satisfying the aforementioned condition:

I need to figure this out in order to solve this problem. UPDATE: solutions can be submitted here: http://poj.org/problem?id=2863, if you solve it, please let me know which strategy you used :D

I guess I need to build a graph where circles are nodes and add edges between circles intersecting each other. Then I would have to find somehow maximal cycles in this graph, for each maximal cycle find the corresponding maximal polygon formed by connecting the centers of circles in the maximal cycle with segments in counter-clockwise order, and finally for each point check if it's contained by one of these maximal polygons. I've got no idea of how to do anything of this :(

Read more »

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

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

There are N (<= 2*10^5) 2D points with coordinates x,y and cost c. There are M (<= 2 * 10^4) queries, each query is a point (x,y) with cost c. For each query, you need to return the point with cost <= c that is closest to the query using euclidean distance. In case of ties, return the point that appears first in the input. The full problem statement can be found here: https://icpcarchive.ecs.baylor.edu/external/77/p7744.pdf.

Any ideas on how to solve it? I've got the feeling that some efficient spatial partitioning data structure might be of help, but I'm not sure of which one. For instance one idea I have in mind is to sort both the points and the queries by their costs, and then use 2 pointers, so that one pointer advances through the queries and the other pointer advances through the points, and as I advance through the points I insert each point to some dynamic data structure that would allow me to quickly find the nearest neighbor to the current query (and somehow break ties using the point indexes). Using this strategy, a static data structure such as a kd-tree would not work because the structure would need to be dynamic (support updates). So I just googled dynamic spatial partitioning data structures and for instance I found R* trees, but I'm afraid that learning R* tree might be overkill for competitive programming (?)

Any ideas/hints/suggestions will be appreciated.

Read more »

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

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

Can anyone confirm that ICPC Live Archive is behaving strangely by throwing WA with 0.000 seconds to all submissions? Is this a common bug of the server, and if so does anyone know why it happens and whether it will get fixed soon?

Read more »

 
 
 
 

By pabloskimg, history, 7 months ago, In English,

Given 2 nodes u and v, IF for each pair of paths between u and v there is a common in-between node, THEN there is a GLOBAL common in-between node (a.k.a. articulation point) shared by all paths between u and v.

tl;dr does pairwise imply global?

Is this true? Any formal proofs?

Read more »

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

By pabloskimg, history, 8 months ago, In English,

Is it true that if a biconnected component has an odd simple cycle, then ALL edges in that component belong to some (not necessarily the same) odd simple cycle? If that's the case, what would be a formal proof for that? I believe this property would be crucial to solve this problem: http://codeforces.com/problemset/problem/97/E

Read more »

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

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

Hi everyone,

I'm struggling to come up with a correct and efficient algorithm that is able to find an odd-length cycle in an undirected graph. Any odd-length cycle is fine. I already know that a graph has an odd-length cycle if and only if it's not bipartite, but the problem is that this only tells you whether there is an odd-length cycle or not, but it doesn't find you an actual cycle in case there is one. One possible approach I came up with is to run DFS and every time there is a back-edge check if the cycle formed by the back-edge has an odd length, but the problem with this strategy is that it would only test a subset of the cycles, but not all possible cycles (think of complex cycles using many back edges in complex ways). Does any one know how to solve this problem?

Thank you guys in advance.

Read more »

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

By pabloskimg, history, 14 months ago, In English,

I'm trying to solve the following problem (Electrical Pollution): https://www.urionlinejudge.com.br/judge/en/problems/view/1334 (please read the problem statement). So basically we are given many 2 variable (x + y = c) and 1 variable (x = c) linear equations, i.e measurements, and then we are given multiple 2 variable (w + z = ?) and 1 variable (w = ?) queries and we have to either give the exact result if the answer can be inferred from the previous measurements, or * otherwise.

My idea is to build a graph where the nodes are the variables and the edges are the 2-variable equations connecting them.

1) As a first step, we already know the values of the variables in the 1-variable measurements, and starting from them we can propagate and infer the values of all the other variables connected with BFS over the graph.

2) As a second step, we can solve equation systems with an odd number of equations where there are the same number of equations and variables. Basically we can run DFS, find loops (backward edges), if the loop has an odd length then we can easily solve the equation system of the edges in that loop (say, we solve for the first variable in the loop) and then we propagate to the whole connected component with BFS (as in 1).

3) It turns out that 1) and 2) are not enough, because it's not necessary to know the exact values of both variables to be able to know the value of their sum. In fact, given a 2-variable query (x + y = ?), if we can find a path (not necessarily a loop) of odd length, and if we enumerate the measurements along that path with 1, 2, 3, ..., n, then we can solve the equation (x + y = ?) by adding the measurements with odd index and subtracting the measurements with even index along that path. Moreover, any odd-length path would do the trick, because the final result will be the sum of the variables at both ends of the path, and variables in between just cancel each other (like a sort of telescoping sum http://mathworld.wolfram.com/TelescopingSum.html).

My question is basically about how to implement point 3). Right know I'm not sure about how to do it. I guess it shouldn't be necessary to find a specific path, because the final result will not depend on the exact path taken, just on the end points. Maybe precomputing partial sums and combining them using LCA somehow or something like that could work, but I cannot see how to exactly do the combination.

Any help will be deeply appreciated :)

Thanks in advance

Read more »

 
 
 
 

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

Hi everyone!

I'm struggling way too much trying to get accepted in a problem called "Olympic Games", whose statement can be found here: https://dl.dropboxusercontent.com/u/28504121/ProblemsetRPC11/J.pdf. This was the problem J of a latin american regional simulation contest. Later on I realised this problem was actually borrowed from a brazilian contest, so you can also find the same problem in URI Online Judge at this link: https://www.urionlinejudge.com.br/judge/en/problems/view/2244. I recommend the latter link in case you want to submit solutions of your own.

Feel free to read the problem statement. Otherwise, here is a brief summary (although it's subject to my own interpretation, which might be wrong):

Summary:

There are 1 <= N <= 10^5 athletes. Each athlete has skill and fatigue. Skills and fatigues are linear functions (intercept and slope) of time. In other words, for each athlete i:

skill_i (t)  =  skm_i * t + skn_i
Fatigue_i (t) = ftm_i * t + ftn_i

where  -10^6 <= skm_i, skn_i, ftm_i, ftn_i <= 10^6
        skm_i & ftm_i  !=  0   (slopes are not 0)
        t >= 0    (there is no negative time)
        All the slopes and intercepts are intergers

A golden athlete is someone who at a given period of time happens to be the guy with maximum skill and minimum fatigue. You are asked to return the total number of golden athletes.

Ambiguities:

  • Right away I noticed a certain ambiguity in the definition of a golden athlete. What happens if there are more than 1 athlete with maximum skill, or with minimum fatigue, or both at the same time? The golden athlete must be the only winner in both? Can there be a tie in one attribute and a unique winner in the other attribute? Can there be ties in both attributes and therefore there be 2 or more golden athletes at the same time?
  • Another ambiguity: Is it possible to be a golden athlete for a singleton of time (a single instant), or does it have to be an interval with a non-zero duration?

My current approach:

Now I will briefly explain how I'm trying to solve the problem. First of all, since we are interested in the maximum of the skills, we want the upper envelope of the skill lines. Likewise, we also want the lower envelope of the fatigue lines. Therefore, by Point-Line Duality, we want the lower-hull of the skill dual points and the upper-hull of the fatigue dual points. So we do that, and then basically we iterate over the lines of the skill upper-envelope, perform intersections between consecutive lines and generate a sequence of skill time intervals, and for each interval we remember the id's of the athletes that are dominant in that interval. We do the same for the fatigue lower-envelope. Finally we perform a parallel linear sweep of both sequences of intervals using 2 pointers, and for each pair (skill-interval, fatigue interval) we look for a unique athlete who is the best in both intervals (for example, we can have a set of ids in each interval and perform a set intersection and make sure we get only one). We count all these golden athletes (we make sure we don't count the same athlete more than once) and return the total count.

You can check my current implementation here (I hope the code and commentary are clear enough): https://github.com/PabloMessina/Competitive-Programming-Material/blob/master/Solved%20problems/Red%20de%20Programaci%C3%B3n%20Competitiva/2016-Competencia-11/J_OlympicGames.cpp

My current attempt makes some assumptions, though:

  • I allow draws within skill intervals and fatigue intervals, but the intersection should have size 1 (a unique golden athlete).
  • I allow golden athletes for singletons of time (say, if an athlete has the best skill only in a single instant where multiple lines intersect one another, but he has the lowest fatigue all the time, then he would be golden for me in that single instant).

Currently I'm getting wrong answer with 20% of the test cases correct in URI Online Judge.

Questions:

  • What is the right interpretation of the problem statement? (refer to the ambiguities above)
  • What do you think about my current assumptions and implementation? Any tips on how to make the implementation less tricky?
  • Would you mind sharing some tricky corner cases to test my code?
  • Ideally: if you were able to get accepted, would you mind explaining your solution :D?

References:

Some references on Point-Line Duality:

Thank you guys in advance.

Read more »

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

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

Hello everybody. I'm struggling to figure out the solution for a problem but I still don't quite get it. It's the Problem A, Freight Train, of a latin american problem set, which you can find here: https://dl.dropboxusercontent.com/u/28504121/ProblemsetRPC08.pdf

I recommend you to read the problem statement directly from the link in order to have an unbiased interpretation thereof, otherwise you can read the following summary:

Basically you are given a sequence of N wagons, where W of those wagons have freight in them, and the rest is just empty wagons. You are given the actual indexes of the W wagons with freight (all wagons are arranged from 1 to N). You are also given a number L of locomotives. You can assign wagons to locomotives, but you can only assign contiguous sequences of wagons to locomotives. So for example one locomotive can pick the first 3 wagons, another locomotive can pick the next 4, etc. But you cannot have a locomotive picking the first and the third wagon an leave the second wagon unpicked in between, for instance. Ok, so there are two targets to send the wagons to, target A and target B. But, the thing is, you are required to send all the W wagons with freight to A, but the empty wagons can be sent to either A or B (but there cannot be wagons leftover, all the wagons must be sent to somewhere). So the challenge is to find an assignment of wagons to locomotives such that minimizes the longest train (locomotive + wagons) forwarded to A (trains sent to B don't matter, you can send huge trains to B and their lengths would be ignored). Also, you are not required to use all the L locomotives, you can use fewer if that is enough.

And let me not forget it: 0 <= N <= 10^9, 1 <= W, L <= 10^4, and W <= N

So even O(N) would yield time limit exceeded, which it's a clear indication that the algorithm complexity should be based on W and L instead. So my intuition is that there must be some reductions / simplifications around the empty wagons, in other words, it shouldn't be necessary to try every single position within a contiguous sequence of empty wagons to decide where the previous train ends and where the next one starts. For example, if you assign a partial substring of empty wagons to a train and then send the train to B, that would be stupid because you would be better off sending the whole string of empty wagons to B in one shot. Another insight is that you always have the suboptimal solution of splitting the wagons into L groups with sizes of at most ceil(N / L) each, so that would be an upperbound for any train forwarded to A. I have a feeling that this should be solvable using Dynamic Programming, but still I don't see a way to define some recursive formula or something that handles the empty wagons correctly.

So feel free to enjoy yourself solving this problem and any help, insight or advice that you can share would be really appreciated.

Note: if you actually want to solve the problem and submit a solution, you can try out this website: https://acm.javeriana.edu.co/maratones/2016/08/. Be aware, though, that the site is in Spanish since it's a latin american online judge, the server performance is not the best of the world, and in order to submit solutions you need to login using one of the dummy usernames provided in the page and leave the password field empty.

Read more »

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