Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### pabloskimg's blog

By pabloskimg, history, 4 months ago, ,

Hi, I'm trying to solve the problem Jeopardized Election. This was problem J in 2018 ICPC Latin America Regional Contest. No team in Latin America was able to solve it during the contest, check out the final scoreboard. I'm trying to figure out the solution but so far I can only think of the brute force approach, which is factorial and can't work. I've got a feeling that there must be a greedy strategy to solve it, but I'm not sure. It would be awesome if some of the genius minds here on Codeforces could shed some light on the solution.

Thank you very much!

• +14

By pabloskimg, history, 4 months ago, ,

Hi, I'm trying to solve this problem. The problem turned out to be way harder than I expected, and my current solution has many lines of code, I have debugged it a lot with many hand-made test cases but I'm still getting WA. You can find my code here. I looked for a proper implementation of the area of the intersection between a triangle and a convex polygon but I couldn't find any. I would appreciate if someone with expertise in geometry could share his/her knowledge, or if someone could share a link to a proper implementation of this problem that would be awesome too, that way I can compare my solution with it and figure out what I'm doing wrong too.

Thank you very much.

• +19

By pabloskimg, history, 5 months ago, ,

Hi, I'm trying to solve Gym 102263E Longest Path Problem and my code can be found here. My strategy is to think of each edge as a bridge that splits the tree in 2 subtrees, and the subtree I'm interested in depends on which direction (forward or backward) I'm considering. So, given edge e=(u,v), if I consider the forward direction then I'm interested in the subtree that has v as root (and u is the parent of v), whereas if I consider the backward direction then I'm interested in the subtree that has u as root (and v is the parent of u). Thus, I can use dynamic programming to compute many things for the subtree forward and the subtree backward defined by each edge, the signature of the DP is basically DP(edge, direction) where edge $\in [1,N-1]$ and direction $\in$ { forward, backward }. Using this strategy I can recursively compute the diameter, the end nodes of a diameter, the maximum depth and the deepest leaf for both subtrees (forward and backward) associated to each edge in O(N). Once I have that, then the answer for each edge is the maximum between the diameter forward, the diameter backward and the longest path that we obtain by connecting the center of the subtree backward and the center of the subtree forward with the current edge. To find the center of each subtree, I use binary search between the end nodes of a diameter (found in the DP previously explained) using LCA with binary lifting method in the predicate.

I debugged my solution a lot and it's working with the example and I created some additional examples by hand and it's working with them too. However I'm getting wrong answer on test 3. I would really appreciate if somebody could help me out by providing some tricky test cases to test my solution with. Unfortunately gym doesn't show the test cases so I had to create test cases myself but my solution seems to work all the time. Maybe there is something wrong in my strategy somewhere, some tricky corner cases which I'm overlooking.

Thank you very much in advance.

Update: I debugged my solution a little more and realized I had a bug in a function that finds the k-th node in the path from u to v, I fixed that bug but now I'm getting TLE on test case 60 :(, any tips on how to optimize my code even more? You can find my latest code here

• 0

By pabloskimg, history, 5 months ago, ,

Given a tree, I need to find all the edges that are shared by all diameters of that tree. In other words, let D be the length of the longest path in the tree and P be the set of all paths in the tree with length = D. I need to find the intersection of the edges shared by all paths in P. How can I do that?

I know how to do it in O(N^3) which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.

Thank you very much.

Update: I need to know how to do this in order to solve this problem: https://www.codechef.com/MARCH13/problems/SUBTREE

• +1

By pabloskimg, history, 6 months ago, ,

I have a tree, and if I remove an edge the tree would get disconnected into 2 subtrees. Now, for each of these 2 subtrees I would like to find (quickly) 2 end nodes of a diameter, that is, I would like to find the end nodes of a diameter of subtree 1 and the end nodes of a diameter of subtree 2 (4 nodes in total). I need to do this for many possible edges (edge removals don't accumulate). Is it possible to do that efficiently? I need this in order to solve this problem. Otherwise I will need to figure out another approach. Thank you in advance.

• +10

By pabloskimg, history, 7 months ago, ,

Problem: there are N players, each one starts with some initial score, therefore they appear sorted non-increasingly by their scores in a dynamic leaderboard. From time to time some player changes his score, and the leaderboard gets updated to reflect the player's new ranking (in case of ties, for simplicity let's assume ties are broken by comparing the players' unique IDs). At the same time, we need to answer queries of the form "What is the accumulated sum of the scores of all players with rank between L and R in the leaderboard?". Score updates and range sum queries are interleaved.

Does anybody know how to implement this efficiently? I know I can implement a dynamic ranking using STL policy based data structures, because I can query the current ranking of a player in O(log(N)), remove him in O(log(N)), insert him again with his new score in O(log(N)) and finally query his updated ranking in O(log(N)). However I don't know how to keep track of accumulated sums of ranked scores efficiently. Maybe some clever adaptation of segment tree or fenwick tree might be of help but I'm not sure how.

Any help is very appreciated.

• +2

By pabloskimg, history, 7 months ago, ,

There are $N$ jobs, each job $i$ has a single prerequisite job $P_i$ that must be done before, except for a global root job which has no prerequisite. Each job takes $T_i$ time to be finished, and if a job is finished at time $t$ it contributes with a penalty of $t * U_i$, where $U_i$ is the i-th job's penalty coefficient. What is the minimum penalty for finishing all jobs?

Constraints: $N <= 2 * 10^5$, everything is integer and non-negative

Notes:

• only a single task can be performed at a time (there is no concurrent work / task parallelism)
• the tasks DAG looks like a rooted tree

Any ideas on how to solve this? I was thinking of performing some kind of backtracking over all possible topological orderings of the DAG + some kind of extremely heavy pruning, but I haven't figured out yet a good pruning strategy to avoid exponential time. I also thought of using DP, but then I need to use bitmasks to keep track of unvisited nodes, which leads to exponential time.

• -33

By pabloskimg, history, 8 months ago, ,

• 0

By pabloskimg, history, 11 months ago, ,

As of now, in the root directory of ICPC Live Archive there is no folder named "Regionals 2018". The latest folder is "Regionals 2017". Does anybody know why 2018 regionals have not been uploaded yet and when they will be uploaded? Alternatively, is there any other online judge hosting all 2018 regional problems?

• +14

By pabloskimg, history, 15 months ago, ,

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.

• 0

By pabloskimg, history, 15 months ago, ,

• +10

By pabloskimg, history, 16 months ago, ,

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

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?

• -24

By pabloskimg, history, 16 months ago, ,

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

• +15

By pabloskimg, history, 16 months ago, ,

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?

• +19

By pabloskimg, history, 16 months ago, ,

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.

• 0

By pabloskimg, history, 17 months ago, ,

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

• +11

By pabloskimg, history, 17 months ago, ,

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.

• +8

By pabloskimg, history, 17 months ago, ,

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?

• 0

By pabloskimg, history, 22 months ago, ,

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?

• -19

By pabloskimg, history, 22 months ago, ,

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

• +3

By pabloskimg, history, 2 years ago, ,

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?

• +8

By pabloskimg, history, 2 years ago, ,

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

• 0

By pabloskimg, history, 3 years ago, ,

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:

• +47

By pabloskimg, history, 4 years ago, ,

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.