Main public logs

Combined display of all available logs of programming_contest. You can narrow down the view by selecting a log type, the username (case-sensitive), or the affected page (also case-sensitive).

• 19:34, 9 March 2024 Kmk21 talk contribs created page GCDs (Created page with "realization: only a small total count of GCDs. moreso, any range that spans coprime numbers will be 1. or more generally, all numbers in that range must be divisible by the GCD, and no higher number. So go through each number, track the earliest seen number which is divisible by each possible GCD (max 100). O(100*100k) Category:ICPC Problems Category:Nac2014 Category:Algorithm Medium Category:Math Category:GCD Category:Dynamic Programming")
• 18:24, 9 March 2024 Kmk21 talk contribs created page Diplomacy (Created page with "collapse all groups of same color nodes. they always change together. then try every group and alternate expanding it purple/orange. this is just distance. find the one with the least distance to the furthest node Category:ICPC Problems Category:Nac2014 Category:Algorithm Medium Category:Graph Category:Brute Force")
• 17:03, 9 March 2024 Kmk21 talk contribs created page Banjo (Created page with "need to search over both entry and exit point. also may be helpful to fix the number of times we "cross" the circle. Category:ICPC Problems Category:Nac2014 Category:Algorithm Medium Category:Implementation Hard Category:Geometry Category:Binary Search")
• 17:01, 9 March 2024 Kmk21 talk contribs created page Category:Nac2014 (Created page with "category:nac category:2014 category:contests")
• 21:15, 2 March 2024 Kmk21 talk contribs created page Category:Graph Transformation (Created page with "Category:Techniques")
• 21:14, 2 March 2024 Kmk21 talk contribs created page Uniform Subtrees (Created page with "the input is a tree, and the output graph is also a tree (with the longest chain and most nodes on the left hand children). Consider this input: (((()()))(()()())) (encourage drawing it out) The "output" Is 0 10 110 1110 1120 120 130 20 210 This maps to a tree of the following form: (((()())()())(())) (again encourage drawing it out) whose preorder traversal defines the output. (number each edge from each node from left to right to see this) If we have two subtrees...")
• 16:26, 1 March 2024 Kmk21 talk contribs created page Winter Roads (Created page with "MST is only 1k nodes, so most operations are cheap. S is just a bfs in O(n), R is similar...bfs from the two endpoints of the repaired road (if not on the tree) and swap out if the repaired edge is higher than the min on that path in O(n). B is harder, but max 2k B operations, so can rebuild the MST each time. Don't rebuild the heap in kruskal, so you don't eat the extra log...just update the heap for each B and R. Only rebuild if B operation is for an edge on the curre...")
• 03:45, 29 February 2024 Kmk21 talk contribs created page Category:Simplex (Created page with "Category:Techniques")
• 03:45, 29 February 2024 Kmk21 talk contribs created page Goat Ropes (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Simplex")
• 03:31, 29 February 2024 Kmk21 talk contribs created page Flooding Fields (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Max Flow Category:Grid Category:In-Out Nodes‎")
• 02:51, 29 February 2024 Kmk21 talk contribs created page Unreal Estate (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Sweep Line")
• 02:50, 29 February 2024 Kmk21 talk contribs created page Overlapping Maps (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Easy Category:Coordinate Transformation Category:Math")
• 02:49, 29 February 2024 Kmk21 talk contribs created page Job Postings (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Min Cost Max Flow")
• 02:45, 29 February 2024 Kmk21 talk contribs created page 3D Printer (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:3D Geometry")
• 02:43, 29 February 2024 Kmk21 talk contribs created page Category:Range Query (Created page with "Category:Techniques")
• 02:43, 29 February 2024 Kmk21 talk contribs created page Category:Data Structures (Created page with "Category:Techniques")
• 02:43, 29 February 2024 Kmk21 talk contribs created page Can of Worms (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Data Structures Category:Range Query")
• 02:38, 29 February 2024 Kmk21 talk contribs created page Category:Suffix Tree (Created page with "Category:Techniques")
• 02:38, 29 February 2024 Kmk21 talk contribs created page Automatic Trading (Created page with "Category:ICPC Problems Category:Nac2013 Category:Algorithm Medium Category:Strings Category:Suffix Tree")
• 06:29, 27 February 2024 Kmk21 talk contribs created page Category:Nac2013 (Created page with "category:nac category:2013 category:contests")
• 06:15, 27 February 2024 Kmk21 talk contribs created page Category:Hall's Theorem (Created page with "Category:Techniques")
• 06:15, 27 February 2024 Kmk21 talk contribs created page Science! (Created page with "Standard bipartite graph construction. Binary search on the maximum possible flow which can be met (chaning capacity from source->people, and from button->sink)> This is not necessarily tight bound? Have to demonstrate that even with this value, that we can actually construct a valid assignment. Remove unused edges with no loss of generality. Consider node A and B which should be paired with W, X in round one, and X, Y in round two. Then consider they are paired with W,...")
• 05:05, 27 February 2024 Kmk21 talk contribs created page CosmoCraft (Created page with "fastest way to grow is to build workers first. worker:production approaches golden ratio. never build army more than 2 turns out. Example: 5W, 3P: max army 5W, 3A, 5P ->8A,5P->13A->18A max prod 8W, 0A, 5P ->5A,8P->13A break-even is 2 turns. so greedy max production unless we need to optimize for army in any of the next two turns. Greedy 1) as much army as necessary to defeat attacks (or last 2 turns) 2) workers 3) production Category:ICPC Problems Categ...")
• 03:41, 27 February 2024 Kmk21 talk contribs created page Category:3D Geometry (Created page with "Category:Techniques")
• 03:41, 27 February 2024 Kmk21 talk contribs created page The Worm in the Apple (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Hard Category:Implementation Hard Category:3D Geometry Category:Convex Hull")
• 03:39, 27 February 2024 Kmk21 talk contribs created page The Red Gem (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Medium Category:Geometry")
• 03:37, 27 February 2024 Kmk21 talk contribs created page Covered Walkway (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Hard Category:DP Category:Convex Hull Optimization")
• 03:19, 27 February 2024 Kmk21 talk contribs created page Red/Blue Spanning Tree (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Medium Category:Tree")
• 03:14, 27 February 2024 Kmk21 talk contribs created page Estimation (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Medium Category:DP")
• 03:09, 27 February 2024 Kmk21 talk contribs created page Category:Fenwick Tree (Created page with "Category:Techniques")
• 03:09, 27 February 2024 Kmk21 talk contribs created page Juggler (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Medium Category:Fenwick Tree")
• 03:06, 27 February 2024 Kmk21 talk contribs created page Category:LCM (Created page with "Category:Techniques")
• 03:05, 27 February 2024 Kmk21 talk contribs created page Double Dealing (Created page with "Category:ICPC Problems Category:Nac2012 Category:Algorithm Medium Category:LCM")
• 03:03, 27 February 2024 Kmk21 talk contribs created page The End of the World (Created page with "Category:Problems Category:Nac2012 Category:Algorithm Medium Category:Select an Element")
• 02:55, 27 February 2024 Kmk21 talk contribs moved page Category:NAC2012 to Category:Nac2012
• 02:55, 27 February 2024 Kmk21 talk contribs moved page Category:NAC to Category:Nac without leaving a redirect
• 02:54, 27 February 2024 Kmk21 talk contribs created page Category:NAC2012 (Created page with "category:nac category:2011 category:contests")
• 02:53, 27 February 2024 Kmk21 talk contribs created page Category:NAC (Created page with "category:regions")
• 07:43, 14 February 2023 Kmk21 talk contribs created page Category:Binary Lifting (Created page with "Category:Techniques")
• 07:43, 14 February 2023 Kmk21 talk contribs created page Category:Least Common Ancestor (Created page with "Category:Techniques")
• 07:42, 14 February 2023 Kmk21 talk contribs created page Toll Roads (Created page with "This problem defines a "toll" to traverse a road, and asks of a road network multiple queries of what is the minimum maximum toll to be paid to connect two cities, and how mayn cities can be connected with that toll. The first observation (other than this is probably a graph problem), is that the problem space is too large for something like all pairs shortest path. It should also be apparent that even if we somehow were able to do dijstra, with 10^5 queries, its unlike...")
• 07:15, 14 February 2023 Kmk21 talk contribs created page Spidey Distance (Created page with "This problem defines two measures of grid distance and asks us what the fraction of overlap is. The first thing to note is we only need to observe one quadrant, and it doesn't change the answer, as both measures are 4-way symmetric. Second, we note that the distance is only 10^6, so it is relatively small. Lastly, given an X value, we can closed-form compute the Y value for both manhattan distance. They are, both from observation: * y=taxi-x * y=(spidey-1.5x)+x=spidy-....")
• 07:03, 14 February 2023 Kmk21 talk contribs created page Smallest Calculated Value (Created page with "This problem gives us 3 integers and asks us to perform any combination of arithmetic operations on them to see which result is smallest and non-negative. As the numbers cannot be rearranged, we see that there are only 16 combinations of the 4 operators. Therefore, we can brute force and try all of them. Category:ICPC Problems Category:Naq2022 Category:Algorithm Easy Category:Implementation Easyh Category:BruteForce")
• 07:01, 14 February 2023 Kmk21 talk contribs created page Room Evacuation (Created page with "This problem gives us an ASCII description of a room, with people and exits, and asks us how many people can reach an exit in an allotted time. The input size of 20x20, and the intuitive understanding of a "choke point" in the graph strongly indicate that this is a flow problem. We can naturally create a node for each NxM pair, at each time t. We split each node to in-out nodes, with a traversal of 1, to guarantee only a single person traverses a node at any time. We se...")
• 06:55, 14 February 2023 Kmk21 talk contribs created page Platform Placing (Created page with "This problem gives us fixed "anchor points" on the x axis, and a minimum and maximum interval which we can carve out around those anchor points, and asks what the maximum non-overlapping coverage ove the axis is. We can first consider the two-anchor case. Suppose we have two anchors which would overlap if they both had maximum widge intervals. We can also see that so long as those segments are grown to such a degree that they are touching, then the total span of the two...")
• 06:49, 14 February 2023 Kmk21 talk contribs created page Movie Night (Created page with "This problem gives us rules about which friends require other friends in order to go out, and asks us the count of combinations of friends. We see that this is well suited to a graph representation, and representing the links as such gives us a couple intuitions: # Each node has exactly one outgoing edge # If there is a cycle or strongly connected component, it MUST be a sink of the graph, otherwise there would be a node with multiple outgoing edges # Each connected com...")
• 06:41, 14 February 2023 Kmk21 talk contribs created page Metronome (Created page with "Divide by 4. printf(%.2f). Category:ICPC Problems Category:Naq2022 Category:Algorithm Trivial Category:Implementation Trivial")
• 06:40, 14 February 2023 Kmk21 talk contribs created page MazeMan (Created page with "This problem gives us and ASCII maze with a few entrances and tells us how many dots are reachable, and how many different entrances we have to use to reach these dots. In short, it's asking us how many connected components there are. This is a relatively straightforward flood-fill problem, whereby we walk around the permiter of the maze to find an un-used entrance, and flood fill. If we ecounter any dots on this fill, we increment our count by 1. We also mark any exit...")
• 06:32, 14 February 2023 Kmk21 talk contribs created page Ghost Leg (Created page with "This problem gives us a ladder (much akin to a mini-game from the original mario party!) and asks us what permutation it forms. We can simulate this quite easily. Generate an array of size n, where a[i]=i. Then for each rung m, swap the two corresponding elements. WHen we're done, print out the remaining array. Category:ICPC Problems Category:Naq2022 Category:Algorithm Easy Category:Implementation Easy Category:Simulation")
• 06:31, 14 February 2023 Kmk21 talk contribs created page Class Field Trip (Created page with "Input the Strings. Concatenate them. Put them in Char array, sort it. Print it. Category:ICPC Problems Category:Naq2022 Category:Algorithm Trivial Category:Implementation Trivial")