I meant it comes from the sketch of the optimal solution, I dont see the problem, is part of being a competitor to check the implicit constraints too and I think it's brilliant how they did it here, it made me doubt a lot

Well, x — y means one of your n's will be equal to x-y. That means the original restriction on the sum of n's indirectly restricts the value of x and y

right, thanks for the tip

I meant from the second equation you wrote, direct

Why cannot we just solve the equation for $$$F(x+1)$$$ and then replace $$$x+1$$$ by $$$y$$$?

I would suggest doing it iterative instead of recursive. Moreover, you have an extra dimension that you can skip (see the explanation of Saul)

you're right, your problem is the break, you should have pushed more the n to the last position you could so that the solution is lexicographically the smallest

You have to set $$$p[n] = 1$$$ at the end after $$$p[x]=n$$$, otherwise you are overwriting it when $$$x == n$$$

I see, I think what I didn't get is that $$$K_i$$$ is cumulative

Thanks

Why do we get $$$min(cnt_j, i)$$$ in the formula for $$$K_i$$$ ? I get the part of $$$cnt_j$$$, but not the reason for the i. Is like we're telling we are repeating an element in one of the set we built right? but this should then be invalid

I didn't solve the problem at contest time, but I think that the first thing to do here is to split the problem in two cases:

if r — l + 1 >= 2 * (a + b)

in this case the person A is going to put a different letters for sure, since there is at least a segment of a letters in which person A is going to put his different letters. Since person B should play optimally then he's going to put the same letter and it should be one of the letters from the first A segment. but since there are 2 segments for A, then A cannot put the same letters as in the first segment since B already put one letter and A look for a suffix of at least 1.

So, in this case the solution is a + 1

else

simulation, starting from l to r starting with the letters from A or B depending on l % (a+b)

I think what is wrong with your solution is the following: you have to check in the for at line 55 if you have already used the products for that index, because sometimes 2 * products_i could be less than products_j for some i,j, let me know if you need a more detailed explanation

yeah :D there should be more contest like this one

Hi, can someone explain div 1 500 approach? thnx

may you explain your O(N * log N) approach?, thanks.

Hi, may you elaborate it a little bit?, please

and then you realize that the dress was indeed white and gold

i'm trying to change my gcj username but it says that i can't change the password more than two times for year and the last time i changed it was last year, any ideas?

Again topcoder :/ , i really like it problems but they must change a lot of things to improve TC

yes, this approach is O(n^2) because you will try every combination of the wrong edges but you will have at most 3 wrong edges (if you have more then this configuration of the tree will never be a tree). In the worst case these 3 wrong edges will be between the middle nodes which means that you will try at most 4*4*4 combinations (if there are 3 nodes with more than 3 edges), or 4*5 combinations (a node with 4 edges and a node with 5 edges) or 6 combinations.

So, i think in the worst case it will run in 4*4*4*(N^2)

what about other kind of problems? do you recommend Timus for other kinds of problems as well?

can you provide the explanation for 2nd problem?, please

Problem B can be solved with a c++ set

let's say that we must type the word W,

first we insert it in the set (our dictionary) as the statement says, and then we can use set's lower_bound method, and upper_bound method to find the words that more look like W, and compare these with W and compute how many characters indeed we need to type to make W.

Of course this solution is O(N log(N)) but has space O(N). With Trie sometimes the memory could be a tricky thing i guess.

oh sorry, now i get it, is the minimum so you need the minimum in each child, thanks

but what if there are more than a child that give you present with price x-1, does it change the recursive formula? i mean:

a[1] = 1 a[x] = 1 + m * a[x-1] + a[x-2] + ... + a[2] + a[1]

where m are the number of people that give you presents with price m

thanks, well explained :D

i have failed because of this and i think i must wait for another year :/

may you explain the analysis for this problem?

Here in Venezuela Contest will take place at 4:30 a.m T_T i hope my alarm can wake me T_T

thanks :D

just one question, is there any disadvantage when you become coach? can't you participate in competitions or anything like that?

i gained +351 xD

thanks :D

I never understand div 1 B problem statement, could someone explain it?

i think problem A can be done with mincost-maxflow but i don't know if it will give TLE, am i right ?

i had the same problem but i fixed it, you must think what happens when you have a case like this:

Left = 6 ; Right = 7

6 is written in binary like 110 7 is written in binray like 111

following with your approach you will go to the last bit and set it as 0 then all the remaining bits as 1, but in this case you will return 6 and the correct answer is 7. So, you must care the case when it is the last bit, if they only differ in the last bit you must return Right

try to formulate a top-down DP solution that takes O((r+g)*h), this will give you MLE, then try to formulate the same DP bottom-up, this will require only O(r) in space and runtime of O((r+g)*h), if you see my code you will see both approaches

but the problem said the graph is undirected, so the cycles are edges between two points or not?

la verdad, es que esa era la que tenia pensada, solo que dudaba implementarla y por eso pregunte

no, lo implementare mas tarde, por que?

thanks man

thanks, i really appreciate it

how do you solve Ecology problem?

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=823&page=show_problem&problem=4660

there will be only one division?, i think only one is better

may someone provide a better explanation for the C-div1 first solution ?

How to solve Grandpa Pepe's Pizza problem? any ideas?

here in Venezuela, the support to this kind of competition is almost nothing, indeed in my town there is not this kind of competition, when i moved to Caracas (the capital) and i began the university was the first time i heard about this kind of competitions (math or programming).

thanks :)

how do you register in that contest?, or it does not need registration?

thanks :)

can someone provide a better explanation to 464C — Substitutes in Number ?

thanks :)

yes, they talked about optimization, but if you look the last comment:

" But my personal feeling is that most Topcoder Marathon matches are of a different kind — e.g. machine learning (classifying something properly) or image processing "

I'd like if you can provide a list of these "machine learning" or "image processing" techniques or algorithms, and others subjects.

Thanks in advance.

thanks :D

may i do the same thing?, i have the same problem

[email protected]

do you have any other resources?

please, can you tell where are the Psyho's lectures?.

i'd like to practice with you

someone can provide an explanation of div 1 500?, thanks.

thanks

yes, but then we need a proof to say that this is maximum, because ysymyth told that all numbers are matched (i refer to all numbers but 1 and primes larger than N/2)

yeah, but how do you ensure that all the remaining numbers of the form 2P can be matched?, i mean why this quantity (the remaining numbers) is always an even number (for match all these), i mean it might be that one number get unmatched from all these

may someone make a detailed explanation of the solution for problem Div1 D?

hi may you do another group for people that does not have a rating as high as 2000, and maybe train us or do something similar to the things Krk did with you?

thanks.

Hi may someone explain 438D - The Child and Sequence better?, thanks.

great explanation, thanks.

Can someone provide the demonstration for problem C Div 1

hi, someone can explain solution for problem E div2/C div1?

thanks

i have the same problem and The author had a mistake: "Problem B. Inna and New Matrix of Candies ***** In problem B was mistake in the statement you must choose all line with dwarf that is not in candy location, not several. Now the statement is correct. Sorry for that."

May someone tell me why this submission get WA, i don't know why it is printing -1 on test 8

http://codeforces.me/contest/400/submission/5944310

yes, i have the same mistake, the thingis that s.size() is an unsigned int... and when it is 1 and substract 3, it is 4294967294, because all the expresion is indeed unsigned int, and then when you access to the element 4294967294 of the string it give you RE, because it only has 1 element.

hi, the links are down, where may i find the materials and video?

thnx

thanks :D

may someone explain solution for D?, thx

hi, look here http://codeforces.me/blog/entry/10423 for the explanation of clp012345 is a good one.

thanks :D

thanks for the explenation, i think it is very clear.

this is a cool reduction of the problem... thanks guys :D

what a good contest! :D really cool, good problems

Good alanysis for problem D

I think that a solution in O(N^4) should pass because 10^8 can pass in two seconds, indeed my solution is O(N^4)

A very interesting contest :)

Yeah, this was my worst contest ever, A problem was very strange