Sorry this is for the sake of making the statements shorter to read :)

what is the benefit of scoring distribution before the contest ?!

There is 25 minutes after cf round according to clist.by.

Last time I checked there is a 25 minutes break between them (which is the reason this time was chosen in the first place)

We just worked with a huge pool of problems, part of which are gone to Round 369, another part come to this round.

Good luck You too :)

I wonder if you've ever heard of Photoshop. :P

It wasn't the previous one, it was the one before. Round #371 was correctly held, so it should be the same on Saturday.

This contest ends 25 minutes before the SRM.

I am a Malaysian FYI. :)

Some of the later test cases actually came from successful hacks of the competition, so not all of them are done by me.

I'm glad you enjoyed the last round. I'm sure you'll find this round more interesting :)

Round 371 was rated and was held without any problem.

I do agree! last contest's A & B were less logic oriented, but more coding oriented, but problem D was really nice!

Not sure why you've been downvoted. I'll risk my reputation too.

Good luck!

Well I think most people will like the problem to be straight to the point and simple to read and understand. (i.e. short statements)

Chris is the guy who says he likes Chris the Baboon above. :)

Yeah! More thinking problems needed :D

My last round was round 369, and 369 is a multiple of 3.

This round is round 372, another multiple of 3.

Yes you can

Why? Will that mean a slow website today?

They usually do it because the servers are overloaded

Have already started :P

Your comment is one of them?

Ya i have another topcoder srm later :D

So you're saying "Girls > Contests"? smh

Be carefull about sub string.

i didn't just forget the "?"s but i kept outputing only the 26 letters substring , even when i fixed that i forgot replacing the "?"s . it was pretty clear in the problem statement but i didnt fully read it :( " This string should match the string from the input, except for the question marks replaced with uppercase English letters "

Fuck. They have put wrong words in bold.

'all the question marks with uppercase letters' should be ' all the question marks with uppercase letters'.

Or even better:
' ALL the question marks with uppercase letters'

The problem states: This string should match the string from the input, except for the question marks replaced with uppercase English letters. There is no reason to believe it is enough to replace a minimal amount of question marks.

Don't post code during contest

Seriously, Contest blog should be blocked during contest.

you can't post code in here right now and i can't help you , but what i can say is that i had the same problem and it can be fixed.

Jump for i-th level is to number i * i * (i - 1) * (i - 1)

I have passed pretests with this: for i in range [2, n] just outputed (i+1)^2*i-(i-1). I don't know if it is right or not.

It scares me when I spend 2 hours coding something and then a much stronger coder asks how to solve it :S

Now I'm confused if I'm right. Well, at least I won't lose ratings.

How I've tried:

Set all unknown edges to 1.

Find shortest path s->t (assume it's equal to L2)

Then if L2 > L then there is no answer. Else if L2 = L, output graph else Count all edges on shortest path (assume cnt). If cnt = 0 then no soluton.
one of edges set to L — L2 + 1. All other edges (outside shortest path) set to INF.

But I didn't send my solution.

I had an idea and although I couldn't finish it in time, I will explain it because I believe it's correct. The minimum weight we can use for each edge is 1, so let's use it for every single edge with erased weight. Find the shortest path, say L'. If L'>L, then no solution. if L'==L, then we have found a solution. Assume L'<L and D=L-L' and again put 1 on every edge that doesn't have weight. Let's loop over the edges that have no weight and make the current weight from 1 to 1+D. After doing it for the current edge, let's find the shortest path and if it is L, we are done. Otherwise, it will be less than L and we can continue the process with the other edges. To do that fast, we can just binary search for the last edge that got its length increased before the shortest path became L :)

Is my solution right? I hope it will pass the pretest.

1, Run Dijkstra to find a shortest path (1).

2, Assign the weights of "erased" edges on shortest path (1).

3, For other "erased" edges, assign weight 10^15 (so (1) has more chances to be a shortest path of length L)

4, Dijkstra again to check.

5, Print the result.

I didn't participate in the contest, but keeping an upper and lower bound of a node and run a Dijkstra should be a good idea.

When visit a node: if a nearby edge is weighted do the same thing as Dijkstra and set the underground to the distance, and if there is no question marked edge then also set the lower bound to it. If there is a question mark edge, set the lower bound to dist+1 and upper bound to INF-1.

Of course the Dijkstra will be ran under the upperbound.

*I am a bit drunk right now, so I may miss out something important, and yes I typed "hit" instead of "bit" before I revised this...

I thought to find all the simple paths between S and T. If on any one path number of zero weights >= (L-remaining weight on this path) then answer exist else answer doesnot exist.

Now on this path we replace all zero weights by one except the last zero weight. On the last zero weight edge we put weight = L - X where X= number of zero weights on this path-1

Now we can put INF on rest of zero weight edges so the given condition gets satisfied. I could not implement within the contest time. :( Can someone comment on the correctness of this solution ?

You like B too!!! Seriously, now I'm convinced I wrote crap for 2 hours ;_;

Count l from 1 to n and for each l output l == 1 ? 2 : l * l * l + 2 * l * l + 1. That's all you need to do.

just for all i = 1..n output i * (i + 1) * (i + 1) — i + 1

number at level k can be of form t*k as it has to be multiple of k assume we add x times k to number then

(t*k)+k*x= ((k+1)*r)^2 // rhs is to satisfy next level

r=k is a solution of this equation x=(k+1*k+1 * k )-t it will be in range always as max it can go cube of 10^5

Consider a constructive method:

When you are in L(evel)4, you have number k.

If you want to advance to L5, you have to make your number a perfect square and can divide by 5, also you have to make this target number 4-divisible because you add 4 for every press, then 5*5*4*4 may be a good choice.

Let's try this simple idea from L1 to L5.you have:

L1 2 --> 4 = 1*1*2*2

L2 2 = 1*2 --> 36 = 2*2*3*3

L3 6 = 2*3 --> 144 = 3*3*4*4

L4 12 = 3*4 --> 400 = 4*4*5*5

L5 20 = 4*5 --> ...

This idea works really fine and performs beautiful.And now you can summarise the final expression Li = i == 1 ? 2 : (i)*(i+1)*(i+1) — (i-1) and now you are done.

Thanks everyone :)

Do you print the whole string? Do you print any question marks?

Why did you dislike this round?

Because replace all the question marks with uppercase letters

could you explain your solution please

I agree. Div 2C was a beautiful problem.

My solution failed on pretest 6 because I didn't change all question marks to letters, or I wasn't printing the whole string, just a 26-letter substring.

That' s for sure. This can effect the result a little bit.

I tried such approach... But got WA on pretest 4... Maybe i made a mistake...

Yes, otherwise L might be less than the number of erased edges on the chosen path, and you'll be printing NO.

Same here dude! :( ! I still have no clue why my submissions are wrong despite implementing the same methods

The great evil plan of choosing all M as prime in all pretests. >=]

After assigning you should check if the path you got at the beginning is still the shortest one after you removed all the zeroes.