Hi everyone, it's me again!
Codeforces Round #372 (Div. 1 + Div. 2) will take place on 17 September 2016 at 16:35 MSK,
After my last round, this will be my second round on Codeforces. I believe you'll find the problems interesting and I hope you'll enjoy the round.
This round would not be possible without danilka.pro who improved one of the problems that made this round possible, and also helped in preparing and testing the round. Also, thanks to all the testers, IlyaLos, HellKitsune and phobos and thanks to MikeMirzayanov for the awesome Codeforces and Polygon platforms.
ZS the Coder and Chris the Baboon's trip in Udayland is over. In this round, you'll help ZS the Coder solve the problems he have randomly came up with. Do you have what it takes to solve them all?
The problems are sorted by difficulty but as always it's recommended to read all the problems.
We wish you'll have many 
solutions and enjoy the problems. :)
As usual, the scoring will be published right before the contest.
UPD : There will be 5 problems in both division as usual.
Scoring :
Div. 2 : 500 — 1000 — 1500 — 2000 — 2500
Div. 1 : 500 — 1000 — 1500 — 2500 — 2750
Good luck and I hope you enjoy the problems!
UPD : Contest is over. I hope you enjoyed the contest and problems :) I'm sure some of you wants to see the editorial now, so here it is while we wait for System Test to start.
UPD : System tests is over. Here're the winners :
Division 1 :
Division 2 :
Congratulations to them!
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
I like Chris the Baboon...
Sorry this is for the sake of making the statements shorter to read :)
shorter statement, better life! ;)
hope that scoring distribution will be announced before the contest ... unlike the previous round
what is the benefit of scoring distribution before the contest ?!
Sometimes we go to C before B if C contains 1500 points and B 1000 :) but if both have same points, we try to see each of them serially. that is the benefit I think.
I know. But I said
before the contest. you can decide what problem to solve when you saw dashboard !(maybe it buys some time to think about it before the contest!)
I think you should solve tasks instead of worrying about score
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
last round was absolutely amazing for learning purpose! DP + GRAPHS + MATHS + ADHOC.. hope to see more such rounds in future covering diverse areas with good problems.. :) thank you.. :D
Excuse me, this round overlaps with topcoder Google Sponsored SRM. Is there any possibility of changing the time of 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 love you zs!
GL & HF :D
zscoder , It would be great if u could ensure that questions aren't googlable _/_
How come it's your second contest after such a short period of time? "We have a long queue, sorry for not answering".
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 everyone and a high rating!
Good luck You too :)
It's about one hour that I submitted a code, and it's still in queue!
hope there be no long queue during the contest.
I wonder if you've ever heard of Photoshop. :P
and I wonder if you've ever heard of Trust :P
You got me wrong buddy, I was talking about cropping the image to remove unnecessary part. :P
maybe cropping makes you feel its not real :P
Paint.exe is enough.
Salute! Prolific problemsetter(potential writer of Round 373:P
Hope this time Codeforces's Server will Work Properly not like the last time ... Very disappointed with the last contest that that turned out to be UNRATED !!!
It wasn't the previous one, it was the one before. Round #371 was correctly held, so it should be the same on Saturday.
I think there is schedule conflict with SRM698 (1:00 AM GMT+9). Could we change the start time earlier or other day?
This contest ends 25 minutes before the SRM.
Never mind, I didn't relize that the starting time had been changed.
What is good to have a Korean problem setter?
NOW WE HAVE A FEASIBLE COMPETITION TIME FOR EAST ASIA. You are my hero man
I am a Malaysian FYI. :)
Oh god my apologies. Sorry for messing that up.
Last round of zscoder div2 B's test case was absolutely amazing . Pretest was passed in the contest for B , but i got wrong ans on test no. 116 . How amazing it is !
Some of the later test cases actually came from successful hacks of the competition, so not all of them are done by me.
Thank you ~~~~~ zscoder ~~~~~ for writting this contest :) the last contest you wrote was very cool.. Hope it will be also :)
I'm glad you enjoyed the last round. I'm sure you'll find this round more interesting :)
Good luck everyone and happy rating
Has the server issue been solved? round 370 became unrated for this.
Round 371 was rated and was held without any problem.
thanks zscoder for your awesome contribution in codeforces.
i hope problems will have ideas this time because problem A&B in the previous round were just about coding with no ideas
I do agree! last contest's A & B were less logic oriented, but more coding oriented, but problem D was really nice!
This is my last contest before my school starts :( Gotta do well this time.
GL & HF everyone.
:)
Not sure why you've been downvoted. I'll risk my reputation too.
Good luck!
thank you I'm not sure why I got downvoted too I was just wishing good luck for everyone I don't see anything harmful in that.
Oh no, can you please make the contest time as usual as it was :(
good luck and high rating~
مش لازم تحشر اسمك ف كل المسائل .... فاكس الجو بتاع السبكي ده :V
Maybe we can have more animals in coming contest's problems. I really enjoyed them xD. And sorry who is the Chris ???
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...I love the short statements :)
Hope the round will as interesting as zscoder's last round.
i hope it will contain more thinking and less knowledge , and good luck for everyone .
Yeah! More thinking problems needed :D
it's edited now , i wasn't mean that , excuse me u misunderstood me.
:D okk! so, you should thank me :D
thank you for sure :D
It's okay :P
Good luck and have a hight rating, thanks you every one.
What does the tag "multiple-of-three-again" mean ? :"D
My last round was round 369, and 369 is a multiple of 3.
This round is round 372, another multiple of 3.
Great :D
GL and high rating everyone!
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Can I rush into Div.1? jump ahead////
Yes you can
pro _/_
however...i made a wtf mistake..& my friend wa 6 times on B.. so..wish the next roundQAQ also,thank u lala
10 min delay.
Why? Will that mean a slow website today?
maybe because about 1k more people registered for today.
why you guys do this at very last time? (the delay) :3
They usually do it because the servers are overloaded
Y dont u stop posting useless comments to ease some load off the server
How is answering his question useless? Anyways, the load of one comment is negligible relative to 8k users loading a page.
will that cause "in queue" verdict? :(
No, queue will be empty because nobody will be able to submit :D
That isn't ":D" This is "X("
Swarm of comments about delay incoming...
Have already started :P
Your comment is one of them?
:/
Now much smaller gap between Codeforces round and Topcoder SRM
The dalays are really annoying when I make plans taking into account the time and duration of a CF contest. Now I have a date and will have to leave 10 minutes before the contest ends, and I'm sure a lot of people are in the same situation. :/
Ya i have another topcoder srm later :D
So you're saying "Girls > Contests"? smh
No, he's just making sure that we all know he has a date :D
Div 2 round starts 1 second after div 1. XD
Missed the contest due to calendar bug :/
https://calendar.google.com/calendar/embed?src=br1o1n70iqgrrbc875vcehacjg%40group.calendar.google.com
shows 14:35 UTC
Div2B Pretest 6 is messing up a lot of people this contest
Be carefull about sub string.
It messed me up as well! Can you tell me the reason?
For me, I forgot to fill the previous '?' into letters.
Try "?AABCDEFGHIJKLMNOPQRSTUVWXY?" :)
What do you mean?
Div2 B should specify that all '?' those that are not in the 26 range solution must also be replaced.I think even though many people got the logic right, not including this fact is giving them many penalties.
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.
Yes, there are no logical reasons to believe in that, but there are psychological reasons. We are not computers, we are humans with biases :)
Why do I have a wrond answer for presest 1??? Help me please. My answer for 1 pretest is the same as a correct one. here is the code:
map<char, int>a;
int main(){ ios::sync_with_stdio(false); string s; cin >> s;
}
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.
How?
I used codeforces' "custom invocation" to test my code on their servers and track down the problem, i changed a while condition to a variable and I assigned the boolean statement to it (check my first two submissions on B) , i still dont know how did the code run correctly on my compiler and on ideone but gave -1 on CF
C is too hard :/
Sadness is when you code D, but can't submit because you didn't solve anything else, and there's only time to solve A, and you don't even know if D will pass, so you don't want to risk it, so you're just sitting there, waiting for the contest to be over :(
Missed D by a second :/
Can someone explain solution for Div.2 C? I got TLE on pretest 5 :/
Jump for i-th level is to number i * i * (i - 1) * (i - 1)
Can you explain that?
You want the number before the sqrt to be i ^ 2 * (i+1)^2 since it must be divisible by i and be a prefect square whose root is divisible by i+1. Doing so would make the number the start of level i (for i > 1) be i * (i-1) (simple sqrt of the above expression with i larger by one). So you want to solve i * (i — 1) + i * x = i ^ 2 * (i+1)^2 i * x = i ^ 2 * (i+1)^2 — i * (i-1) x = i * (i+1)^2 — i*(i+1) x = i^3+2i^2+1
for the transition from level 1 to 2 you want to get the number on the screen to 1 ^2 * 2 ^2 so you print 2
Why not i*i*(i-1) — i + 2 ?
i * i * (i — 1) — i + 2 = i ^ 3 — i ^ 2 — i + 2
If i = k + 1
= (k + 1) ^ 3 — (k + 1) ^ 2 — k — 1 + 2 = k ^ 3 + 3 * k ^ 2 + 3 * k + 1 — k ^ 2 — 2 * k — 1 — k — 1 + 2 = k ^ 3 + 2 * k ^ 2 + 1
Which is identical to what I proved above, just with a different definition for i(my i = your 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.
I wish I had the time to participate the contest, when I came back from other stuff I solved the div2 questions pretty quickly. Feels bad to miss a train straight towards purple.
How to solve Div1 B？
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.
That wouldn't work with e.g. 4 5 20 0 3 0 1 0 1 2 0 2 3 0 0 2 5 1 3 5
because you will take the shortest path with the three '0' edges, fix them as 1,1,18, but then there will be a path of length 6 through one of the '5' edges.
How do you select that particular edge whose cost you increase? Consider this case.
5 5 10 0 4
0 2 0
0 1 1
1 2 2
2 3 3
3 4 0
Here, if you increase the cost of the edge 3-4, it works but it fails to find a solution if you choose the edge 0-2.
"You God Damn Right!". Thanks for anti-test.
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 don't think so. Why are you assigning 1 to all of them? Are you sure it will be equal to L?
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 - Xwhere X= number of zero weights on this path-1Now 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 need to run dijkstra again to confirm it is valid.
4 4 13 0 3 0 1 0 1 3 0 0 2 11 2 3 1
should answer "NO"
Really, really good problems, thank you! :) I decided to start with C and finished it 15 minutes before the end. However it was better not to submit it without having another problem solved so I started B but couldn't finish coding it, both B and C were pretty nice :) I will send this code when system test is done, let's see if it passes :)
You like B too!!! Seriously, now I'm convinced I wrote crap for 2 hours ;_;
C Div 2. Anyone? How to solve it?
Count
lfrom 1 to n and for eachloutputl == 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.
Why is it
(i)*(i+1)*(i+1) — (i-1)
rather than this
(i)*(i)*(i+1)*(i+1)
I see the second formula in the pattern that you showed.
When you are in Li, you already have i*(i-1) and your target is (i)*(i)*(i+1)*(i+1), the difference is i*i*(i+1)*(i+1) — i*(i-1) ,for a single push, you increase by i, so you gonna divide the difference by i, and you'll get (i)*(i+1)*(i+1) — (i-1).
Sorry for omitting this process.
Thanks everyone :)
I like this round. Problems are so interesting!
I hope my rating will be increased.
Can someone explain the solution of Div.2_B? I don't know why my code is wrong. so i want to compare right solution :>
Do you print the whole string? Do you print any question marks?
I change ? mark to alphabet.
i passed till pretest 5, but i can't pass pretest 6.
You only replace the ?s in the substring. You need to replace every ? in the input.
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
plz don't open round more or I'll hate you
Why did you dislike this round?
20709423 This is the submission for Div 2 B Can anyone tell me why this one fails on PRETEST 6
Because
replace all the question marks with uppercase lettersI really liked problem B! But I don't understand the reason behind its constraints. Does the
solution intended to get AC? (Considering the 4s time limit...)
I had that solution but thought it'd fail. I was hoping to find O(n2 + nm) solution (or something like that), but I came up with an
one!
could you explain your solution please
I think you can understand the whole solution by just looking at my submission! 20704461
A brief description:
First, consider the weights of erased edges equal to 1. Then run dijkstra and find the distance from s to any other vertex. Let d[v] be the distance between s and v.
Let need be L - d[t]. Now run another dijkstra from s. We are aiming to add need to the distance from s to any other node that we could! When you are relaxing an edge vu, check if you can change the weight of this edge in order not to make the distance from s to u less than d[u] + need.
So in the second run of dijkstra we add this extra if before relaxing the edge e = vu:
Problems are really interesting and challenging, great!
Some personal feelings:
1.The difficulty progression from D2.C to D2.D is really harsh, I failed to figure out any workable solution in last half of the contest.Anyway, it's a good problem.
2.D2.C will give a really short constructive solution.It's beautiful, but also lost some fun of hacking.
I agree. Div 2C was a beautiful problem.
I don't think this is a good codeforces round. No offence... Maybe just that i'm not good at solving these problems... My rating... Excited
Maybe many-people thought "What the hell B pretest 6?"
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.
Problem Div 2D. Is it true that we have to find shortest path that contain the least amount of erased edge?
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.
Please help!!! I dont know whats wrong with those B->http://mirror.codeforces.com/contest/716/submission/20707069 C->http://mirror.codeforces.com/contest/716/submission/20710823
Its more likely that I am wrong in C..... I understand the editorial but I dont know whats wrong with mine
Same here dude! :( ! I still have no clue why my submissions are wrong despite implementing the same methods
Allow solutions with finding 1/x (modulo mod) using mod — 2 as a power instead of phi(mod)-1 pass pretests in Div1C is the evilest thing I've ever seen :D
The great evil plan of choosing all M as prime in all pretests. >=]
As I am unable to submit because of pending systests, can someone look at my code for div 2 D and let me know if it will pass?
After assigning you should check if the path you got at the beginning is still the shortest one after you removed all the zeroes.
Thanks :)
I made another mistake. The path I chose didn't necessarily have the least number of erased edges. If this path has more erased edges than L, I'll be printing NO.
Всем привет:) Помогите понять, как работает этот код по Adiv2 на тесте
~~~~~
1 2
3
~~~~~
Это решение читает N+1 чисел. Может кто объяснить, как работает scanf ?
Если числа в input кончились, то он считывает последнее => получается тест
Спасибо, а если читать при помощи cin, оно же должно зависнуть?
Нет, с cin тоже самое
Там считывается N чисел.
scanf("&d",&x);— ничего не считывает.Problem Div2-B 716B - Complete the Word was similar to this recent problem 701C - They Are Everywhere. I just copied my solution from that round.
Indeed both uses the two pointer technique, but this time is more about how to assign the letters I believe.
I think the algorithm is called sliding window and I have a lot of fun solving these problems :D
how? whas there any '?' letter? can you show me your code for 701C?
716B - Complete the Word — 20694959
701C - They Are Everywhere — 19361724
In 701C - They Are Everywhere, My rangeQuery(l,r) function returns number of distinct letter from index l to r. And in 716B - Complete the Word I just had to check for each index whether rangeQuery(i, i + 25) + number of '?' in that range = 26.
WOW
I was printing only 26 letters for Div2B. OMG.
You aren't the only one ;)
I didnt only print 26 but I got WA in pretest 6 too.... What ????????????????????????????????? http://mirror.codeforces.com/contest/716/submission/20707069
Please check if your solution ever outputs any question marks. It shouldn't.
Div 1B RIP.
.
It's not a thing to be proud of.
I know that but i want to explain that the system test is weak
RIP B :( div1 & div2
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
zscoder is really lucky for me. In his last round, I got + 119 and now expecting + 130.
The questions were really nice! Hope to see more rounds from you :D
Can anyone tell me why am I getting WA here.
It reads WA on 9 because "Integer 0 violates the range [1, 1000000000000000000]" whereas 0 is the vertex not the weight.
This looks fishy. Anybody any clues?
YES
1 3 13
2 3 0 <-
Oops! Thanks. This was silly.
Very Very Very bad round for me! Back to Earth Again After flying high last time out
lol, -89 is not that bad, I got -122 once.
I got a -109 because B failed systest. I only had to change literally one line. Imagine how I feel man. If you look at my rating, the last two contests I participated in were the worst. Coincidentally, both contests were written by zscoder lol ;(
I'm sure u'll be back with a bang. I can completely understand what this feels like. Sometimes, its all about what kind of day ur having. Let this miserable feeling drive u to completely finish the next contest.
Eagerly waiting for editorial
Editorial is already out.
Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
Finally became blue for the first time today :) :D
Unfortunately became blue for the first time in over half a year :( D:
What in 22 test in div1 B?
What is correct answer for test case #44 for problem B. Is it -1.
I got wrong answer on test case 44 for problem B (Div2). That happened because I misread the question and instead of looking for substring I looked for subsequence.
I liked the prerequisites section for each problem in the editorial, that is very helpful. Hope that next editorials will have this section.
How to get full test of any problem in problemsets? Not just the first few numbers.
LOL worse did this contest and got +644.
Does this set a record? :D
Yeeeaaaahhh!!11!
Must notify, that my previous round was much more better, and that time i got only +319.
In div2 B pretest 6, http://mirror.codeforces.com/contest/716/submission/20710802
Seriously,is that a bug?
Your solution outputted the string: ABABABBABDEFGHIMNOPQRABABABABATUVWXYAAAAAABABABABAAAAAAAAAAKLCSJBAAAAAAAAAZ, which obviously does not contain a valid substring.
Auctully,it "contains all the letters of the English alphabet exactly once"
Try to count it,I have counted that my output and Jury's answer have same number of 'A',also other alphabet,just different of position.
You need to have A-Z in consecutive 26 positions! Its a substring and not a subsequence
In the second problem the required output is : "If there is no way to replace all the question marks with uppercase letters such that the resulting word is nice, then print - 1 ". so I understand that i should print the nice sub string which contains the letter only once and all the alphabet letters .. so how could test six be correct ? I mean , the problem statement is not clear enough concerning this part that i should print the whole string not only the required nice sub string
From problem statement, This string should match the string from the input, except for the question marks replaced with uppercase English letters. So you should print the whole string.
Please check this out , my submission for div 2B #372 Running the same code on ideone and my pc gives me correct answer , while CF compiler does something else. Is it some bug, costed me rating loss , please check ... Help me out if i am doing wrong somewhere! Ideone link — http://ideone.com/tJdGrc My submission link CF — http://mirror.codeforces.com/contest/716/submission/20716292
You are printing a "?" at the end of the correct string! Recheck it :) Specially the print statements
I tried it using G++ and i got the correct answer ! No idea why CF prints an additional ? :(
Size of ans should be at least 27, and ans[26] = 0.
It worked . But why is it so ? Could you please explain ? Why do g++ compiler shows correct answer while Cf compiler doesnt??
Compiler is allowed to do anything with invalid program including sometimes producing expected output. Read this.
Great Contest It Was... Thanks To ZS-the-Coder !!! Waiting for your next one ...
Div. 2 B solution with using regexes 20716509, Perl.
Hey guys can you help me with something at problem div2 D? :)
If you replace all zeroes with 1 and you run Dijkstra you should obtain the shortest path from S to T.
If it is less than L, then it should be a solution.On this path(which contains now 1 instead of zeroes) you transform an 1 in a number which should make this path's length L.The rest of zeroes in the graph(which were transformed in 1) should become a huge number as 10^18.
Why this approach doesn't work? I mean if it were to be another path from S to T lower than the path we just transformed, it could be just in one condition.There was an path which contained no 0 in the first place because if it were to be a path with an zero, it would have become a number which surpasses L in the first place.
Consider this test:
After changing zeros to ones you get the shortest path from 0 to 3: 0-1-3
Its length is 2, so you need to add 3 to one of the edges. If you choose 1-3 (because there's no reason not to choose it), the length of this path becomes 5. However, the shortest path from 0 to 3 is now 0-1-2-3 with length 4.
I figured out after minutes why I was wrong :)).You are right.Thanks for helping :)
Hi Guys! I got a runtime error on test 84 in Div2 B problem. Here the length of the string is less than 26. But my loop is as follows: for(i=0;i<=s.length()-26;i++) and it gives rte but instead if i store s.length()-26 in a variable,say p, and write the loop as for(i=0;i<=p;i++) its getting accepted. Can you please give me a reason as to why this is happening? My rte code: http://mirror.codeforces.com/contest/716/submission/20693471 My ac code: http://mirror.codeforces.com/contest/716/submission/20713665 Please help me out. Thanks in advance!
because s.length is an unsigned variable so when you do "s.length — 26" it turns to a big number because it can't be negative so you should do an if statement before the loop that is like:
if(s.length < 26){
cout << -1;
return 0;
}
I sign up Codeforces Round #372 yesterday and joined the competition and AC THE A,B,C.But today,when I log in and search my contests "Codeforces Round #372"disapear and I can't know my score.Why? who can help me?
I know I shouldn't be asking this kind of question, but
can anyone who sees this comment please please explain where am i going wrong in this code for Complete the Graph. I am calculating minimum distance from t to all other vertices and then calculating minimum distance from s and updating the edges. I have also tried commenting my code for first time to make it easier to understand. Please help me. I have been stuck on this question for 8 days and now I am finding it hard to move on from this.
I would really appreciate your help.
Please help