You can write untested code and submit. lol

Please don't be offended. In my opinion, down/upvotes should work as a measure of how useful that piece of information is. Your blog, unfortunately, is not useful to most people in this community. Simply because it IS a competitive programming community.

Maybe I misunderstood it, but isn't this only about running native java code inside a java sandbox? Thanks for the help!

Yes, problem difficulty wouldn't change at all, as you would have to consider only one component to build the maze, and fill the others with bushes.

In the last contest I participated I had problems when submitting a hack. Is that related? The submitting form would not show up.

There is really only one USA contestant on site, it looks like he came with the Chinese team (straight from China).

Looks like he got WA on the last 13 minutes and then solved the problem just in time.

I know this is rather old, but as a reference, I'll leave the link to a problem that requires this optimization: http://codeforces.me/problemset/problem/815/C

The contest announcement comments and the editorial and its comments are a good resource to learn about it, see the proof, etc.

Could you help me understand what is needed to maintain the slope segments? I can build the graph by hand, but I couldn't understand exactly what the accepted codes are keeping.

USA's election for president. As there are only two parties, "almost-ties" are frequent.

Ansewered you on GitHub, seems an error on CF API.

Sorry, but what is a blackhorse or an RHS?

edit: lol, just a question guys, no need to downvote... Doesn't seem wrong or offtopic for me.

APIO 2016 Fireworks uses this, but is a much harder problem.

You could keep both the key (value) and a counter (how many are represented on the node).

EDIT: sorry, you actually should check whether an element has already been added or not, as according to the problem statement, an element is only added if it is not in the tree yet. You should check if the element exists, then add it it doesn't.

EDIT2: Something like this:

bool find(node* t, int val)
{
    if (!t) return 0;
    else if (t->key < val) return find(t->r, val);
    else if (t->key > val) return find(t->l, val);
    else return 1;
}

Try this one:

7
I 4
I 5
I 7
I 7
I 6
I 2
K 5

Try producing other tests and using them to debug your code. Print the tree traversal, and the value of the nodes you are entering into when searching for an element. It should give enough input to debug.

Pseudo-random number generators work like this: from a seed number, they generate all the other numbers. If you seed it with "srand" with the same seed every time, it will always produce the same numbers. Doesn't mean it will produce repeated numbers, only the same sequence of numbers. However, if you don't comment that line, your program will always generate a different sequence of numbers, which in turn produces a different tree (as node priorities will be different across different executions). So, to produce always the same tree, you should comment that line, but it should work fine nevertheless.

EDIT: what you're doing in your code is seed rand with a different number everytime, as time(0) returns the current time.

Have you disabled "srand"? If you are seeding the random numbers with a different seed everytime, and your treap is bugged, then things like that can happen.

I like to start debugging treaps by commenting srand and always printing a tree traversal to see if everything is ordered, etc..

Your code fails for this test:

5
I 6
I 4
I 6
I 2
K 2

EDIT: modified to a shorter one

Well, because even though system tests are wrong, system tests are not available until after the contest and shouldn't be taken into account.

It should be rated if pretests were ok.

Stop flooding just because you didn't like the contest, please.

It isn't much math, really. There's no need for ternary search. You have to consider the circumference the the polygon is inside, then the only observation you have to make is that after fixing the size of the arc, any point would suffice as midpoint. (consider a, b and c as points of the polygon. For simplicity, a=1. Also, a < b < c. Then, for every c you choose the angle formed by acb (in this order) is the same).

OJ to practice with JOI Open Contests from the past 4 years: https://oj.uz/problems/source

Do you have any strategy for finding errors like this? lol I have been seeing a lot of these recently (in my own solutions)

Sum of all x: x * (x+1)/2

Sum of all y: y * (y+1)/2

How many times each value of x is summed: y+1

How many times each value of y is summed: x+1

So: x*(x+1)/2*(y+1) + y*(y+1)/2*(x+1)

Which is simplified to (1+x)(1+y)(x+y)/2

Ah, I see, but I think codeforces cheating detector will find this.

His code works just fine, he just used a #define for each original line. The compiler will replace the defines with the correct code before compiling.

why is this cheating?

edit: ok, I think obfuscated code is not allowed, but he's the only one that will loose points because of that (in case of a possible hack that didn't happen)

Maybe author commited a mistake while writing the problem statement, but he described the other problem when telling to others.

You're supposed to post in english under the english part of codeforces. I suggest you edit it before the downvote flood. lol

Sum of x+y for all points in the rectangle determined by x and y is (1 + x) (1 + y) (x + y)/2. It is enough to test only points which have integer coordinates, as only lattice points have trees. So, iterate y from 0 to b, determine x and use the formula. There are less efficient solutions, and also there may be a O(1) solution, but this works just fine.

By the time people complained about D, many other contestants had already spent a lot of time trying to solve it. Thats why things are not that simple. It really should be made unrated, as everyone expects a WA to be a WA and so on.

Search the comments here in this page...

Greedy maybe?

No need for merge sort tree if queries come after updates.

There's a harder version here: http://www.spoj.com/problems/ORDERSET

I think the most classical idea in this problem is "noticing" you are dealing with an alphabet with 26 letters, so you can preprocess individually. Exploring this idea is useful for a handful of problems that have different approaches. Even tries would not have the same complexity if your alphabet was greater. You could find a longest non decreasing subsequence of characters in O(26*n), as another example.

http://blog.ezyang.com/2012/02/visualizing-range-trees/

You can do in O(log n) using a binary search tree, a BIT or a segtree... all of them support binary searching in O(log n)

Nice, thanks! I had seen it before, but I thought it only had statements in Korean.

There is a tool in the website to migrate all your submissions. However, it is currently not working. I think it is related to MAIN being offline.

I see it actually has some problem statements in english, but most of them are in polish and the site has the side menus in polish.

Thanks, I can at least submit there and use google cache or the wayback machine to read problem statements that were in MAIN.

I suppose the judge had a bug, and it was solved, but his submission wasn't rejudged.

(Yes.)

Yeah, but GNU C++ should include it. Maybe its because CF runs on windows?

Show us the code

But would it pass if it had compiled?

Codeforces is probably experiencing problems

Check my new update.It should make things clear now.

I also modified your code a bit:

http://codeforces.me/contest/319/submission/23075126

I like to write put an eps value (1e-12) just to be sure with doubles.

Also, the way I learned, my function "useless" is different from yours. I'm not sure if it makes any difference. (I'm testing if left crosses right before left crosses middle, instead of testing if middle crosses right before left crosses middle).

I think it doesn't make any difference at this case, and I used your version to prove my point above.

I too don't understand codeforces users behaviour. There are lots of upvotes on jokes, but almost no upvotes on interesting stuff. I think some posts asking for help should be downvoted however, thinking about those which question has been answereda thousand times on the internet. See this, for example: http://codeforces.me/blog/entry/49132 . It's just useless.

Ok, done with my complaints lol. I made some tests:

http://codeforces.me/contest/319/submission/23074890

The situation you described never happens on the testcases (cur never points to an empty line). I'll try to think why.

EDIT: More strictly, you never remove the line that was chosen as cur:

http://codeforces.me/contest/319/submission/23075005

I'm pretty sure this is related to the problem. I think the fact you'll never remove the line that was chosen is true and can be proved, but I can't get to it.

EDIT 2: Ok, my last statement is true. Here's why (drawing will help):

So you choose line r for a given a_i. Now, the next line we will add to the convex hull is going to cross the y axis at the same y-coordinate that line r has when x = a_i (this is because of the DP recurrence). b_i is always greater than zero, so our new line will cross line r at an x-coordinate greater than a_i. This way, our new line crosses line r at a x-coordinate greater than the one where line r crosses the line before it. This way, line r won't be "useless" and won't be removed.

This is an explanation about why your code works. Note that, the way I see it, your solution works because of the way the DP recurrence works. Maybe its a more general property, I don't know. You can try playing around for yourself.

Some useful stuff... Indent code, space between operators, create functions for things you repeat, and also for some of the things you don't. Name your variables and funcions well, declare variables the closest possible to the necessary scope, try to be concise when writing conditions and such. I like to use C++ ranged loops when possible, and also lamba functions when they are useful. Using STL objects such as pairs and typedefing some structures is very useful too.

There's no trick, really. I like to go reading other's solutions to past problems and pick up the ideas from other's codes. It's important you code them yourself.

https://web.archive.org/web/*/acm.sgu.ru

I think this would be better discussed at the issues page on the github repository.

However, which version of VIM are you using, the function matchstrpos should be native, it looks like your VIM version is lacking it.

I just fixed the second error, sorry for this. Please update and check if it is working.

You actually don't need to setup the keybindings, they are already configured by the plugin.

EDIT: I tried replacing the function that was missing on the first error, please update and check if it is working.

First, you have to setup your leader key (http://usevim.com/2012/07/20/vim101-leader/) to use the keybindings (note they start with <leader>).

Some commands can be used anywhere, such as login, and list submissions. Others may be used while writing your solution.

Suppose you are writing your solution for problem 342D, name your file or fold hierarchy as mentioned in the repo README, eg: 342D.cpp. Then cfparser.vim will recognize the problem your dealing with when you run the commands to download tests, test your solution, read problem statement and submit your solution.

To run the command that submits your solution, for example, you must be logged in and press the <leader> key, followed by c, f and s.

diff is a linux utility to compare two files. It is included in most linux distros by default. In cfparser.vim, diff is used to compare the expected output and the program output.

Auto comment: topic has been updated by gabrielsimoes (previous revision, new revision, compare).

You can also pick any problem about LCA to practice this topic, like SPOJ LCA

RodionGork is active at his github profile. However, the organization account for the translation repo is not, and there are 6 commits waiting for response. I don't know, you could try contacting him somehow. It really is a great project.

Thanks for the reply!

Yeah, you did prove. People who remember DSU's proof will most likely understand. I stated a more extensive proof would be better thinking about people who don't exactly know the proof. Don't take me wrong, but they may get a little confused reading this proof.

I mentioned my code exactly because everyone has a different opinion,. Maybe it'll help a later reader, that's all.

I think what you called "binary accent" is referenced as "binary lifting". Great article by the way! Thanks

On problem B editorial, I think the part "Then we need to make cnt[a_i] –  and add the value cnt[a_i  -  cur] to the asnwer." would be better as "Then we need to add the value cnt[cur - a_i] to the answer and increase cnt[a_i]". I don't know if I'm correct, but it was the way I understood the solution. I'm considering cnt[x] starts empty before iterating. Maybe you meant the oposite, and cnt[a_i] should be decreased before adding cnt[cur - a_i] to the answer, but it was not clear from the editorial statement.

Look at a set of siblings, the array of direct children of some vertex. Then, after shuffling his array, there is nos reason for a vertex u to appear more than half of the permutations before v, as all permutations are equiprobable. That is, by symmetry, half of the permutations will have u < v and other half will have v < u.

You can extend this to the subtree of vertex u and v: a children x of vertex u will have 1 / 2 probability of happening before vertex v (think like it will inherit the probability from its parent) and also x will have 1 / 2 probability of happening after a vertex y that is a children of vertex v.

OP said it'll be posted soon, just wait!

Try reducing the number of times you compute modulo. http://codeforces.me/blog/entry/46009?#comment-304869

MOD2 could be any multiple of MOD,

From what I understood, it should be "2 1".

Usually the golden rule is that a computer can handle around 10⁷ operations in around one second. However, this applies to big-O analises because it usually omits a lot of constants. In this case, it's just a simple loop, so 10⁹ operations run easily in one second.

Suppose we generate all possible arrays for dfs in-order permutation, all of then equiprobable. Let's denote t_v the time of vertex v and N the number of permutations we computed.

You agree ? Where t_v is the value a given vertex would have in permutation p. is outside summation because all permutations are equiprobable, so all of them have probabilty .

However you may notice this is the same as . For every vertex u, u will be visited before v:

• in 0 of the permutations, if u is inside subtree of v.
• in N of the permutations, if v is inside subtree of u.
• in N / 2 of the permutations, otherwise.

Then, we get to the equation mentioned.

Check my comment above.

.

We will denote E(v) as the expected time value of vertex v (the answer for v).

Then, we will compute the answer based on the probabilty that each vertex u ≠ v is visited before v. So , where p(u) is the probability that u is visited before v. Then we will have p(u) = 1 in case u is an ancestor, p(u) = 0 in case u is a children and else we will have p(u) = 1 / 2 .

We have depth[v] nodes with p(u) = 1 and n - sub[v] - (depth[v] - 1) nodes with p(u) = 1 / 2, which leads us to the formula.

Edit: Actually formula on the editorial was wrong, it should be n - sub[v] - (depth[v] - 1), where depth begins at 1.

Check this, the approach is a bit different: http://codeforces.me/blog/entry/45991?#comment-305083

Thanks for this, I found it much better to understand than the editorial

Ah, yes. I was confused again with complete binary trees.

Great post. If you explained the idea before showing the code, it would be better to understand. Also commenting the variables meaning in the code would be of great help.

It would be good to mention that most solutions will answer the queries offline, which may be a problem sometime (maybe someone didn't notice this lol).

Also, it would be nice to post hints about the solutions.

Proving explicitly why it is nlogn would be good too (ie. as each node's subtree set gets merged into one set of size equal or greater, and the base set has size 1 and the last set has size n, then we take logn steps to go from 1 to n. Summarizing, each node gets merged logn times, so the total complexity is O(nlogn)).

Here's my solution to 343D, maybe it will be of help to someone: 18958875. A lot easier to code than the one in the tutorial.

Maybe I misunderstood your approach, but shouldn't the cases be:

if (maxdepth[v1] == maxdepth[v2])
    complete[v] = complete[v1] && complete[v2];
else if (maxdepth[v1] + 1 == maxdepth[v2])
    complete[v] = complete[v1] && full[v2];
else if (maxdepth[v1] == maxdepth[v2] + 1)
    complete[v] = full[v1] && complete[v2];
else
    complete[v] = 0;

However, I'm still cofused with the conventions, lol. I think a full binary tree is the one in which all nodes which aren't leaves have two children. If I'm correct, what you called "full" would be "perfect".

Ah, it might be good for learners to state this approach is kind of a DP one.

Yeah, that's what I meant. Only clarifying MaxDepth[v] would be the depth of the deepest vertex in the subtree of v. You said it, but writting in another way: first vertex would have depth 0.

Well, you know how many nodes should be in a tree with k levels, right? Just compute how many levels are in each subtree and check if it matches with their size.

EDIT: according to what op said below, this would be an approach to verify if the subtree is a perfect binary tree, not a complete one.

Could anyone tell me if that will work?

Ah, I get it now.

The two cases are: when the range will be determined by the lines tangent to the cirumference which pass through the cockroach's starting point and when the range will be determined by the lines which pass through the cockroach's starting point and the points of intersection between the two circumferences. You can determine which case is this by comparing the length of the segment from the point of tangency to the cockroach's starting point (tLen) and r0.

In the first case, the angle can be determined through triangle similarity. In the second case, you may derive the equation from the triangle formed by the center of both circumferences and a point of intersection.

I also didn't get it. If someone could explain why divide in two cases, it would be of great help.

Well, if M is really small, you can compute hash for all possible words of size <= M inside the string N. Then, just compute the hash for the ith word and check if the same hash was found inside the string N.

Edit: this would be O(n*m + q*m)

You may want to change your post title adding the problem name on SPOJ, so that people looking for some help on this problem may find this post easier.

https://github.com/gabrielsimoes/codes/blob/master/SPOJEN/pt07f.cpp

Here is my solution. I tried to comment it so it will be easier to understand. The function that builds the lists of chains is a bit confuse. Just contact me if you have any doubts.

I may try solving it later, but I found two resources that might be interesting to you:

https://github.com/dragonslayerv2/Competitive-Programming/blob/master/spoj/PT07F.cpp

https://apps.topcoder.com/forums/?module=Thread&threadID=688173&start=0&mc=2#1290229

Why x₁ - x₂|lcm(c₁, c₂, ...) ? Wouldn't it be the oposite?

You said that if x = k * (a * b * c) + t then . This is not true.

However, it is true that

Start by noticing that palindromes with even number of digits are made of two equal parts. That is, if you cut them in half, both parts will be equal, but reversed.

You may want to change "appearance" to "visibility" for better understanding.

What is "manhattan distance <= const" equation? Wouldn't that be |x2 - x1| + |y1 - y1| + |z2 - z1| ≤ const ?

Actually not. If it compares equal, the candidate is necessarily a centroid, as there would be a subtree with n/2 nodes and another (or more than one) with n/2-1 nodes.

Thanks, it works declaring sub and msub as double. Didn't think this would affect.

Can anyone help me debug this?

This solution got accepted http://codeforces.me/contest/686/submission/18688448 And this got Wrong Answer: http://codeforces.me/contest/686/submission/18688414

However, the only change I made was comparing the subtrees of the centroid pretender and the current node, at line 28. This shouldn't change the program's behaviour. I'm following this solution: http://codeforces.me/blog/entry/45556?#comment-301968

You may also want to check for n = 7^3 and m = 7^4, or 1 and 7^7

Yeah. But I have nothing to complain. I would have failed in two problems if they were weak. LOL

Yeah, Div2C/Div1A had a really bad english problem statement. I managed to understand it, but it must have been hard for some contestants whose first language is not english.

Check Brian Bi's answer to this: http://stackoverflow.com/questions/8716934/longest-increasing-subsequence-lis-with-two-numbers/8719900#8719900

I recommend you try think and find out what he means with a "staircase-like data structure"("coastline"). However I could try to explain it.