I've been taking a long break from CP... in fact I never thought I'd return.

But, one day, something incredible happened.

I was talking to some people. Just, regular, normal conversation. And then, swept up by the moment, I decided to make a meme. After releasing a creative, witty meme that perfectly fitted the situation, I felt like something was wrong. While the others laughed, I only felt more empty.

Like I was missing something. Like my meme was missing something. I thought "would Xellos approve of this meme?"

And then I felt a deep void, a deep rip in my heart, because I was missing something all along.

In a desperate effort to get rid of this feeling of loneliness, of absolute terror, I came up with another joke... but the joke involved bitset. The randoms in front of me would not understand it. They couldn't. They might never.

So I clawed my skin in agony, vaguely aware of the thing that was missing in my life. I was sweating buckets and grasping my abdomen in anticipation of the waves of anguish and adrenaline causing through my body.

Suddenly, I stood up, left the room. The randoms in front of me tried to stop me, to keep me in a prison of words. But I could no longer see them. They didn't exist. I told them, "you don't even exist!"

And then I ran to my bike, rode it through the streets. The bike broke so I got into a car and drove as far a I could. When the car hit a tree, I ran until my feet were bleeding and I finally arrived at my familiar abode.

Slamming the door, throwing off my bloodied shoes, and running into my room, I opened my computer.

And then, slowly, carefully, with utmost concern for the sanctity of the folding metal contraption emitting polarized light through the means of a liquid crystal display, I typed in the browser "https://mirror.codeforces.com"

For SCCs if we want to answer the query "are A and B in the same component?" it's quite easy because each vertex belongs to only one component. We can store color[i] and compare them.

But this idea won't work for biconnected components. Cut vertices (articulation points) can be part of O(N) BCCs. I'm not sure if there is a solution for the general case of "are A and B in the same BCC?". Can we do some processing to solve this problem for biconnected components in sublinear time?

I recently read this article which summarizes cool cp tricks.

Trick 12 is something uses Euler Tour to solve algorithmic problems on trees. The thing is, I don't know what the difference is between euler tour 1 and 2? If in one euler tour for each node we store when it enters and exits, that gives us continuous segments = subtrees. But what about a path? Apparently another euler tour solves this, but I don't know how it should be represents/how to do it. Could someone please elaborate, preferrably with a diagram?

UPD: Many thanks to saharshluthra for leading me to idea.

I will now try to explain idea in my own words (with hope that it will help others in the future). The idea I was already familiar was this: we create events when we enter a node but not when we exit. We can then query subtrees and update a node in O(logn) with some tree to maintain prefix sums.

The way to query paths is not much different, instead of creating an event for when you enter, you must also create an event for when you exit the node (2 copies). This is because you want to ignore nodes not in the path: nodes with event that end before current one begins in the euler tour. Why are these not in path? Because an exit/ending event indicates backtracking, and if it backtracked from some node A before going into the current node B, node A can't possibly be on path from root to B.

If we visit the nodes in the order [1,2,3,4,5,6] the euler tour we build is [1,2,3,3,4,4,2,5,5,6,6,1]. Notice each number appears twice, one to represent entering and one for exiting (backtracking). Updating a node can be done by adding v in the start position and subtracting v from the end position of a node. Updating subtrees can be done with some range update ideas/keeping track of frequency of starts/ends in some interval. Querying can be done by finding the sum of numbers up to the first position the number shows up.

In the recent snackdown round A qualifier, there was a problem I could not figure out.

Link: https://www.codechef.com/SNCK1A19/problems/AVGMAT

From skimming the solutions and from making my own observations I have realized the following:

• Most solution use some type of DP with two passes storing DP1[i][j] and DP2[i][j], where i and j presumably mean row and column.
• For any given distance D, there are O(D) other nodes D away in manhattan distance
• We can construct ans from dp1 and dp2 where ans[i] stores the amount of pairs of nodes i away from each other in manhattan distance

The editorial is not out, as codechef editorials can be quite slow (some in 2016 still pending).

Can anybody explain the solution here?

EDIT:

Possible solutions:

• Prefix sums over diagonals (previous mentioned observation), dp1[][] and dp2[][] represent theses where each of them deal with a diagonal in each direction

• Rotate the matrix by 45 degrees. Now you can solve it with normal prefix sums (over columns and rows) or matrix sums because the distance will be a "square away". One such conversion method is mat[x][y] --> mat[x-y][x+y]. Note that this conversion is space inefficient, and therefore you may need to define a NxN matrix as mat[-n...n][0...2n]

• FFT and mathy approaches .-.

I am sure we are all familiar with Machiavelli's book The Prince. He says ends justify the means. But higher rating doesn't justify current system to handle cheaters. Cheater can send in code and get his rating skipped if he do bad, and if he do well he profit. We need negative penalty rating and banning cheaters. Ends don't justify means here, because higher rating through cheater is meaningless.

Fair people suffer (get lower overall standing) because cheaters boosting themselves up. Stop this cancerous behaviour on cf.

Hello guys, if you analyze a lot of past codeforces problems in div2 you can notice knowledge of standard algorithms/ds is useful but not necessity. That segment tree solution can be done with set, or with prefix sum style sweeping.

Actually the most important "algorithm" in these problems is using your brain as someone said here.

That is why I want to ask the community for some great ad-hoc problems that have made you think/taught you important concepts or observations. (For example, you can add X to a set of numbers in O(1) by keeping global variable) I think these skills of making observations/simplifying the problem/looking at the problem from different angles is something me and many other coders are lacking, and it would especially help someone like me who is good at standard stuff but quite lacking in problem-solving skill.

For some strange reason, my code to compress a directed graph into a DAG and run some process on it gets TLE on this problem 894E - Ralph and Mushrooms.

This is strange, because N = M = 1e6 at maximum. In addition, I used to have a log factor which I removed (using math instead), but it still gets TLE on test case 14.

My solution to the problem (41978175) is pretty much same idea as editorial, up until the last point. Instead of running toposort/dp on the DAG, I just traverse down and take the maximum path, but complexity of the function should still be O(N+M).

I am baffled by how this would TLE, can anybody give me some advice on constant optimizations or how the complexity could possibly be worse than imagined?

There is a problem that I have noticed recently to be a subproblem in many string dp problems, especially one where you want to either "include" or "exclude" a certain substring when considering your answers.

This problem is "maximum prefix of S that matches given i characters already match and we add the character c". Basically it is useful because at each point in our dp we want to know how many characters we are matching (how much we progress to a good/invalid state).

For example:

S = "lololol"

i = 3, c = 'z' would represent "lolz", and the match would be 0

i = 3, c = 'o' would represent "lolo", and the match would be 4 because it matches with the prefix " lolo lol"

Naive O(alphabet * N^3) solution is to loop every size, (a-z), then try every prefix size, and compare string in O(N). This can become O(N^2) with hashing or some string algorithm (what I had to resort to, but it is a pain).

However, there seems to be an easy to write DP solution.

The DP is briefly mentioned in this div3 tutorial (but with only 2 characters): http://mirror.codeforces.com/contest/1015/problem/F

However, solution code does not contain an implementation of it.

After some digging, I found tutorial to this problem used exactly same dp.

DP[i][char] represents value as defined above.

Implementation of tutorial looks something like this (notice pattern is zero indexed, so i-1 is the i'th character):

for (int i = 1; i < m; ++i) {
    int prev = next[i - 1][pattern[i - 1]];
    next[i - 1][pattern[i - 1]] = i;
    for (int j = 0; j < 26; ++j) {
        next[i][j] = next[prev][j];
    }
}
next[m - 1][pattern[m - 1]] = m;

So maybe I am just slow, but it really does seem like magic right now!

Now I want to ask, what is the idea behind this O(N) dp. For example, why is it always optimal to build off prev, and what exactly does prev represent (I'm assuming it is the biggest match beforehand excluding a full match).

Yes, instead of saying I need "help with problem" or "help with algorithm" where instead I just want you to help debug, I will be straight with you.

I need help debugging.

I have tried debugging for 3 weeks, but no progress.

The problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=230

My Solution (10/11 cases): https://pastebin.com/4kdzmf4F

My solution's idea is basically same as editorial's: convert graph to tsp problem and do tsp like bitmask dp.

But now on RxC = 50x50 and N = 15 case it gets MLE/RTE.

My ideas for what's wrong:

1) Stack exceeded because too deep recursion -- > it's probably not this because I change recursive dp to iterative deepening but it still don't work. (loop decreasing order and call solve())

2) Segfault in dp table -- > I cannot find how it will segfault, I stored 2^16 values for 0...15 element bitmask. 15'th element is ghost island I made so you can start at any other island.

3) Some other memory error -- > I am not experienced enough to find out!

Help me this has been bugging me for so long.

According to animeshf, it is possible: his comment

But the implementation link he shared is expired so the implementation is gone! I'm confused one how to lazily propagate changes in the second dimension, more specifically how to store the lazy updates in a way so that both operations are logn^2 worst case.

Any ideas here?

I cannot find any good list of dynamic/implicit segment tree problems. Can anybody share good dynamic segment tree problems?

Here is my AC code: https://hastebin.com/ewobuzater.cpp

It uses offline BIT + sorting.

Here is the strange thing: que[200001] works perfectly fine, but if you change it to que[200000] it will segfault. However, it is zero based indexing and q is at max 200000.

Can anyone think of a case where que[200000] faces out of bound access?

Hello,

I have recently been doing this problem 701F - Break Up.

While it does not have an explanation in the official editorial, some user made an informal editorial.

I wrote Tarjan's for finding bridges, but then realized such a solution doesn't even pass the samples because a bridge is only guaranteed to split the graph into two components, but not necessarily separating the vertex s from t. How can I modify the algorithm to only consider bridges that split s and t?

UPD: Ok. The solution I tried was to dfs rooted at s, and for each dfs call update where t is reachable from the current vertex. It gets WA on 98. Is the thought process behind this correct? (Or is different solution intended) I want to make sure I'm not looking for nonexistent bug.

The writer is wo_

Time

Scoring Distribution

ABC: 100 — 200 — 300 — 400

ARC: 300 — 400 — 700 — 900

https://arc090.contest.atcoder.jp/

https://abc087.contest.atcoder.jp/

Let's discuss the problems after the contest :)

Hello,

I was doing this problem and was getting TLE on the last two test cases.

On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.

According to this benchmark, stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.

In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.

You can try to submit my solution and it should AC. But if you replace "stable_sort" with "sort" it will TLE.

Does anyone know which types of cases stable_sort can outperform sort?

Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.

According to a comment by ffao, Codeforces reserves 256MB to stack size by default.

However, my solution that does not exceed 1e7 layers of recursion in this sample 33910932, yet it RTE's because of too deep recursion. (I had to write iterative solution to get AC)

Supposing each 64 bit int uses 8 bytes, and a pointer in a 64-bit compiler would take 8 bytes. 1e7 * 16 bytes = 160 megabytes.

Is there extra memory usage I am unaware about? Shouldn't this be able to squeeze under the size limit?

Here is the Atcoder ARC/ABC — D problem from today's contest.

https://arc088.contest.atcoder.jp/tasks/arc088_b

The editorial describes an O(n) solution.

My question is about a different solution. When I first saw this problem I thought binary search on the radius would work, but quickly discarded the idea because I could not think of a correct "check" function to see if a given radius works.

However, minimario proved me wrong.

Here is his code: https://hastebin.com/qefuquxoke.cpp

In his check function, he assumes that "k to n is fixed" and "0 to n-k-1 fixed", which seems to be the basis of the function's logic. (I ran his code by hand, but it still feels like magic to me)

Can anybody elaborate on the reasoning behind this solution?

http://www.usaco.org/index.php?page=viewproblem2&cpid=597

I wrote multiple solutions for this problem:

My approach: - Store values, multiply them by two. This avoid errors in dealing with floating-point values - Precompute prefix and suffix: at every point store the value of radius necessary to destroy all haybales to the left (prefix) and the right (suffix). - Binary Search on Size of initial Radius (of explosion) - Binary Search of location - upper_bound/lower_bound inside to check for location, and then check if possible location using prefix/suffix values

I have tried to debug this for about a week, I asked about 4 people, and I changed my method and I still get WA with binary search.

Some things that I tried: - Wrote slower code for less chance of error; this code produces same output - Changing upper and lower values of binary search to the only possible locations of haybales (I changed it back because this had no effect)

Some things I haven't tried: - Throw away prefix/suffix and check it in O(n) <-- (now I tried, it worked)

Should I completely changed my approach? I think this approach can go. If it is just another bug (hopefully), does anyone have an idea what the bug is?

EDIT: I solved it thanks to Noam527 and WhaleVomit — wv made me realize my suffix and prefix ignored the case where the optimal simulation does not travel along adjacent hay bales. Also Noam suggested O(n) checking (which worked).

EDIT: Resolved.

This is what codeforces looks like on my browser (chrome):

The side menu is completely missing!

It's been like this for the past week. Everytime I try to open the problemset or check contests I have to search it up separately, making the site very hard to navigate.

Anyone know what the issue could be?