Think of the most stupid solution you can do

Great editorial for problem G

What happens if you take medium?

Same thing happened to me :(

I think it's roughly equals to (number of CF users hit by meteorite fall) / (number of meteorite falls)

I like antontrygubO_o problems, but once Thanos said "Perfectly balanced as all thing should be", I feel that CF is missing this balance in the problems, I would prefer a bit of diversity in the problem set.

Yeah, that's definitely what I was looking for

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

I mean a filter for standings

Yet another screencast. The channel have focus in brazilian community so many videos will be in portuguese, but from time to time I maybe do something in english, or with no audio like this screencast

I suggest to create something as a collaborative repository to hold translations (or maybe just a short description of the problem) based in automatic translations, I think this could helpful to you and easier to be achieved.

Can anyone hack https://mirror.codeforces.com/contest/1285/submission/68545833 ?

What is TC9 in E ?

I did it, but WA62

UPD: It works, I have made a silly bug

You are a genius. I am already waiting for it.

In G, isn't possible to construct a case where taking the modulo during the calculations will lead to a wrong answer ? Like, endpoint A needs MOD to run and endpoint B needs 100 to run, if you take the mod the max will be B, but the real max is A.

D — Test case 6 is this test really right ? M = 11511 but there is only 1875 lines

I didn't pass the problem yet (seems like there is a index out of bound in my code), but I passed the case 5, seems like the statement is incorrect, link in this line you are comparing $$$a \lt = b$$$, but the statement says it should be $$$a \lt = b'$$$ right ?

What is the case 5 of D ?

I will give a few hints.

B: It's only necessary to know some parities to be able to say if a number is lucky or not.

I: $$$C = V - E$$$ Where $$$C$$$ is number of components, $$$V$$$ is number of vertex and $$$E$$$ is number of edges, you can pre calculate the value o $$$V$$$ and $$$E$$$ for each number, this doesn't work if there is cycles, but in the problem the graph is a cactus so you can count the number of cycles that you should exclude.

L: If you can solve the problem for $$$N = 2$$$ you can solve for bigger $$$N$$$, you should think about inclusion-exclusion here.

Good luck Emiso ❤️

I realized that in the D is necessary to consider the cases where there is a 0 in the range, but didn't corrected my code correctly, wasted a big chance :(

20 minutes of penalty is too much.

I used the same strategy and only passed my C++ problem in the last 24 seconds

I used javascript, C#, PHP, Ruby, Python 2, D, Java, C and C++ . It was fun like last year.

K: You can do with the same complexity but with trie and kmp, you build a trie for every word in the set that has length smaller than for every node in the trie you keep the the current answer and the last index last of the occurrence then updates this values running in the substrings of size smaller than of the text and for the rest of the strings in the set you do kmp. I don't know if it's faster, passed with 275 ms

Use another sqrt decomposition to know the mex value, you do updates in constant time and query in , since you make only N queries the overall complexity becomes

Can you explain the reasons or at least a idea about this formula ?

How to solve G and D?

Instituto Militar de Engenharia:
naumazeredo mccastro mutreta

Universidade de São Paulo:
yancouto victorsenam arthur.nascimento

Universidade de São Paulo — Campus de São Carlos:
samuelfgs rodz LoppA

Universidade Federal de Pernambuco:
tfg luucasv alpgc

Universidade Federal do Rio Grande do Norte:
victoragnez helio RailtonT

Universidade Federal de Campina Grande:

fmota
ME_AJUUUUUDAAA
ordan

The last year magic was canceled in the scoreboard

UPD: It's fixed

You end up in fourth in the contest and then the contest was declared unrated, so sad

Wow, nice tutorial.

The vector just keeps a pointer, so no .

For E, let's solve a simpler problem, suppose you just have to change the root and query the sum in a subtree, if we preprocess the sum of subtrees with the tree rooted at X, there's only three cases to handle when answering queries to a vertex V,
if (current_root = V), the answer is the sum of all nodes
if (current_root in V subtree), the answer is the sum of all nodes minus the sum of nodes in subtree of vertex that leads to current_root in the sons of V
if (current_root not in V subtree), the answer is the sum of the nodes in the subtree of V

To process the updates you have to find the lca(u,v) considering the tree rooted in current_root, the vertex is one of the nodes in {lca(u,v), lca(u, current_root), lca(v, current_root)} and then you process the update similar to the queries, to update a subtree and to query the sum in a subtree, you just need a bit and euler tour.

For D, you can use a implicit persistent segment tree to keep the values of the words and another to keep the amount of words with value equals to X.

Why "Idleness limit exceeded on pretest 1" in http://mirror.codeforces.com/contest/916/submission/34316902 ?

UPD: This happens because I am trying to read an integer in queries and removes

My code for D didn't passed the examples during the contest and now it's is AC, amazing.

Will the problems be moved to practice ?

Yes, https://ideone.com/61Va4F

Really bad issue with test cases, hoping for rejudging. First time that I won a contest. : )

" Brazil broke into the top! ... ". In this moment, I realized that I visited too much codeforces .

Is F an analysis of various cases ?

Good luck to you, I also wanna thanks to chessmaster , this was one of my motivations in the year, happily I achieved the objective before my regionals

Can you link one of this submissions ?

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/replace-27c5286c/ . This is a harder version of problem G. Also the editorial explains the complexity. My implementation http://mirror.codeforces.com/contest/911/submission/33747581 .

That was what I tried too, I tried to use block-cut tree to check if it is possible to reach but, unhappily I received MLE (Maybe the implementation was wrong)

How to solve Plat. 2 ?

What's the pretest 3 on C ?

I get the ideia now, interesting solution

https://imgur.com/a/rR4vK That was the answer that I received

This will create a discussion about the advantages that you get based on CF color

What you have done to being not affected ?

Probably the queue worked

9 ?

He is not a burden to me, ordan thinks the same, I don't know about the previous team. Why he would be embarrassed ? He has his religion and we can't do nothing about it. This team wasn't decided a day before the competition, we discussed the whole situation, the whole team accepted it. I am happy that I had the necessary to qualify to world finals and take ME_AJUUUUUDAAA to his second worlds. You don't know how we respect him, so your text offended me a bit.

In the world finals he will participate

It was the whole contest with two people, ME_AJUUUUUDAAA stayed with us, but didn't worked in the problems, because that day the sunset was after the end of competition, one of the rules says that an incomplete team will be disqualified so it was necessary. For who are in the same situation, one option is to use the reserve, we didn't choose this for especif reasons.

D?

Ignore ...

Clash with OpenCup. ;(

Is this a plug-in ?

When you use the second option, an element with key a1 is inserted on the map, so the runtime will be slower since you gonna have more values in your map

It's not impossible http://mirror.codeforces.com/contest/869/submission/31077410 , there are others, you can see it on http://mirror.codeforces.com/contest/869/status/C , just set the language to Java ... I don't think there is suck lack, look to the top ones in the rating and you gonna see that some of them use Java

Had you slept during the contest ? That was not a good decision

Well, I didn't understand your case, so I will explain the main idea in this problem, first we reduce the problem to:
We have a array A of size N initially every element is equal to infinity and we can do:
Update in position: pos k, make A[pos] = k
Update in range: l r k, for every element i in the interval [l, r] make A[i] = min(A[i], k)
Query: l r, ask for the sum of every element different of infinity on the interval [l, r]

So, to solve this with the idea of the segment tree, we gonna keep for every segment what is the biggest element in that segment, how much times the biggest element appears on the segment , the second biggest segment on segment, the sum of the segment and a variable to indicate the lazy propagation

If we gonna do soma update in pos we just change the value of the biggest element, how many times appear and sum of the node in segment tree that represent this element.

When we gonna process some update we gonna do the recursive procedure of the segment tree:
if the current node is out of the interval of update, there is nothing to process in this node
if the max element in the range of current node is smaller than k, there is nothing to process in this node
if the range of current node is completely inside of the range of update and the second biggest element is smaller than k, we gonna process this node, the only thing that will change will be the sum of the interval and the biggest element element also we gonna sinalize the lazy propagation
Else we gonna recurse to the left son and right son, after this we gonna recalculate the value of the nodes where the recursion passed.

If we gonna query, we just do the normal of the segment tree, taking the sum value of each node

If I would say the complexity it would be in O(QN) in a trivial analise, but my intuition say that it's faster. My code is 30763830 . Can you say what is the complexity ?

Well, the construction of the segment tree is in O(N) and solve every query in O(logN), in the sparse table the construction is in O(NlogN) and every query in O(1) supposing that you find the log2 in constant time but the complexity of the function log2 of C++ is not constant, so in your code every query is solved in O(logN), you can try to use :
__builtin_clz(1) — __builtin_clz(len)
Or preprocess the log2 of every number.

Looks like yes, in the tutorial in chinese they link this problem http://mirror.codeforces.com/contest/444/problem/C also, that can be solved with this trick

Think about divide and after join

Probably yes, try to optimize the query in the range and how you find the index of some string, I used a trie for example.

If you will solve a problem and know that your idea is right by a formal reason you gonna probably receive AC, but if you use pure intuition ( what I am doing in everything) you can receive a lot of verdicts and waste a lot of time coding for nothing. Also this can be just something that I thought to accept my rating. :)

Wow, I always thought that to get the red color you should prove the algorithms before writing and do a lot of things that I don't do, maybe I have a chance of get the color.

Well, it's better to use sparse table and unordered_map in your code, but you would receive wrong answer because what calculate the length of a C string is strlen, since you are using sizeof, it's the same as to add the same thing for all values of strings. And you have to treat the case when l > r.

https://ideone.com/U1GmWp
It's basically what bazsi700 explained, I counted the value of palindromes for every string, mapped the strings with a trie and used a sparse table to do the queries

Yes, it runs fine, in case my solution passed in 1746 ms.

Basically, you have to see that some number may be 'lost', what I mean is that when we are compressing we are not considering the elements l[e] < X < r[e], for every e, so we can create a case were there is more that an range loses one of it's elements and after this our algorithm gives the wrong answer, but actually we don't have to take exactly all the X, if this situation gonna happen is because of there is two ranges with some intersection, so the values that matters are the borders of the ranges, it's not a good answer, but if it's not clear I can try to explain in a better way

My solution is:
suppose the elements l[e], r[e] <= 10⁵
If you add 1 to every element in the range [l[e], r[e]] for every e , you can check if a range is good checking if the minimum element in the range is 1.
Because if the minimum is 1 after deleting that range we gonna have at least a 0, what means that the number of moments increased.

If you are compressing the values, you should add (r[e] + 1) to the values to compress, at least I did this and passed

Was just me or someone else didn't know what is 'expected score' ?

I also thought it should have passed, was nothing big, just optimizations. When I have time, I will recalculate everything, the constant factor shiuld be small.

Think in the following way:
First, lets calculate the sum of every prefix in the string.
Now, we can reduce the problem to finding the number of different values in the form Sum[i] — Sum[j], where sum[i] is the prefix sum of position i.
It's very close to standard FFT problem, but it's a subtraction, to solve this we can just add an constant making all values bigger than zero, in the case 26 * (max size of the string)
Now, just do FFT, and count how much indexes have value different from zero. You have to see, that with this method the empty string will be counted one time and any other will be counted twice.
The complexity will be O(C * log(C)) where C is the maximum value
My team didn't solved by a little bug and strict TL.

How to solve D?

I solved with DP, but there was people that solved in 11 minutes, maybe there is an easier solution. My idea, lets consider every prefix of all strings and build an graph, where exists an edge between the prefix and the prefix without the first letter. It will be a forest. No two adjacent vertex can be at the set and just the vertexes that are prefix can be choose. Since you have to find maximun, you can apply dp.

:( . I hope you have another chance to hack me.

Waiting Petr screencast to see myself being hacked. :)

1
3 6

should be 4

Google translate, I have a very poor english

Same thing, do you know if they can make the contest unrated for who was injured due to issue? I made a comment asking to admin during the contest, but I had no response until now.

too

You can use persistent segment tree to this. I couldn't see the idea of the xor, instead I used persistent segment tree to hash(multiplying) and binary search, in a brief description, inserting the elements in the tree from the smaller to large in value, will make possible have the hash of a ordered segment of the queries, you can find the first element that mismatch in the binary search, if exists, after you can use another binary search for find the second, to see if they are the same, is just multiply the element that mismatch in the first with the hash of the interval of the second and the element that mismatch in the second with the hash of the interval of the first. https://www.codechef.com/viewsolution/14056539

My solution is O(n² * 2ⁿ) how do you take off one of the n's of the complexity? Also how to put complexity right in the comments? Thanks in advance

Contest is over, so let's discuss the problems, what is the solution for EvenOdd and Global Warning? I solved Global Warning, with dynamic programming, but it's certainly not the intended solution I had to made a lot of optimizations and it passed with 1.93s.

2
3200 800

Your program fails in this case

In similar triangles, we have that the ratio of base/height has to be the same, so you can find the base for a height doing, heightX/heightB, where heightX is the height that you wanna know the base, and heightB is the full base height(the value of the height of the complete triangle).

This is a fake account, real account is ordan , he don't want to get downvotes.

In the first operation p = 1 p = p + a[p] + k p = 1 + 3 + 1 p = 5 In the second operation p = 5 p = 5 + 7 + 1 p = 13 p > 10

How to solve A?

Same problem here

I am in.