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?

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?

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.net/problemset/problem/97/E

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.

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

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:

• http://www.cs.uu.nl/docs/vakken/ga/slides8.pdf
• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.1459&rep=rep1&type=pdf
• http://students.cec.wustl.edu/~tdeck/duality/

Thank you guys in advance.

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.