this indeed seems like a typo chromate00

In problem G do negatives happen? If yes, how are they supposed to be handled?

Happened to me. Maybe check if you're handling $$$A=B=1$$$ correctly.

For C you either use only L or only R, so you can try both and take the max. For the proof:

• First you can realize that if you reach the extreme on the left first then you can use only L at the beginning and then only R after reaching it. Similarly if you reach the extreme on the right first, you only use R at the beginning, and then only L. With this I think you could already use some data structure to solve the problem.

• If you take an optimal solution. In the first case (first use L then R), if you replace some of the L into an R the maximum distance either doesn't change or increase by 1 or 2, so by doing this you end up with a solution that has only R and is just as good or better.

One way to do it, is to use a sparse table to do jumps where before the end of a jump you move without changing $$$y$$$ and then to move to the final $$$x=e$$$ you first need to move to $$$y = L_e$$$ or $$$y = U_e$$$. This allows us to have a reasonable number of states by also having for the initial $$$x=s$$$ a $$$y = L_s$$$ or $$$y = U_s$$$. Then the sparse table allows you to do many of these jumps quickly, and you move forward as long as you don't go beyond $$$t_x$$$.

Additionally to precalculate the jumps you also need a couple of sparse tables, and you need to do a jump from the initial $$$s_x$$$ (but you can reuse the code needed for the precalculation).

You can check my submission for an implementation.

Instead of just returning a count you can return a count and also the position where it is reached. Also there is a maximum count you don't want to exceed and you need to remove a prefix which is not within the range of the query. You can take a look my submission

Your precomputation step's complexity is actually $$$O(nlog^4n)$$$.

For each of the $$$O(nlogn)$$$ level changes you do a binary search which adds a $$$O(logn)$$$, and your query method has $$$O(logn)$$$ calls, and calling lower_bound inside adds an extra $$$O(logn)$$$.

I actually had the same issue, the query method can be changed so that the binary search is done inside the query.

Buth both c and y are int

When calculating $$$c*(y+1)$$$ you may have an overflow.

Whether the order of the hashed values matter depends on the hashing function, the XOR hashing or sum hashing mentioned in the article linked in the editorial are actually independent of the order. For the sum hashing (which is the one used in the editorial's solution) in particular the hash will be different if a particular element repeats a different number of times in both multisets.

This is similar to the alternative solution in the editorial, you would obtain it by decomposing the $$$(m-c)!$$$ in odd and even terms, then use the even ones to simplify the $$$(\frac{m-c}{2})!$$$, leaving you with a power of two and the product of odd terms.

Proof of the complexity would be the same as for the stack. You do n pushes into the stack and each element is removed at most once, so the number of removals is at most n, thus the complexity is O(n).

It is doing the same thing as the stack solution, using the sol array to keep the stack

If I understand correctly, you're considering the interval can start at some $$$a_i$$$ and finish at $$$a_i + x$$$, but you may be missing the cases where it can finish at some $$$a_i$$$ and start at $$$a_i - x$$$.

To handle this I used a copy of the array with the reversed sign, and then you can take the min between both cases. Code

Yes, the Japanese version is normally available immediately after the contest (like in this one) while the one in English can take a bit longer.

AtCoder people don't watch Japan's Basketball match? :D

What is the background of the teachers in these schools/educational institutions?

What are the differences between CF and NOI that affect yours and other people's performance?

Do you perhaps mean $$$\gcd(S) \geq 2\gcd(S')$$$ in the second part of the first item?

Here as well, but with small k.

If they're not disjoint, you can still remove the common part and obtain two disjoint intervals with equal XOR.

I think I also failed the same test cases when I missed the case when K and N are equal

I think you wouldn't need to use them all though, if you take one with less or equal than n, then you only need to consider additional cycle sizes such that the primes different from 2 and 5 are not factors of the gcd, so every time you consider one more cycle size you divide the gcd by at least 2, meaning you only need $$$O(\log n)$$$ in total, the product of which should be smaller than X (and also their lcm).

No need to consider borders, the constraints discard this happening.

I failed the same two cases because of not considering that for a few turns the partial damage of an attack can be better than the full damage of another attack, since I see you have only max(a1,a2) in your code, you may have the same issue.

Yes, there's an update about it now

How could this code be modified to work in some modulo? I've tried to modify it for this problem about polynomial multiplication, but got TLE (you can find the code for my submission here). In this case using int alone gives WA because of overflow, so I had to use an intermediate casting to long long before applying the modulo.

seems to be mentioned in one user editiorial in japanese

You have Quantiopian which should be similar.

You mean AI like Game AI, or like Machine Learning?

I was thinking a checkbox asking whether you want to automatically submit Large in case Small is right would be useful.

I'll rember including cstdlib before using srand.

The particular thing in the problem is that the value of o is 2, this gives you the equivalence between solving the main problem and the two subproblems

Since you're using the maximum matching it has to be optimal. Upgrading happens when you modify one occupied cell in one of the two subproblems.

You can divide the problem into one problem for rows/columns (x, o) and one for diagonals (+, o), the first can be solved greedily, and for the second one you do a maximum matching between the diagonals that haven't been used (as long as the edge represents a valid position on the grid).

I'm at Barcelona this week and can confirm Barcelona is great, weather is really nice even during winter and the beach is close. By the way does someone know if individual registration is possible and what's the cost?

Seems related to these two TC editorials (D1-1000):

https://apps.topcoder.com/wiki/display/tc/SRM+518 https://apps.topcoder.com/wiki/display/tc/TCO+2012+Round+2A

Aren't these the problems with the constructive algorithms tag?

Any ideas on how to solve G? I couldn't figure out how to use the second condition.

Yeah, it's the Max-flow Min-cut theorem

In the editorial for C shouldn't the -1 in the inequality be +1?

So, you don't actually need to make the comparison with the greatest element in L, just splitting R in  ≥ 2c and  < 2c, and then inserting all the elements in the second treap one by one into L would also give you the same complexity.

In D3, shouldn't the base cases be dp[0] = dp[-1] = 1, so that it can cover the case when a segment is made with all available columns?

Weird, I tried that link yesterday from my phone and it didn't work, it worked today from my laptop, though. Thanks.

Is the user database the same as the one for the old site? I had already registered in that one and apparently I can't recover the password

Since you know the total sum, once you know the sum of the positive terms you can calculate the sum of the negative terms later.

You can improve that by a factor of two.

If one of the organizers is looking at the post it would be good to indicate the last date when the DCJ testing tool was updated so that we can know if it may be necessary to update it.

Nice site! Would it be possible to add a list of the failed problems? It would be useful in order to go through them once again easily.

It's been a while, but do you mind explaining your solution? It seems to be quite different from the others from what I saw in your code.

Seems to me like what is being built is this: https://threads-iiith.quora.com/The-Bridge-Tree-of-a-graph

I was trying to understand F with the definition of biconnected component as given for example here, but it seems the one being used in all the codes is not quite the same. For example the graph with edges (1,2), (1,2),(2,3),(2,3) would consist of only one component instead of two. Is this okay or am I getting something wrong?

If the only API interaction was for getting the text it should also be possible to make it work with Codeforces' talks, right? :D

Suppose in the previously mentioned problem you coded a recursive solution just to see what is happening in the output, which can be useful sometimes, and then while (or after) coding it you notice that prefix sums are useful, then you will need to either code the solution again, or copy some of it and fix it, coding it again is not optimal for competitions with a limited amount of time, and copying it could introduce unexpected bugs, then why not just code the iterative at the beginning?

And, you can also use the iterative solution to decrease the amount of memory you use.

Latin America, Peru, Universidad Nacional de Ingeniería

josue.0 dmansilla07 Victoralin10

But, interns only need a J1 visa which is not as complicated as those others.

Right, I didn't notice that. Thanks for the explanation.

In the editorial for problem F, when it says "If x_turn is shining, then pos' is shining as well, so we could have finished our turn there.", isn't that only true if x_closer2 <= pos'?

Also, how can we justify that it is optimal to stay at an endpoint when x_turn is not shining?

Anyone can explain how the Wavelet tree is being used in https://www.codechef.com/AUG15/problems/DISTNUM ? From anta's code it seems like it is indeed what is being used,

They sent a form where you could choose the date you preferred, I guess they won't be assigning you the other if you didn't choose it.

You can start by calculating the maximum number of groups you can be from these graphs.

Shouldn't the editorial be unlocked even if you solve the problem after the contest?

Great, thank you.

You've successfully challenged the testing system.

Do you know if we get to choose the dates?

I took the test, but there was no place to choose that in the form.

couldn't resist

But seriously, do you mean during a contest or when training?

you can solve it with Fenwick tree by first calculating: sum(i = x to n) (x — i + 1) x (x — i + 2) , you will get a polynomial of degree 3, then you can use four BITs to heep all necessary information.

mayble a google doc or a github repo with a file for each editorial?

Add the denominations in increasing order. If you already have interval [1,x] and none of the already existing denominations can help you increase it, then if you add a denomination greater than x + 1, you won't be able to make (x + 1), if you add a denomination smaller than x + 1 you will get a smaller interval.

Greedily add the smallest coin you need.

Did the same thing, except for the last step, you could check that the total product was -1.

What is the k in your state?

I used DP in segments of length equal to a power of 2 and then merged them to solve the queries. You could also do that with a segment tree.

Code: 6427362

You do a DP keeping an increasing sequence of powers of 2 by using a bitmask.

Could some team share their approach for problem R from the Electronic Contest? We picked a pair of rows and made some vertical moves, and then only horizontal moves.

Maybe here: http://internetolympiad.org/

Any hint for problem I? I saw that the sequence could be reconstructed, and was thinking about using DP to go through the sequence. The condition of being independent appeared in a recent round, but I couldn't find a way to express the condition of dominating in a recurrence.

You can keep only one prime divisor for each number.

Also you could use an array of next multiple and array of booleans indicating whether a number has been used. You can use the second one to keep the other updated. I think that is faster than using vector <set > st

You can generate all numbers. To find the next number, factorize the current one, then you would need to take the minimum multiple of one of its prime numbers, which hasn't been used.

You also have: http://projecteuler.net/ http://mathalon.in/Mathalon/

There are some problems posted by Anton_Lunyov here: http://mirror.codeforces.com/blog/entry/1520#comment-29431

The archive.

When I go to the link, it shows:

The URL you requested has been blocked. URL = invalid

this one seemed a nice dp with optimization to me:https://www.hackerrank.com/contests/monthly/challenges/alien-languages

that is not completely true, when you filter by a particular tag, both can appear, they can also have different tags

hopefully it won't be my third consecutive unrated round :D

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=572&page=show_problem&problem=4142

You can improve it with this: http://wcipeg.com/wiki/Convex_hull_trick

I'm curious about what chinese coders consider easy, a problem very similar to B was the hardest one in the latinoamerican regional last year.

There are some at ZOJ: http://acm.zju.edu.cn/onlinejudge/searchProblem.do?contestId=1&titlefrom=0&authorfrom=0&sourcefrom=0&query=andrew

http://www.codeforces.com/problemset/problem/9/D

That's ok, but then the description should be changed, since it says there are statements in english, and the are two pdf files but both are in russian.

Look at it as the number of multiples in the range [1,n]. Then you get:

n/1 + n/2 + n/3 + ... + n/n

First fix, the numbers of books with thickness 1 and 2. Then you can find the minimum width of the books at the top greedily.

http://stackoverflow.com/questions/11382189/number-of-ways-to-place-kings-on-chess-board

Can people from any country participate?

By the way problem C is very similar to: http://www.codechef.com/ACMAMR12/problems/FSSYNC

which some (like me) may have solved recently.

You only need to do two sweep lines, one for the X queries, and another for the Y queries.

In each sweep line, you need to keep a counter that tells you the number of active triangles.

This is quite similar to my situation when I started. My country doesn't participate in IOI and I only heard about IMO too late. When I started at ICPC there wasn't any team from my country which had gone to the world finals. My team finally made it at its fourth regional, and again made in the fifth(and last one), so just train seriously and you can make it :)