Hello, Codeforces!

30th September 2016 at 17:05 MSK Codeforces Round #374 (Div. 2) will take place for second division participants. Traditionally, participants from the first division will be able to join out of competition. **Please, notice that the start time is unusual.**

This is my second Codeforces round, I tried to make problems interesting for everyone, so **I recommend to read all problems statements!** I hope that everyone will find something new and interesting. I wish lots of accepted runs and higher rating to all participants.

I want to thank Michael MikeMirzayanov Mirzayanov for wonderful platforms Polygon and Codeforces, and for help in preparing the problems, my best friends Danil dans Sagunov also for help in preparing the round and Ivan BledDest Androsov for testing the problems.

Participants will be given five tasks and two hours for solve them. Scoring system will be announced traditionally closer to round start. :)

The scoring is almost the standard: 500-1000-1500-2000-2750

**UPD**: Editorial

30 September

Oh, sorry, my mistake. Fixed.

Why unusual time? :/ The previous timings were way better.

Unfortunately, this round will be conflict with Jordan-cpc :/

Hi. Sorry for my bad English.

I am loving the that timing is being rotated around! It unfortunately makes a lot of people unhappy but I think it is still a great opportunity for people in different time zones, so nobody misses out.

"Unusual" is the new usual.

You won the Internet. :D

wish to see a programming contest not a hacking contest :D

I think hacking contest is interesting~

I know that you believe that you understand what you think he said, but I am not sure you realize that what you read is not what he meant.

sorry,I didn't read carefully.

but there is no hack in the programming competitions like ICPC or IOI

I think some pretests are little bit weak :<

the pretest of the last 4 or 5 contests were too weak

pretests must be weak, then someone can hack!

but I think it should be strong enough to not see somebody hacks about 15 people on one problem!

the pretest of problem A and B should be stronger~

there is someone hacked 16 people on problem A last contest

he took points like the points on problem E :\

if you hack a person once, you would not say this again =)

bad round PS : one of my friend has comment it when we has class, sorry author :((

one's day may be night for others. so we should appreciate this "unusual" time.

my best friens Danil dans Sagunov also for help in preparing the roundwhat does "friens" mean??

UPD:fixed.thanks, fixed

good luck

why unusual man ? I hate to miss contests

salam

are problems sorted in order of their difficulty?

Usually they do, but it is still recommended to read all the problems, just in case.

Why Kotlin is not allowed in this round? It seems to be the only language missing compared to rounds 371-373. Edit: In the end system accepted Kotlin submissions too.

Looking forward to the contest =D

Round 374.

374 = 2 × 11 × 17 , Sphenic Number

Nice Observation.

I hope the platform will be stable today. Currently there are 7+ pages of pending submissions....

Seems better now :)

The judge queue of practice problems is very very very long now. I hope this issue will be resolved soon and have no impact on this round.

In my opinion, the active contest should have significantly higher priority on the queue than practice.

In my opinion, there should be more servers for running the submissions. And to make things better, the machines should be Linux so that it can produce more exact execution time, instead of "15ms" on Windows.

Hit like if you think your rate will be increased today :v

then Hit Like if you think your rate will be decreased today :v

An old trick for getting upvote , stop it or you will get downvotes again!

I hope that I have become better.

Score distribution ?

Auto comment: topic has been updated by dans (previous revision, new revision, compare).After reinstalling windows, I am unable hack in firefox.

Clicki think you need to update your adobe flash player

i have faced the same problem also

use chrome!

the cool trick in div2 A is that you shouldn't test all samples on your code :v

May I know why ?

Quick question, if I can't get pretests passed for anything I submitted, I'm still eligible for rating drop, right?

Yes, You're eligible for rating drop if you have submitted at least once

Okay ;_;

Sorry :(

not only drop bro :) extreme drop :P

Okay ;_;

I can either keep attempting A and B under time constraints, or I can try to level up. My ratings will get dropped extremely(-130 this time) but it is one of those things you gotta do if you want to improve yourself(I hope) :)

So codeforces allows submit the same code now?

how same code get 15 ms as well as 31 ms??

That apparently counted as resubmitting twice... Isn't that a bit of a problem?

I think you will get 50 point penalty for resubmitting.

He's div1 so it's unrated for him

Having fun then

if you click on submit button several times, your solution submit several time (your picture show us you did it). but if you submit a code and after your code passed the queue, you try again to submit the same code, your solution can't submit.

sry 4 my bad englishDiv2B hack?

There could be multiple occurrences of the same string in list of passwords, that are same as actual password. Some people did not handle that. My own solution does not handle it.

they are pairwise distinct though, no?

Maybe not. Problem statement did not look clear. The last line says "It is guaranteed that the Vanya's Codehorses password is equal to

someof his n passwords."I was very confused by this too

The next n lines contains passwords, one per line — pairwise

distinctnon-empty strings consisting of latin letters and digits."pairwise distinct non-empty strings consisting of latin letters and digits."

The statement has said "pairwise

distinctnon-empty strings"Its written passwords are distinct

Why did you resubmit Div2 C? I saw that most of the people used ~100 MB memory which means a 2d dp state. How did you solve it?

I had done wrongly thought Dijkstra on {cities not visited, time} could work. It took me a lot of time to realise I was wrong.

What is the problem with that solution?, I could not get the mistake. I did a dijkstra from n to 1, and then a dp from 1, trying to search what is the higher depth of the graph.

But it is mentioned that the strings will be pairwise distinct & non-empty.

Nice contest.. Anyone can tell me how to solve problem D??

First, if the amount of negative numbers is even, we want to make it odd. So we pick the number with smallest absolute value and apply operation until it's signal is swapped (sometimes we don't have enough operations but it doesn't matter, just keep trying until the signal is swapped or until you don't have more operations).

Then, we simulate the process. While we can apply operation at least one more time, we apply it to the number with smallest absolute value at each step, raising its absolute value. We can use a priority queue to simulate this. Turn all numbers into positive numbers and store the signal separatedly, so it's easier to work with the priority queue.

Then, after we used all available operations, we push the results to an array and print the answer.

This solution is correct because it is possible to prove that for any set S with only positive numbers, if we can increase any number by K, the total product is maximized if we always pick the smallest one.

Code: http://codeforces.com/contest/721/submission/21037453

Can you prove that why choose smallest abs value and apply opration on it in first step is true ??

Because if we pick the smallest abs number, we will waste a minimum number of operations to swap its signal. These operations will only reduce the abs value of our product or increase it by a smaller value than if we used the operation to increase other value, so we dont want to do a lot of these operations because we want to maximize the abs product (and have an odd amount of negative numbers so the signal of the product is negative and then the total product is the minimum)

Consider that you have two elements

a_{ i}anda_{ j}, |a_{ i}| < |a_{ j}|. Letmbe the smallest number of operations required to change the sign ofa_{ j}. If you apply them toa_{ j}, you will get two numbers,a_{ i}and newa_{ j}, and now |a_{ j}| (the new one) =m·x- |a_{ j}|. If you apply all thosemoperations toa_{ i}instead (there might be some better ways, but let's consider this), there will be newa_{ i}: |a_{ i}| (the new one) =m·x- |a_{ i}|, anda_{ j}will remain unchanged. |a_{ j}| > |a_{ i}|,m·x- |a_{ i}| >m·x- |a_{ j}|, and you need to maximize the absolute value of product, so you get a worse situation if you change an element with non-minimum absolute value.But let's say we have the numbers -2 and 1, an x=4 and t=2 Then by your algorith we wouldn't do anything and leave the product as -2. But we could actually add 4 to the first one and subtract 4 from the second one and get the product 2*(-3)=-6, which is smaller What is wrong in my logic?

How to solve C guys?

d[j][i] = minimal cost to visit j verticles with and last vertex i.

P.S. I had to keep only previous state to fit it in the memory limit.

I used dp and dfs to get the maximum number of visited showplaces before visiting showplace

iunder time T. Then reconstruct the route using backtrack or without backtracking.Is there a special algorithm to do C? I kept getting time limit with a breadth and depth first search.

I was on the same boat for a while. The trick (for me, at least) was topological sorting.

So that's what it was. I've only done a few topological sorting problems so I guess that's why I didn't notice it.

pathLengthis the number of vertices on some path from vertex 1 to the current vertexv. Among all the possible paths from 1 tovwhich havepathLengthvertices between them, there exists the shortest path. We track the cost of that path hereminCost[v][pathLength+ 1].Can you clarify your answer regarding nodes which have multiple parents? If we just loop through all parents of a node and all pathlengths, we get O(n^2 * m). This would be similar to my solution, which barely passed the time limit after contest. Other people have solved it way faster and I'm trying to figure out how...

Sure.

Let's consider, for example, a DAG with 6 vertices:

v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}.The goal is to arrange all vertices in layers or floors. Let's stick to floors.

Imagine there is a 6-storey building:

`[ floor 6 ]`

`[ floor 5 ]`

`[ floor 4 ]`

`[ floor 3 ]`

`[ floor 2 ]`

`[ floor 1 ]`

Floors

somehow(we don't know yet how) correspond to vertices in a graph. We only know the identity of 2 vertices:v_{1}is`[ floor 1 ]`

andv_{6}is`[ floor 6 ]`

, because we always gain access to all of the verices in a graph from vertexv_{1}(we always gain access to the floors of a building through the first floor) and we end our travel in a graph in vertexv_{6}(we cannot move further up from the floor 6).Now, we base our decisions about correspondance of vertices

v_{2},v_{3},v_{4},v_{5}and floors on the fact that ifv_{2}is some`[ floor i]`

then all of the outgoing edges fromv_{2}should point to higher floors. That is, once we are on the`[ floor 4 ]`

, the floors`[ floor 1 ]`

,`[ floor 2 ]`

,`[ floor 3 ]`

become blocked for us — we cannot move to these floors from the current`[ floor 4 ]`

by using outgoing edges of current vertex.At first we have some

unordered setof vertices {1, 2, 3, 4, 5, 6}. Then we use topological sort to create anordered setof vertices with the specified property (we cannot move down from higher floors). Formally, topological sort is a map:{1, 2, 3, 4, 5, 6} (1, 4, 2, 3, 5, 6).

Below is a graphical representation of that mapping (

topological sort).The distinctive property of the picture from the right is that

allof the edges are looking to theright. None of the edges look to the left (backwards).Not a single child is pointing to a parent. That means, when you reach vertexv[i] as you go from left to right, there isno wayyou can update thestateofv[i] later as you continue moving to the right.Actually, the graph on the right is an abstract representation of the concept of dynamic programming. We consider sequence of vertices 1 → 4 → 2 → 3 → 5 → 6 in the specified order. When we are standing on the vertex

v[i] it has optimal property (in our case time to travel to that vertex). We update from that vertexv[i] all of it's children. The next vertex in a sequence afterv[i] now also has optimal property, because it was updated by parents which had optimal property themselves.All of that brings us to a conclusion that after we do topological sort we can just look into each of 10 edges (only

once) in the following order:We have 2 ways of reaching node 2 in your example:

Why is it sufficient to process node 2 only once? We can't know yet whether route A or route B will be part of the final answer, so don't we have to accommodate both possibilities? Like this:

Good question. Do not stop asking until you fully and completely understand.

The node 2 is updated

twice.The first time it was updated on the step 2: 1 → 2.

During that step we updated our estimate of time to travel to that node from ∞ to 3. It is important to understand that the time 3 is the best time to travel from node 1. We cannot get better than that.

The second time we try to update it again on the step 3: 4 → 2. This time we will not update our estimate with number 5 + 2 = 7, because the previous update was better. But again, the time 7 is the best time to travel from node 4. We can only improve that number if we reduce the time to travel to node 4. But we cannot reduce that time, because there are no backward edges pointing to node 4 and we have already explored all of the edged coming inside node 4 and updated it's state.

The general pattern here is following. We only use edge

u→vif we are 100% sure about the optimality of vertexu. That is, we have to consider all of the edges comingintoubefore we start looking at the edges comingoutof the nodeu.Thanks for your help. Your illustration of topological sorting is very nice. However, I don't think your solution works.

"The second time we try to update it again on the step 3: 4 → 2. This time we will not update our estimate with number 5 + 2 = 7, because the previous update was better."If I understood you correctly, you mean we would forget about the 7 cost path because the path with cost 4 is cheaper? It's not correct. For example, if T=1000, then the optimal path will visit all 6 nodes (including the 7 cost path 1->4->2).I was asnwering your question regarding the complexity

O(n^{2}×m).That is, I showed how we can find the shortest path in a Directed Acyclic Graph with complexity

O(n+m) (which is better thanO(n×m)). We managed to reduce the complexity by doing topological sort.We can use the same strategy in the original problem to reduce the complexity from

O(n^{2}×m) toO(n^{2}+m).There is one more idea remaining on top of what I have already described.

Let's concentrate on some vertex

v[i]. There is a set of different paths from vertexv[1] leading tov[i].Now, as it is drawn in the picture, we

splitthe set of all possiblePathsfrom vertexv[1] to vertexv[i] into groups (disjoint subsets).Within each of those groups we will be performing comparison of travel times of those paths and look for a path with a minimum travel time. I've circled the minimum cost path in a group with red.

In the worst case there are 5000 different path lengths (not paths!) from

v[1] tov[i], because the maximum number of vertices in a graph is 5000 and we cannot make a path with repeating vertices.So, for each vertex we will be storing an array of minimum cost paths to that vertex:

The number

minCost[i][5] stores the minimum time to travel fromv[1] to vertexv[i]. But it is notNOTamong all the possible paths, it is only among the paths in thegroup5 (paths of length 5).Nicely illustrated again, but I feel like you are describing my slow solution:

Ok, you've sowed a seed of doubt =)

I wanted to solve this problem after a week or two (when I forget the problem and the solution), but here we go...

The solution that I described: 21115101

Feel free to ask any questions about the code.

I can see your solution passed in 93ms, but I can't figure out how. You even have those 3 nested loops:

The outer-most loop is 5000 worst case. The middle loop is 5000 worst case. The inner loop is 5000 worst case. How does this not lead to 5000^3?

gives us the complexity

O(n).increases our complexity to

O(n^{2}).does

notmultiply the complexityO(n^{2}) to makeO(n^{2}×m). This loop adds to the outer loop (which givesO(n+m)) and multiplies inner-most loop (which givesO(n×m)).If we combine them, we get the complexity

O((n+m) ×n) =O(n^{2}+n×m).Edit:No, I am wrong. The following lines (both of them together)

give us complexity

O(m) — we touch each edge only once.When we add inner-most loop we get total complexity of order

O(n×m).Thanks! Now that you put it like that, it's obvious the complexity is O(n x m). Problem now is I have the same 3 nested loops in my solution, and with a ton of optimizations that code is still running for 3000ms. You probably don't want to scour through this, but I'll link it for reference in any case:

http://codeforces.com/contest/721/submission/21047724

Insert the counter in your code and calculate how many loops the code does.

The worst time is achieved on case #59. It starts with these 3 numbers:

3615 4935 245435090

So, you need to print the amount of loops when you encounter that case:

Your code will fail and you will see in the result how many times the inner-most loop was executed.

Here is my result: 21118607

Your code made 17M iterations, mine did 3M. And yours is 30x faster somehow.

http://codeforces.com/contest/721/submission/21168815

That means the problem is not in the algorithm.

The problem is either in the data structures (probably, collisions in HashMap) or in the input. I doubt that input is bottleneck, because in its maximum it is just about 1500 numbers.

Weird thing is I'm only putting longs and integers into the maps and there is a Java solution to this problem which also uses HashMaps and runs in 200ms.

Look at the cases #8, #9, #10. They both have the maximum possible input and your solution works in

150 ms!But something interesting happens in the case #12. It is not the hugest input. Just 1686 vertices and 4331 edges, but it makes your solution go over 1 second.

On the case #10 the program does only 29611 operations and it takes 140

msto perform them.The case #12 takes 2237322 operations and the times blows up to 1076

ms.Look at this: 21172009

17835090 operations and only 265

ms!The only difference I see is that there are no HashMaps and no TreeMaps.

Thanks for your help. There are HashMap-based solutions which perform in 200ms, so it's still unclear to me what exactly makes my solution slow, but I feel like it may not be worth pursuing further.

Pixar,

I have done step 2 of your solution using recursion. Can you please explain why step 1 (topological sort) is necessary?

Basically, I define a recursive DFS (vertex1, N, time) which stores number of vertices covered and time taken; and call DFS(1,n,T).

My code — CODE gives TLE on test case 11, although I guess DFS algorithm in itself is not exponential time?

Any idea why this might be happening?

Thanks in advance.

We need to know the order in which to process the sequence of vertices. Searching for the right order is called sorting.

Now, what is

rightorder? For us the right order is the situation when we finish processing children of vertexv[i], the next vertex in our orderv[i+ 1] has the cost (time to travel) whichcannotbe improved.What does it mean to improve the cost of the vertex? That means we have found some parent vertex from which we can reach the current vertex by using a smaller cost.

Well, the whole algorithm is a continuous reevaluation of our estimates of the times to travel to each vertex. After each evaluation we reduce our estimates. At first we say that each vertex in a graph has very big cost. On each pass of our algorithm we do these reevaluations of the costs. We reduce and reduce until our estimate becomes the real minimum cost.

How many times should reevaluation of the estimate cost happen?

Let's take some vertex

v_{ k}. For example, it has 3 parent vertices:v_{1},v_{2},v_{3}. Then we will do the reevaluation of the cost only3times!On some step of our algorithm we become sure that we cannot improve the estimate of the cost to travel to

v_{1}. At that moment, we update estimate of child vertexv_{ k}.On some other step of the algorithm we become sure in the estimate of

v_{2}. Then we do the second update of the state of the vertexv_{ k}.And situation repeats for the vertex

v_{3}.If we have processed all of the parents

v_{1},v_{2},v_{3}of the vertexv_{ k}, there is no way we could ever improve the estimate of the vertexv_{ k}! Why? Because there are no more vertices left which lead tov_{ k}and we can only improve the estimate of the cost ofv_{ k}from vertices leading tov_{ k}. What does this mean forv_{ k}? It means thatv_{ k}itself became optimal and we can update the estimates of the children ofv_{ k}.O(n+m).I was wrong regarding the impossibility to solve it with DFS. Here is the solution with DFS.

Thankyou so much! Very nicely explained :)

I just hope 2d dimensional dp for both path parent and cost in Div2C doesn't give memory limit exceed on Div2C. It was pretty close on sample tests :|

I did 2d dp where a[i][j] is the minimum time to get to i after visiting j nodes in O(n*m). If I understand what you did it is O(n*t). That will get TLE on some possible cases.

No i meant n**2 only. However on my first submit it had taken like 260mb of memory so i reduced one of them to unsigned short to just make it through mle. http://codeforces.com/contest/721/submission/21031777

Did someone experience problem with lack of memory in Div2C?

This is the first time it happened to me.

Yeah. The cost dp could be reduced to 2*N array though and that will decrease the memory by half.

However i just tried to reduce the path storing one to unsigned short o.O But not sure whether it will pass in main tests.

Me too. But it wasn't necessary to store that much memory. Use map instead of arrays as there are only 5000 edges.

@rachitjain I used map instead of array to store my dp states but it still gave mem limit exceeded on test case 11. Then I have to change my dp state from 2-d to 1-d. I think it will give a TLE in main tests.(fingers crossed)

I did, could have probably optimized memory complexity but I chose to just make stuff shorts instead of long longs and ints.

I solved it using int dp[5000][5000][2] and it didn't give me MLE

I would have had a successful hack if the contest had 5 more seconds :(.I have already written and copied the hacking input when the time was out.

For which problem?

A

I was surprised that so many people solved C

yes I was also surprised. It made me wonder if I was too complicated or not. Anymay I could not finish in time...

Pretests are extremely weak. My bogus solution using Dijkstra with weights as {cities not visited, time taken} got accepted on pretests. It is easy to create anti test.

There was a similar problem a few months ago on topcoder: DoubleWeights.

well it seems only 600 really solved it...

587.

which means I will gain ratings instead of losing :D

Pretests in div2 B are weak because i didnt increment time by 5 sec due to typo error still pretests passed. hope my final solution passes

problem B hacking Test Case please?

what's an unexpected verdict?

It's a verdict that is unexpected.

wow that was unexpected

Judge shocked, Yukimai rocked

And it becomes an unsuccessful now:)

maybe small bugs

I wonder if this solution for Div2E is correct... I finished the debugging minutes after the contest and I have no idea if it would fail on test case 12 again.

http://pastebin.com/AJ7HrMF6

Hhmmm...

seems odd

daneshvar_a accepted C and D at 1:58 and 1:59.

D was already submitted before and the passed solution differs from the past solution (Which got wrong on answer on 6) only in one line which is an 'abs' function. Of course it is easy to change a single line of your code in a minute.

see? you got WA on C, told you that's odd.

I believe you thought that I'm saying that you have cheated, but that wasn't what I meant, actually I meant(amazing-intresting) by "odd", sorry for my bad English.

Now it's really ODD.

all your submissions were skipped :|

could anyone explain why the following code fails (TLE)? 21035958

In the last three contest Div 2C is a DP problem...

Seems like its time to start practicing DP

DP is a great concept and I think it fits nicely into Codeforces rounds

I really liked the problemset. Solved D, but submitted 1-2 seconds after the contest ended. It would've been the first D I solved on a contest. Anyways, I hope everyone did well and more importantly had fun. Now just to wait for system testing :)

Also, what was the idea behind C, DFS got TLE. Seems like it's DP but I can't think of a formula.

dp[i][j] is min time to get to i after visit j node,and it will get MLE if you use long long

a guy in my room use DFS but he had passed the pretests

I thought I solved C with DFS, but then I realized I missed something and it added a lot to my time complexity after I fixed it. Before I started thinking of optimizations, I switched to D, but I'm sure there are optimizations that make DFS possible.

I use BFS to solve this problem by DP. First get TL using long long, then changed it to int and check not to use times bigger than T. Hope it's right solution.

21049347 is my solution using DFS and it's Accepted, after the contest though :(

Let me know if you have any doubts :)

Hey nice implementation, i actually wanted to confirm one thing.. The line where you check

if (path_data[a][visited].second > cost) path_data[a][visited] = mp(cur_parent,cost);

You acted greedy here right ?? As in if at the current node the path length encountered already exists but with a greater cost and we have a lesser cost in hand at current, then update this with the current {parent,cost} pair as this can further lead to a greater path length. Am i right?? If not please clarify..

Thanks :)

Yes, it was a greedy step. Actually due to that step, I'm unable to calculate how much improvement I made in the time complexity. Attempted but couldn't prove it :( I'm still a beginner. Space complexity : O(n^2)

Glad to know that you found my solution helpful :)

PTs for Div.2B are really weak.I was so foolish that I locked it before making hack data.Then i found that i can hack myself...

What was the hack?

Just a simple case. 7 2 a b cd dc abc acd acc acc

and the ans:15 22 good luck..

So as Div2D... I just realized I made a very, very foolish mistake.

Are there any of us that didn't handle negative test cases?;D

I feel so frustrated again because of not solving the C problem. During the contest, I did not have any thought about DP, I used only DFS...

My B solution got hacked, What would be the problem with that code? http://codeforces.com/contest/721/submission/21032401

you should get the sum of cnt[1~len-1],rather than count one by one.

Can you explain a little bit more please?

You divide every cnt with m and divide by 5, so for: 5 4 a b ab cd abc abc

You will get no periods of 5seconds, even though you have to test 4 wrong passwords before the right one.

Instead, you should've done ((cnt[1]+cnt[2])/m)*5+cnt[1]+cnt[2]

ohh.. Thank you..

get the sum of cnt[1~len-1], and the min ans is sum + 1 + (sum / m * 5),it should not get every cnt[i] / m * 5.

Here's a hack case for your code.

6 3 ab ac abc abd abcd abcf abcd

The 5 sec pause that happens after k tries should be calculated globaly, but you are calculating it inside of the loop, and you get inaccurate results when the division isn't exact (in this case the count of sz[2], sz[3] and sz[4] is 2, and k=3, so the division always returns 0, but if you calculate it globally, it would be (6-1)/2 = 1 pause)

Expecting lots of hacks(System testing failure) on 2nd question. No pretest to bound best part of question

passwordshacking test case of B is very interesting, but not many people see it, so we don't see hack war :D(like 373)

PS : I will get WA on B because that. That is so sad

I realised my solution way too late. At 1:34 from the start of contest, I realised I fucked up and then hacked one too.

How would

`O(N^2logN)`

gets TLE in 3 sec, problem C -_-that's about 3*10^8 repetitions, you should never have that many.

it got AC now with a little more optimization but still

`O(N^2logN)`

21043948very strict TL -_-

I think the intended solution is O(nm)

solved C with Dijkstra , it took 623 ms

better check your code

139 ms lol.

62 ms lol

Can you give hint about your approach? I used DFS. Got 78ms and 1200KB memory (memory seems to be too less!)

I see about 1100 people passed pretest on C but about 600 accepted, why ??

I think too very strict in memory constraints .....

Because of DP

Wow, I got WA on TC 66 because of integer overflow.

To get AC, I changed

a>b+ctoa-b>c(wherea,b,care distance and dp values)I saw your solutions , similiar memory used any idea why mine exceeded ?

same

Graph-related problems lead to tricky cases quite often. We've also seen lots of lots of failed attempts (including myself TUT) in a recent problem (715B - Complete The Graph). (Making these test data also requires great care and patience IMO so let's thank the preparers and hackers :P)

I got WA on test 63 for starting the topological process with vertex 1 instead of all vertices with zero incoming edges... Somehow interesting that it can still make its way through such a large part of system tests.

http://codeforces.com/contest/721/submission/21030275 Memory Limit exceeded in 33 test case ... :| I saw some solutions with similiar limits ... unfair !

Actually, It's fair because your bfs() add a lot of unnecessary vertexs.

You should just add a vertex u when all the vertex which can go to u have already been added.

you should use priority_queue instead of queue , your code is about O(n^3)

Do you mean memory or time ?

wrote a generalised soln for div 2 C ( maximum nodes which can be covered starting from 1 ) until after contest when i read the output statement of question ( path has to end at n ) !

please do not use "bad" words in your comments.

my country bans the sites with bad words and then we can only reach these sites by changing our IP address and that's not easy for us.

thank you for your observance.

sorry brother , updated my comment didn't know that your country follows such strict policies .

This code gives me the correct answer in my computer. But it is wrong in their machine.

Can anyone tell me what is the reason behind this??

maxi+=mm[str.size()]; this part . you ought to add mm[str.size()] -1 . Later d incrementation after the 5sec calculation.

You should not use cin and getchar/scanf when

`ios::sync_with_stdio(false)`

is being used.Why it is bad? And when i should use this code?

I received a really strange Runtime Error on problem B and am not able to identify the reason.

What is wrong here? 21044715

I suspect the error is on the first sort after playing with the answers that Codeforces give me.

Comparing function in

std::sortmust be written in such a way that ifa<bis true, thenb<ais false. And in your code, if stringsaandbare both different form the right password, but their sizes are equal, thena<bandb<a. That's why it's RETry changing

truetofalsein the last line of comparing function, I think this will work.Yes, it worked.

So we may have

a<bandb<abeing both false, but we can't havea<bandb<abeing both true. Is this correct?Yes in the first case sort will think that a = b.

I see. Thanks a lot for the help!

Yes. If

a<bandb<aare both false, then it just means thata=bfor this comparing function.I see. Thanks a lot for the help!

Is something is wrong with the ratings? I think all three should be "Became Candidate Master"

This bug takes place when the ratings have just been updated, however, five minutes later, the bug gets automatically resolved. This is just a minor rating to color mapping bug.

Wonder! I noticed the solving time of problem a of rank 1 holder in standing(he is from div1). How is it possible to read problem description and write such long code only within 1 minute !! His code

Perhaps it's because he's familiar with crosswords from his own country (just geuessing XD)

the logic portion is only the 'solve()' function. Everything else was prewritten.

Auto comment: topic has been updated by P1kachu (previous revision, new revision, compare).Why this code gives http://codeforces.com/contest/721/submission/21026545 gives runtime error while http://codeforces.com/contest/721/submission/21044409 gives accepted. The only difference between the two codes is that i am using comparator function for sorting the strings in non-decreasing order of length in 1st code

comparator functionbool comp( const string&a, const string&b)

{ if(a.length()<=b.length())

}

Can someone help what is the problem when i am using the above comparator function and thus causing the runtime error ?

Same as above, there must be no two elements such that

comp(a,b) = =trueandcomp(b,a) = =true.Thank you !! Got it :)

Thank you !! Forgot to take note of these things :)

Thank you !! Then how should I sort it in non-decreasing order of length ?

relax

http://codeforces.com/contest/721/submission/21035009 the following submission of the second question i.e. password ,my solution got accepted in the pretests however during the system check it got a wrong answer on pretest 14 ,here the number of unsuccessful password attempts are 5 and one for correct the answer should've been 6 ,since there is a penalty after 6 wrong submissions.Could any one please explain it. Thank you

In problem C, I took the maximum number as 10^9 and got Runtime error case 66, Now submitted the same code with value 10^9+1. Got Accepted. Why am I so stupid ? -_-

I got Skipped, can you tell me why ?

kudos to the author for the awesome contest, where even 4th question was well in reach! looking forward to more rounds from your side @P1kachu

Hello , Can someone solve some of my doubts!

My solution 21045986 passes even though the first line of my loop( while(K--) ) has a pair < int , int > which can obviously overflow(first element is the element of the array) and I resubmitted it after changing it to pair < long long , int > and got AC. But to my surprise this submission also gets AC(I don't get why ) . Can someone explain?

Moreover is there some compiler flag which I can use to warn me whenever I try to typecast a data type to other which can cause data loss?

Actually, you never use the value of

x.firstin the loop, so your solution works even if the value you assign to it is greater thatinttype can store.Oh Okay I get it , I wish I never saw this :D . BTW can you answer the second question?

66 test cases of a problem and the one your code gets WA on, 66

Life is hardwhy so serious to down vote my comments !?

I feel sorry for you. Lol :)

Can you guys help me with some debugging tips?

Using search engine (Google.com or bing.com for example) provides good results! Here's one : http://programmers.stackexchange.com/questions/10735/how-to-most-effectively-debug-code

I don't want a gazillion suggessions. I want some practices that actually work. eg — the rubber duckie method is a little silly. Writing test cases is not always feasible, you have to generate lots of random inputs and you have to write a generator, a brute force solution checker, which can take time. Btw, I've read some of these tips earlier, I just wanted to know if there's something else out there I don't know about.

Can anyone explain C? I got ACC with a 3000ms solution but I can see many people with <200ms solutions. I process nodes in topological order and maintain dp[i][j] (or map for the same purpose due to memory constraints) where dp[i][j] = minimum cost to reach vertex i through j vertices. What am I missing here?

map increases time,you don't need them. Ordered Maps can cause difference of upto log n. 2D int array will pass whereas 2D long array causes Memory Limit to exceed.

Ok, but it doesn't explain the difference between 200ms and 3000ms. For example, here is another Java Map implementation that passes under 200ms: http://codeforces.com/contest/721/submission/21033441

How did you even manage to pass with this solution? I suppose it is nicely optimized

O(N^{3}), so I doubt you can make it work.The

O(NM) solution uses well-known Bellman-Ford algorithm.On iteration

Kif you can reach vertexN, that means you can visit this vertex usingKedges. Now we are going to read the statements and see this:'there areno cyclic routesbetween showplaces.'That means that on iteration

Kall the edges are different, and more than that, there can not be two equal vertexes on this path. This means that this path consists ofK+ 1 different vertexes.In conclusion, you simply run

Bellman-Fordand if you can hit vertexNon iterationKin ≤Ttime, thenKcan be the answer. After that you need to recover the path for answer, you can do this inO(NM) memory which fits memory limit I guess.Thanks, I now got a 600ms solution using a modified version of Bellman-Ford.

Concerning problem C, "output any solution" means I can choose any solution ? I can't pass because sometimes my path differs from the judge but it is correct :/

and why is the second example correct ? Why can't we go through 1 2 4 6 5 for a total time of 7 (which is not exceeding 7) ?

You have to finish the journey in the showplace

n.The problem statement asks to find a path from 1 to n. Here n = 6. In your output path, last node should have been 6 instead of 5

oh god...

Thanks

my problem was quite different :/

Publishing editorials after such long delay kills excitement. BTW, why can't editorials published just after contest ends? Any alternate solutions discovered during contest can be added to editorials later..

can someone explain why this MLE?

can someone tell me whats wrong with my D solution? http://codeforces.com/contest/721/submission/21054178

here i consider 0 to be positive first, if the number of negative numbers is even, i find the number with the lowest abs value, keep reducing its abs value untill its sign is changed.

then while we still have operations left, find the number with the smallest abs value, and increase its abs value.

I'm looking forward to the solution... The problem E was a little bit hard for me. :D

I have no idea why did my code failed on test case 50... Can anyone help point it out?

http://codeforces.com/contest/721/submission/21056370

Because you were failing at this test case [Even I did] :-

.

Were I in problem E, I would probably sing when there weren't light because I would be frightened by the dark and sing to encourage myself.

lol

Can anyone explain why 21030683 receives runtime error, but 21056614 passes? All i did was add a random comment at the beginning. Also if i send exactly the same code that got RE with C++14 it passes without any comment magic.

How did you even realize that adding comment would fix it? :o

CF usually doesn't let you submit 2 identical source codes, that's why I added this :D Apparently if you send it using different languages it's fine.

Also, i did some more testing and found that the verdict changes depending on what you write in the comment. For example 21063149, 21063169, 21063271. I think it only happens with C++11.

Is there any way we can contact codeforces team to tell us what exactly that RunTimeError is?

I think it's a problem of codeforces platform.

21074703 is the same code you submitted during the contest and it is Accepted when I submitted it.

This is a serious issue, CODEFORCES TEAM!!! IF YOU ARE READING THIS, please make a note!

Im wondering how author can check D's solutions correct or not? Is it necessary to calculate product of array by using prime accumulation? Ps: I accidentally posted in Russian version, so I must re-post :((

where is the editorial??

Hey guys,

Thank you for the contest, but the problem statements really pissed me off during the contest:

Problem B:

What does that even mean? He wants to enter the web-site? He has managed to enter? He wants to sign in?

Also I missed the sentence about the fact that the input contains the

actualpassword of Vanya, because it was only mentioned in a sentence inside theInputpart of the problem statement. Although I should probably pick on myself for that, authors should have mentioned that in the problem description. I believe that theInputandOutputparts should only describe theformatof the input and output, NOT add any meaning or logic to the problem.Problem D:

Wait, what? Do we still invent numbers these days? He

came upwith a number, he found a number, but certainly he didn't invent a number.Is that a joke or a pun? Because minimalism doesn't really refer to a desire to minimize numbers in an array.

thus-- people around don't really say "thus", they say "so", unless they are coming from the 18th century.Here's what I think would make this sentence clearer and correct:

So he wants to know what the minimum value of the product of all elements of the array would be, if he applies no more than k operations to that arrayAnd this is not everything that could be improved to make problems clearer. I am nitpicking, but it is something that makes thing much harder to understand if done in almost every sentence. We all want to make Codeforces better, and all what I mean by this comment is that there are certainly ways to do that just by spending few minutes to review the problem statements before the contest. Otherwise, every time I read it in English, it turns into a hell of figuring out what the author meant.

I hope other people feel the same way too.

## FreeEditorial

Test case 7 of E-Road To Home doesn't seem to satisfy the conditions of the question. Can Danil start singing at x=12 which is the end? If no, I am getting output of 4,but 5 is the answer. Can someone explains me this thing. Thank you.

No, he would start singing at x=7 till x=12 hence answer is 5, he will not sing from x=0 to x=7 (t is 7).

Thank you..I just missed that case

where is editorial?

editorials please??

Excelent set of problems but with a missing editerial. :(

By the way, I think problem D is full of details which causes a mass of code with mountains of special cases. Anyone think it's good for a Codeforces problem or bad?

You can solve it with 2 cases.Suppose you will change

a_{1},then new product will be:so if you choose

a_{1}the smallest number by absolute value,you have 2 cases,if then you addxelse subtractx.Thanks a lot for your solution of Problem D. Maybe I have made an inappropriate example...

WHERE IS TH EDITORIAL???Editorial from p1kachu's blog.

Thanks you very much

when is 'soon'?????? :(

Editorial pls

Can anyone give detailed solution for problem C,Div 2

And different ways to solve this problem please. I understood the way using dp as suggested by Pixar using dfs and dp using pathLength. What are other ways to solve problem. Full discription please.