The Way Through The Forest

ACM-ICPC Live Archive 4329: Ping Pong My Problem Version Given N (3 ≤ N ≤ 20000) distinct numbers, a 1  , a 2  ,  a 3 ... a N , each not more than 100000, how many ways can we select a pair of three numbers, a x  , a y  , and a z  , such that a x < a y  < a z   and x < y < z? Note: x=1, y=2, z=3 is different from x=2, y=1, z=3. The Algorithm We can take a hint from "... how many ways can we select ..." that this would involve prefix sums. Since we are asked to select the way to make 3 things, we would need to make 3 prefix sum arrays... unless we try to consider the problem from a y  's point of view: the amount of ways to select a number to "its" left and smaller times the number of ways to select a number to "its" right and bigger is the amount of ways to create a pair where "it" is  a y . We do this for every possible value of y. Wait a minute... smaller and to its left ... larger and to its...

USACO Training "subset": Subset Sums Problem Statement Subset Sums JRM For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical: {3} and {1,2} This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions). If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum: {1,6,7} and {2,3,4,5} {2,5,7} and {1,3,4,6} {3,4,7} and {1,2,5,6} {1,2,4,7} and {3,5,6} Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. Your program must calculate the answer, not look it up from a table. PROGRAM NAME: s...

I moved all the posts from Codrspace, another blogging platform. Here is the link   to my Codrspace blog (now no longer updated.) So don't think I wrote all these posts in a single day. Thank you. 😌

USACO Gold December 2016 "Lasers and Mirrors" Problem Statement (Original) For some reason, Farmer John's cows always seem to be running laser light shows. For their latest show, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move it easily from the location where it was delivered. They would like to somehow send the light from the laser to the barn on the other side of FJ's property. Both the laser and the barn can be considered to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or y axes). They will then bounce this beam off a number of mirrors to direct it to the barn. On the farm there are N fence posts (1≤N≤100,000) located at distinct 2D points (also distinct from the laser and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror o...

Disjoint Set Data Structures The disjoint set data structure, or DSDS, is a collection of different trees. The DSDS is an efficient way to search up whether two nodes are in the same group or not or to keep track of the connected components of an undirected graph. It is efficient because it remembers all operations done on the structure, and makes those exact operations more efficient in the future, giving it an edge over plain brute-force search. Implementations of the DSDS for specific problems commonly require different specifications and changes, but the unimproved DSDS has three methods:  1. MakeSet(),  2. Find(),  3. and Unify(). MakeSet() initializes a tree with only one node and adds it to the DSDS (forest). This method is run before any other method calls. The node of an unimproved DSDS has the following attributes:  1. node.parent (the ancestor of the node)  2. (only necessary for optimizations and commonly redundant) node.rank Initially, ...

NOI China 2002: Legend of Galactic Heroes Original Problem Statement 描述 公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。 然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。 在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。 作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。 最终的决战已经展开，银河的历史又翻过了一页…… 格式 输入格式 输入的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。 以下有T行，每行有一条指令。指令有两种格式： 1.M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。 2.C i j ：i和j是两个整数（1<=i , j...

USACOT 1.3.2: Barn Repair Problem Statement Barn Repair It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full. The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width. Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase. Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calcul...

USACOT "hamming": Hamming Code Problem Statement Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):         0x554 = 0101 0101 0100         0x234 = 0010 0011 0100 Bit differences: xxx  xx Since five bits were different, the Hamming distance is 5. PROGRAM NAME: hamming INPUT FORMAT N, B, D on a single line SAMPLE INPUT (file hamming.in) 16 7 3 OUTPUT FORMAT N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted a...

Subway Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10066 Accepted: 3289 Description You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school. You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions. Input Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway run...

Continued from  post on BITS. The choppy array, which only stores benchmarks.Only storing benchmarks allow a roughly O(n/x+x) speedup to commands. Adding a element. Mark each index in the details up to the next benchmark. Only some things are stored! Example First, let's increment index 2. Here, 2,3,4,5,6,7,8,9 are all incremented. Then, only the benchmarks are incremented (10,20,30,40). We can think of it like this: The 2,3,4, and 5 represent a small stream, where at 9 the stream merges into a river only containing benchmarks. So we can imagine a choppy tree/array like so: 0~~~~~~~~~~~~~~10~~~~~~~~~~~~~~~~~~~20~~~~~~~~~~~~~~~~~~~30                /                    /                    /  1~2~3~~~~~8~9~  11~12~13~~~~~18~19~  21~22~23~~~~~28~29~ We increment 2 to 9, then 10, 20 and 30: 0~~~~~~~~~~~~~~~1~~~~~~~~~~~...

POJ 3104: Drying Problem Statement Description It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time. Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes. There are n clothes Jane has just washed. Each of them took ai water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed. Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by k this minute (but not less than zero — if the thing contains less than...