Привет, Codeforces!
30 сентября 2016 года в 17:05 Мск состоится Codeforces Round #374 (Div. 2) для участников из второго дивизиона. Участники первого дивизиона традиционно могут участвовать вне конкурса. Обратите внимание на необычное время проведения.
Это мой второй раунд на Codeforces, я старался сделать задачи интересными для всех, поэтому рекомендую прочитать условия всех задач! Желаю всем участникам раунда найти что-то новое и интересное для себя, и, естественно, быстрых решений и высокого рейтинга!
Хочу поблагодарить Михаила MikeMirzayanov Мирзаянова за замечательные платформы Codeforces и Polygon, за помощь в придумывании задач и их подготовке, своих очень хороших друзей Данила danilka.pro Сагунова также за помощь в подготовке соревнования и Ивана BledDest Андросова за прорешивание раунда.
Участникам будет предложено 5 задач и 2 часа на их решение. Разбалловка будет традиционно объявлена ближе к началу раунда. :)
Разбалловка почти стандартная: 500-1000-1500-2000-2750
UPD: Разбор
30 September
Oh, sorry, my mistake. Fixed.
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 danilka.pro Sagunov also for help in preparing the round
what does "friens" mean??
UPD: fixed.
thanks, fixed
good luck
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.
Round 374.
374 = 2 × 11 × 17 , Sphenic Number
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 danilka.pro (previous revision, new revision, compare).
After reinstalling windows, I am unable hack in firefox.
i 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
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 ;_;
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?
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
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 english
Div2B 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 some of his n passwords."
I was very confused by this too
The next n lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits.
"pairwise distinct non-empty strings consisting of latin letters and digits."
The statement has said "pairwise distinct non-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.net/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 ai and aj, |ai| < |aj|. Let m be the smallest number of operations required to change the sign of aj. If you apply them to aj, you will get two numbers, ai and new aj, and now |aj| (the new one) = m·x - |aj|. If you apply all those m operations to ai instead (there might be some better ways, but let's consider this), there will be new ai: |ai| (the new one) = m·x - |ai|, and aj will remain unchanged. |aj| > |ai|, m·x - |ai| > m·x - |aj|, 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 i under 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.
pathLength is the number of vertices on some path from vertex 1 to the current vertex v. Among all the possible paths from 1 to v which have pathLength vertices between them, there exists the shortest path. We track the cost of that path here minCost[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: v1, v2, v3, v4, v5, v6.
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: v1 is
[ floor 1 ]and v6 is[ floor 6 ], because we always gain access to all of the verices in a graph from vertex v1 (we always gain access to the floors of a building through the first floor) and we end our travel in a graph in vertex v6 (we cannot move further up from the floor 6).Now, we base our decisions about correspondance of vertices v2, v3, v4, v5 and floors on the fact that if v2 is some
[ floor i]then all of the outgoing edges from v2 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 set of vertices {1, 2, 3, 4, 5, 6}. Then we use topological sort to create an ordered set of vertices with the specified property (we cannot move down from higher floors). Formally, topological sort is a map:
(1, 4, 2, 3, 5, 6).
{1, 2, 3, 4, 5, 6}
Below is a graphical representation of that mapping ( topological sort ).
The distinctive property of the picture from the right is that all of the edges are looking to the right. None of the edges look to the left (backwards). Not a single child is pointing to a parent. That means, when you reach vertex v[i] as you go from left to right, there is no way you can update the state of v[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 vertex v[i] all of it's children. The next vertex in a sequence after v[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 → v if we are 100% sure about the optimality of vertex u. That is, we have to consider all of the edges coming into u before we start looking at the edges coming out of the node u.
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(n2 × 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 than O(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(n2 × m) to O(n2 + 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 vertex v[1] leading to v[i].
Now, as it is drawn in the picture, we split the set of all possible Paths from vertex v[1] to vertex v[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] to v[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 from v[1] to vertex v[i]. But it is not NOT among all the possible paths, it is only among the paths in the group 5 (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(n2).
does not multiply the complexity O(n2) to make O(n2 × m). This loop adds to the outer loop (which gives O(n + m)) and multiplies inner-most loop (which gives O(n × m)).
If we combine them, we get the complexity O((n + m) × n) = O(n2 + 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.net/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.net/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 140ms to perform them.
The case #12 takes 2237322 operations and the times blows up to 1076ms.
Look at this: 21172009
17835090 operations and only 265ms!
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 right order? For us the right order is the situation when we finish processing children of vertex v[i], the next vertex in our order v[i + 1] has the cost (time to travel) which cannot be 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 vk. For example, it has 3 parent vertices: v1, v2, v3. Then we will do the reevaluation of the cost only 3 times!
On some step of our algorithm we become sure that we cannot improve the estimate of the cost to travel to v1. At that moment, we update estimate of child vertex vk.
On some other step of the algorithm we become sure in the estimate of v2. Then we do the second update of the state of the vertex vk.
And situation repeats for the vertex v3.
If we have processed all of the parents v1, v2, v3 of the vertex vk, there is no way we could ever improve the estimate of the vertex vk! Why? Because there are no more vertices left which lead to vk and we can only improve the estimate of the cost of vk from vertices leading to vk. What does this mean for vk? It means that vk itself became optimal and we can update the estimates of the children of vk.
I was wrong regarding the impossibility to solve it with DFS. Here is the solution with DFS.
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.net/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
DIV2B pretests are too weak. my wrong solution where i didnt increment time by 5 sec when k strings are matched passed pretests . hell . hoping my final solution passes
I was surprised that so many people solved C
There was a similar problem a few months ago on topcoder: DoubleWeights.
well it seems only 600 really solved it...
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
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
dkjsfkhg 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...
Когда читаешь задачу B, а именно строчку:"Ваня не будет вводить один и тот же пароль несколько раз." Кажется, что в тестах может быть случай, когда существует несколько ОДИНАКОВЫХ паролей. Однако же попытки взлома с таким условием дали "некорректный тест" [FAIL All passwords must be distinct], Что говорит о том, что все пароли должны быть уникальны. И судя по решениям участников не так мало людей согласны со мной в понимании условий этой задачи.
Сказать то хочется только одно по этому случаю: Не надо так)))
Иногда, когда я не понимаю условие после прочтения на русском, я использую такой трюк: я открываю описание задачи на английском =)
После прочтения условия задачи в первый раз у меня тоже возник такой вопрос, но, открыв английскую версию, всё сразу встало на места. Там есть вот такая чёткая фраза: " pairwise distinct non-empty strings".
на русском тоже вроде понятно всё " различные непустые строки"
И действительно. Видимо сегодня просто много невнимательных людей)
My B solution got hacked, What would be the problem with that code? http://codeforces.net/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]
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 passwords
hacking 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 ??
Because of DP
Wow, I got WA on TC 66 because of integer overflow.
To get AC, I changed a > b + c to a - b > c (where a, b, c are distance and dp values)
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.net/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)
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??
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::sort must be written in such a way that if a < b is true, then b < a is false. And in your code, if strings a and b are both different form the right password, but their sizes are equal, then a < b and b < a. That's why it's RE
Try changing true to false in the last line of comparing function, I think this will work.
Yes, it worked.
So we may have a < b and b < a being both false, but we can't have a < b and b < a being 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 < b and b < a are both false, then it just means that a = b for 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 vovuh (previous revision, new revision, compare).
Why this code gives http://codeforces.net/contest/721/submission/21026545 gives runtime error while http://codeforces.net/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
bool 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) = = true and comp(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
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 @vovuh
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.first in the loop, so your solution works even if the value you assign to it is greater that int type 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 hard
why 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.net/contest/721/submission/21033441
How did you even manage to pass with this solution? I suppose it is nicely optimized O(N3), so I doubt you can make it work.
The O(NM) solution uses well-known Bellman-Ford algorithm.
On iteration K if you can reach vertex N, that means you can visit this vertex using K edges. Now we are going to read the statements and see this:
'there are no cyclic routes between showplaces.'
That means that on iteration K all the edges are different, and more than that, there can not be two equal vertexes on this path. This means that this path consists of K + 1 different vertexes.
In conclusion, you simply run Bellman-Ford and if you can hit vertex N on iteration K in ≤ T time, then K can be the answer. After that you need to recover the path for answer, you can do this in O(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
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 tell me whats wrong with my D solution? http://codeforces.net/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.net/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!
I'm wondering how author can check solution of D correct or not? Is it necessary to calculate product of all elements by using prime accumulation?
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 actual password of Vanya, because it was only mentioned in a sentence inside the Input part 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 the Input and Output parts should only describe the format of 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 up with 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 array
And 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).
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 a1,then new product will be:
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.
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.