zscoder's blog

By zscoder, history, 4 years ago, ,

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 dans 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 — 25002750

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!

• +423

 » 4 years ago, # |   +10 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   +16 I like Chris the Baboon...
•  » » 4 years ago, # ^ |   +58 Sorry this is for the sake of making the statements shorter to read :)
•  » » » 4 years ago, # ^ |   +55 shorter statement, better life! ;)
 » 4 years ago, # |   -33 hope that scoring distribution will be announced before the contest ... unlike the previous round
•  » » 4 years ago, # ^ |   +18 what is the benefit of scoring distribution before the contest ?!
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 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!)
•  » » » » 4 years ago, # ^ |   +88 I think you should solve tasks instead of worrying about score
 » 4 years ago, # |   +8 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   +29 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
 » 4 years ago, # |   +5 Excuse me, this round overlaps with topcoder Google Sponsored SRM. Is there any possibility of changing the time of contest?
•  » » 4 years ago, # ^ | ← Rev. 4 →   +19 There is 25 minutes after cf round according to clist.by.
•  » » 4 years ago, # ^ |   +36 Last time I checked there is a 25 minutes break between them (which is the reason this time was chosen in the first place)
•  » » » 4 years ago, # ^ |   0 we love you zs!
 » 4 years ago, # |   -8 GL & HF :D
 » 4 years ago, # |   -30 zscoder , It would be great if u could ensure that questions aren't googlable _/_
 » 4 years ago, # |   +38 How come it's your second contest after such a short period of time? "We have a long queue, sorry for not answering".
•  » » 4 years ago, # ^ |   +15 We just worked with a huge pool of problems, part of which are gone to Round 369, another part come to this round.
 » 4 years ago, # |   +9 Good luck everyone and a high rating!
•  » » 4 years ago, # ^ | ← Rev. 6 →   +2 Good luck You too :)
 » 4 years ago, # |   -38 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.
•  » » 4 years ago, # ^ |   +13 I wonder if you've ever heard of Photoshop. :P
•  » » » 4 years ago, # ^ |   +13 and I wonder if you've ever heard of Trust :P
•  » » » » 4 years ago, # ^ |   0 You got me wrong buddy, I was talking about cropping the image to remove unnecessary part. :P
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 maybe cropping makes you feel its not real :P
•  » » » » » 4 years ago, # ^ |   +14 Paint.exe is enough.
 » 4 years ago, # |   0 Salute! Prolific problemsetter(potential writer of Round 373:P
 » 4 years ago, # |   -21 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 !!!
•  » » 4 years ago, # ^ |   0 It wasn't the previous one, it was the one before. Round #371 was correctly held, so it should be the same on Saturday.
 » 4 years ago, # |   0 I think there is schedule conflict with SRM698 (1:00 AM GMT+9). Could we change the start time earlier or other day?
•  » » 4 years ago, # ^ |   +9 This contest ends 25 minutes before the SRM.
•  » » » 4 years ago, # ^ |   0 Never mind, I didn't relize that the starting time had been changed.
 » 4 years ago, # |   +8 What is good to have a Korean problem setter?NOW WE HAVE A FEASIBLE COMPETITION TIME FOR EAST ASIA. You are my hero man
•  » » 4 years ago, # ^ |   +46 I am a Malaysian FYI. :)
•  » » » 4 years ago, # ^ |   +15 Oh god my apologies. Sorry for messing that up.
 » 4 years ago, # |   0 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 !
•  » » 4 years ago, # ^ |   +9 Some of the later test cases actually came from successful hacks of the competition, so not all of them are done by me.
 » 4 years ago, # |   0 Thank you ~~~~~ zscoder ~~~~~ for writting this contest :) the last contest you wrote was very cool.. Hope it will be also :)
•  » » 4 years ago, # ^ |   0 I'm glad you enjoyed the last round. I'm sure you'll find this round more interesting :)
 » 4 years ago, # |   +4 Good luck everyone and happy rating
 » 4 years ago, # |   0 Has the server issue been solved? round 370 became unrated for this.
•  » » 4 years ago, # ^ |   +15 Round 371 was rated and was held without any problem.
 » 4 years ago, # | ← Rev. 2 →   +1 thanks zscoder for your awesome contribution in codeforces.
 » 4 years ago, # |   -33 i hope problems will have ideas this time because problem A&B in the previous round were just about coding with no ideas
•  » » 4 years ago, # ^ |   -39 I do agree! last contest's A & B were less logic oriented, but more coding oriented, but problem D was really nice!
 » 4 years ago, # |   0 This is my last contest before my school starts :( Gotta do well this time.GL & HF everyone.:)
•  » » 4 years ago, # ^ |   +24 Not sure why you've been downvoted. I'll risk my reputation too.Good luck!
•  » » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   -41 Oh no, can you please make the contest time as usual as it was :(
 » 4 years ago, # |   0 good luck and high rating~
 » 4 years ago, # |   -56 مش لازم تحشر اسمك ف كل المسائل .... فاكس الجو بتاع السبكي ده :V
 » 4 years ago, # |   -6 Maybe we can have more animals in coming contest's problems. I really enjoyed them xD. And sorry who is the Chris ???
•  » » 4 years ago, # ^ |   +37 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. :)
•  » » » 4 years ago, # ^ |   -27 yeah...I love the short statements :)
 » 4 years ago, # |   -15 Hope the round will as interesting as zscoder's last round.
 » 4 years ago, # | ← Rev. 2 →   0 i hope it will contain more thinking and less knowledge , and good luck for everyone .
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Yeah! More thinking problems needed :D
•  » » » 4 years ago, # ^ |   0 it's edited now , i wasn't mean that , excuse me u misunderstood me.
•  » » » » 4 years ago, # ^ |   -14 :D okk! so, you should thank me :D
•  » » » » » 4 years ago, # ^ |   0 thank you for sure :D
•  » » » » » » 4 years ago, # ^ |   0 It's okay :P
 » 4 years ago, # |   0 Good luck and have a hight rating, thanks you every one.
 » 4 years ago, # |   0 Help ZS the Coder wanaa to kill me with the problemsSorry :(
 » 4 years ago, # |   +11 What does the tag "multiple-of-three-again" mean ? :"D
•  » » 4 years ago, # ^ |   +40 My last round was round 369, and 369 is a multiple of 3.This round is round 372, another multiple of 3.
•  » » » 4 years ago, # ^ |   +6 Great :D
•  » » » 4 years ago, # ^ |   -37 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: mapa; int main(){ ios::sync_with_stdio(false); string s; cin >> s; string ss = ""; if (s.size() < 26) { cout << -1 << '\n'; return 0; }bool o = 0; int l = 0; for (int i = 0; i <= s.size() — 26; ++i) { a.clear(); bool ok = 1; string str = ""; for (int j = i; j <= i + 26; ++j) { a[s[j]]++; str.push_back(s[j]); if (s[j]!='?'&&a[s[j]] > 1){ ok = 0; break; } } if (ok) { ss = str; o = 1; l = i; break; }}for (int i = 0; i < ss.size(); ++i) { if (ss[i] == '?') { for (char c = 'A'; c <= 'Z'; ++c) { if (ss.find(c) == ss.npos) { ss[i] = c; break; } } } }if (!o)cout << "-1" << '\n'; else { for (int i = 0; i < l; ++i) cout << s[i]; for (int i = l; i <= l + 26; ++i) cout << ss[i - l]; for (int i = l + 26 + 1; i < s.size(); ++i) cout << s[i];} }
 » 4 years ago, # |   0 GL and high rating everyone!
 » 4 years ago, # |   +4 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   +5 Can I rush into Div.1? jump ahead////
•  » » 4 years ago, # ^ |   0 Yes you can
•  » » » 4 years ago, # ^ |   +5 pro _/_
•  » » » 4 years ago, # ^ |   0 however...i made a wtf mistake..& my friend wa 6 times on B.. so..wish the next roundQAQ also,thank u lala
 » 4 years ago, # |   +30 10 min delay.
•  » » 4 years ago, # ^ |   0 Why? Will that mean a slow website today?
•  » » » 4 years ago, # ^ |   +3 maybe because about 1k more people registered for today.
 » 4 years ago, # |   +29 why you guys do this at very last time? (the delay) :3
•  » » 4 years ago, # ^ |   +8 They usually do it because the servers are overloaded
•  » » » 4 years ago, # ^ |   -14 Y dont u stop posting useless comments to ease some load off the server
•  » » » » 4 years ago, # ^ |   +9 How is answering his question useless? Anyways, the load of one comment is negligible relative to 8k users loading a page.
•  » » » 4 years ago, # ^ |   +2 will that cause "in queue" verdict? :(
•  » » » » 4 years ago, # ^ |   0 No, queue will be empty because nobody will be able to submit :D
•  » » » » » 4 years ago, # ^ |   +1 That isn't ":D" This is "X("
 » 4 years ago, # |   +33 Swarm of comments about delay incoming...
•  » » 4 years ago, # ^ |   0 Have already started :P
•  » » 4 years ago, # ^ |   +36 Your comment is one of them?
 » 4 years ago, # | ← Rev. 3 →   0 :/
 » 4 years ago, # |   +17 Now much smaller gap between Codeforces round and Topcoder SRM
 » 4 years ago, # | ← Rev. 2 →   +30 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. :/
•  » » 4 years ago, # ^ |   +11 Ya i have another topcoder srm later :D
•  » » 4 years ago, # ^ |   +10 So you're saying "Girls > Contests"? smh
•  » » » 4 years ago, # ^ |   +49 No, he's just making sure that we all know he has a date :D
 » 4 years ago, # | ← Rev. 2 →   +4 Div 2 round starts 1 second after div 1. XD
 » 4 years ago, # |   0 why cf was down for first 20 min to only me???
 » 4 years ago, # |   +6 Missed the contest due to calendar bug :/https://calendar.google.com/calendar/embed?src=br1o1n70iqgrrbc875vcehacjg%40group.calendar.google.comshows 14:35 UTC
 » 4 years ago, # | ← Rev. 2 →   0 Div2B Pretest 6 is messing up a lot of people this contest
•  » » 4 years ago, # ^ |   -10 Be carefull about sub string.
•  » » » 4 years ago, # ^ |   +3 It messed me up as well! Can you tell me the reason?
•  » » » » 4 years ago, # ^ |   0 For me, I forgot to fill the previous '?' into letters.Try "?AABCDEFGHIJKLMNOPQRSTUVWXY?" :)
•  » » » 4 years ago, # ^ |   0 What do you mean?
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   0 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 "
•  » » 4 years ago, # ^ | ← Rev. 2 →   +11 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'
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ |   0 Yes, there are no logical reasons to believe in that, but there are psychological reasons. We are not computers, we are humans with biases :)
 » 4 years ago, # | ← Rev. 2 →   -92 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:mapa;int main(){ ios::sync_with_stdio(false); string s; cin >> s; string ss = ""; if (s.size() < 26) { cout << -1 << '\n'; return 0; } bool o = 0; int l = 0; for (int i = 0; i <= s.size() - 26; ++i) { a.clear(); bool ok = 1; string str = ""; for (int j = i; j <= i + 26; ++j) { a[s[j]]++; str.push_back(s[j]); if (s[j]!='?'&&a[s[j]] > 1){ ok = 0; break; } } if (ok) { ss = str; o = 1; l = i; break; } } for (int i = 0; i < ss.size(); ++i) { if (ss[i] == '?') { for (char c = 'A'; c <= 'Z'; ++c) { if (ss.find(c) == ss.npos) { ss[i] = c; break; } } } } if (!o)cout << "-1" << '\n'; else { for (int i = 0; i < l; ++i) cout << s[i]; for (int i = l; i <= l + 26; ++i) cout << ss[i - l]; for (int i = l + 26 + 1; i < s.size(); ++i) cout << s[i]; } }
•  » » 4 years ago, # ^ |   -6 it's freaking unfair
•  » » 4 years ago, # ^ |   +21 Don't post code during contest
•  » » 4 years ago, # ^ |   +2 Seriously, Contest blog should be blocked during contest.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 How?
•  » » » » 4 years ago, # ^ |   0 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
 » 4 years ago, # |   +2 C is too hard :/
 » 4 years ago, # |   -18 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 :(
 » 4 years ago, # |   0 Missed D by a second :/
 » 4 years ago, # |   0 Can someone explain solution for Div.2 C? I got TLE on pretest 5 :/
•  » » 4 years ago, # ^ |   +18 Jump for i-th level is to number i * i * (i - 1) * (i - 1)
•  » » » 4 years ago, # ^ |   0 Can you explain that?
•  » » » » 4 years ago, # ^ |   +3 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+1for 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
•  » » » 4 years ago, # ^ |   0 Why not i*i*(i-1) — i + 2 ?
•  » » » » 4 years ago, # ^ |   0 i * i * (i — 1) — i + 2 = i ^ 3 — i ^ 2 — i + 2If 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 + 1Which is identical to what I proved above, just with a different definition for i(my i = your i — 1).
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 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.
 » 4 years ago, # |   +1 How to solve Div1 B？
•  » » 4 years ago, # ^ |   0 It scares me when I spend 2 hours coding something and then a much stronger coder asks how to solve it :SNow I'm confused if I'm right. Well, at least I won't lose ratings.
•  » » 4 years ago, # ^ |   -20 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.
•  » » » 4 years ago, # ^ |   0 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 5because 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.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 How do you select that particular edge whose cost you increase? Consider this case.5 5 10 0 40 2 00 1 11 2 22 3 33 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.
•  » » » » 4 years ago, # ^ |   0 "You God Damn Right!". Thanks for anti-test.
•  » » 4 years ago, # ^ |   0 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'
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 I don't think so. Why are you assigning 1 to all of them? Are you sure it will be equal to L?
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 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...
•  » » 4 years ago, # ^ |   0 I thought to find all the simple paths between S and T. If on any one path number of zero weights >= (L-remaining weight on this path) then answer exist else answer doesnot exist. Now on this path we replace all zero weights by one except the last zero weight. On the last zero weight edge we put weight = L - X where X= number of zero weights on this path-1 Now we can put INF on rest of zero weight edges so the given condition gets satisfied. I could not implement within the contest time. :( Can someone comment on the correctness of this solution ?
•  » » » 4 years ago, # ^ |   +3 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 1should answer "NO"
 » 4 years ago, # |   0 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 :)
•  » » 4 years ago, # ^ |   -15 You like B too!!! Seriously, now I'm convinced I wrote crap for 2 hours ;_;
 » 4 years ago, # |   +1 C Div 2. Anyone? How to solve it?
•  » » 4 years ago, # ^ |   0 Count l from 1 to n and for each l output l == 1 ? 2 : l * l * l + 2 * l * l + 1. That's all you need to do.
•  » » 4 years ago, # ^ |   0 just for all i = 1..n output i * (i + 1) * (i + 1) — i + 1
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 4 years ago, # ^ | ← Rev. 3 →   +12 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*2L2 2 = 1*2 --> 36 = 2*2*3*3L3 6 = 2*3 --> 144 = 3*3*4*4L4 12 = 3*4 --> 400 = 4*4*5*5L5 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.
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   +1 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.
•  » » 4 years ago, # ^ |   0 Thanks everyone :)
 » 4 years ago, # |   0 Can anyone tell me a solution approach/hint for Div2/D? Thanks! Great contest by the way!
 » 4 years ago, # |   0 I like this round. Problems are so interesting!I hope my rating will be increased.
 » 4 years ago, # |   0 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 :>
•  » » 4 years ago, # ^ |   0 Do you print the whole string? Do you print any question marks?
•  » » » 4 years ago, # ^ |   0 I change ? mark to alphabet.i passed till pretest 5, but i can't pass pretest 6.
•  » » » » 4 years ago, # ^ |   0 You only replace the ?s in the substring. You need to replace every ? in the input.
•  » » » » » 4 years ago, # ^ |   0 OMG....... I don't understand about that....hmm.. I think that what I need to do is studying english....I can't understand problem well T-T so, when I submit wrong problem, I am confused that this problem is from my terrible progmramming skill or from my horrible english skill(...)thanks for your kind help! I realized what is wrong, and because of your help, I will sleep well today!
 » 4 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   -26 plz don't open round more or I'll hate you
•  » » 4 years ago, # ^ |   0 Why did you dislike this round?
•  » » » 4 years ago, # ^ |   0 Just... for me... so hard. :(
 » 4 years ago, # |   0 20709423 This is the submission for Div 2 B Can anyone tell me why this one fails on PRETEST 6
•  » » 4 years ago, # ^ |   0 Thaks you very much!
•  » » 4 years ago, # ^ |   0 Because replace all the question marks with uppercase letters
 » 4 years ago, # | ← Rev. 2 →   +16 I 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(n 2 + nm) solution (or something like that), but I came up with an one!
•  » » 4 years ago, # ^ |   0 could you explain your solution please
•  » » » 4 years ago, # ^ | ← Rev. 5 →   +20 I think you can understand the whole solution by just looking at my submission! 20704461A 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: if(isErased[e] && dist[v] + w[e] < d[u] + need) w[e] = d[u] + need - dist[v]; 
 » 4 years ago, # | ← Rev. 2 →   +16 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.
•  » » 4 years ago, # ^ |   0 I agree. Div 2C was a beautiful problem.
 » 4 years ago, # |   0 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
 » 4 years ago, # |   0 Maybe many-people thought "What the hell B pretest 6?"
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
 » 4 years ago, # |   +6 Problem Div 2D. Is it true that we have to find shortest path that contain the least amount of erased edge?
•  » » 4 years ago, # ^ |   0 That' s for sure. This can effect the result a little bit.
•  » » 4 years ago, # ^ |   0 I tried such approach... But got WA on pretest 4... Maybe i made a mistake...
•  » » 4 years ago, # ^ |   0 Yes, otherwise L might be less than the number of erased edges on the chosen path, and you'll be printing NO.
 » 4 years ago, # |   0 Please help!!! I dont know whats wrong with those B->http://codeforces.com/contest/716/submission/20707069 C->http://codeforces.com/contest/716/submission/20710823Its more likely that I am wrong in C..... I understand the editorial but I dont know whats wrong with mine
•  » » 4 years ago, # ^ |   0 Same here dude! :( ! I still have no clue why my submissions are wrong despite implementing the same methods
•  » » » 4 years ago, # ^ |   0 I had same problem and i figured out after i combined 2nd sample test and 1st one and i got -1 which was wrong.The reason of that was because when i was going trough a 25 substring and changing the '?' marks i forgot to re do them after i move on next substring.I beelive this is your mistake aswell. UPD:I just tried your solution and it gives WA if i combine 2nd and 1st sample test.Cheers
 » 4 years ago, # | ← Rev. 6 →   +10 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
•  » » 4 years ago, # ^ |   0 The great evil plan of choosing all M as prime in all pretests. >=]
 » 4 years ago, # |   -8 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?
•  » » 4 years ago, # ^ |   +3 After assigning you should check if the path you got at the beginning is still the shortest one after you removed all the zeroes.
•  » » » 4 years ago, # ^ |   0 Thanks :)
•  » » » 4 years ago, # ^ |   -8 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.
 » 4 years ago, # |   +1 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.
•  » » 4 years ago, # ^ |   0 Indeed both uses the two pointer technique, but this time is more about how to assign the letters I believe.
•  » » 4 years ago, # ^ |   0 I think the algorithm is called sliding window and I have a lot of fun solving these problems :D
•  » » 4 years ago, # ^ |   0 how? whas there any '?' letter? can you show me your code for 701C?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -9 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.
•  » » » » 4 years ago, # ^ |   0 WOW
 » 4 years ago, # |   +4 I was printing only 26 letters for Div2B. OMG.
•  » » 4 years ago, # ^ |   +4 You aren't the only one ;)
•  » » 4 years ago, # ^ |   0 I didnt only print 26 but I got WA in pretest 6 too.... What ????????????????????????????????? http://codeforces.com/contest/716/submission/20707069
•  » » » 4 years ago, # ^ |   0 Please check if your solution ever outputs any question marks. It shouldn't.
 » 4 years ago, # |   +29 Div 1B RIP.
 » 4 years ago, # | ← Rev. 2 →   -27 .
•  » » 4 years ago, # ^ |   +1 It's not a thing to be proud of.
•  » » » 4 years ago, # ^ |   0 I know that but i want to explain that the system test is weak
 » 4 years ago, # |   0 RIP B :( div1 & div2
 » 4 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   +5 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
 » 4 years ago, # | ← Rev. 3 →   +3 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?
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 YES 1 3 13 2 3 0 <-
•  » » » 4 years ago, # ^ |   0 Oops! Thanks. This was silly.
 » 4 years ago, # |   +1 Very Very Very bad round for me! Back to Earth Again After flying high last time out
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 lol, -89 is not that bad, I got -122 once.
•  » » 4 years ago, # ^ |   +1 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 ;(
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 4 years ago, # |   -6 Eagerly waiting for editorial
•  » » 4 years ago, # ^ |   +22 Editorial is already out.
 » 4 years ago, # | ← Rev. 3 →   0 Nice Contest btw
 » 4 years ago, # |   0 Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).
 » 4 years ago, # |   +1 Finally became blue for the first time today :) :D
•  » » 4 years ago, # ^ |   0 Unfortunately became blue for the first time in over half a year :( D:
 » 4 years ago, # |   0 What in 22 test in div1 B?
 » 4 years ago, # |   0 What is correct answer for test case #44 for problem B. Is it -1.
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   +1 I liked the prerequisites section for each problem in the editorial, that is very helpful. Hope that next editorials will have this section.
 » 4 years ago, # |   0 How to get full test of any problem in problemsets? Not just the first few numbers.
 » 4 years ago, # | ← Rev. 4 →   +13 LOL worse did this contest and got +644. Does this set a record? :D
•  » » 4 years ago, # ^ |   +10 Yeeeaaaahhh!!11!Must notify, that my previous round was much more better, and that time i got only +319.
 » 4 years ago, # |   0 In div2 B pretest 6, http://codeforces.com/contest/716/submission/20710802Seriously,is that a bug?
•  » » 4 years ago, # ^ |   0 Your solution outputted the string: ABABABBABDEFGHIMNOPQRABABABABATUVWXYAAAAAABABABABAAAAAAAAAAKLCSJBAAAAAAAAAZ, which obviously does not contain a valid substring.
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 You need to have A-Z in consecutive 26 positions! Its a substring and not a subsequence
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 There are more than 26 character,haha
 » 4 years ago, # |   0 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
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   0 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://codeforces.com/contest/716/submission/20716292
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You are printing a "?" at the end of the correct string! Recheck it :) Specially the print statementsI tried it using G++ and i got the correct answer ! No idea why CF prints an additional ? :(
•  » » » 4 years ago, # ^ |   0 how is it possible that ideone shows a different answer and Cf shows other ... check both the links please , and i recheckd with pen and paper , its working coorectly , Please explain if u find the error. Thanks for reply
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Size of ans should be at least 27, and ans[26] = 0.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 It worked . But why is it so ? Could you please explain ? Why do g++ compiler shows correct answer while Cf compiler doesnt??
•  » » » » 4 years ago, # ^ |   0 Compiler is allowed to do anything with invalid program including sometimes producing expected output. Read this.
•  » » » » » 4 years ago, # ^ |   0 thanks for reply :-) It was helpful .
 » 4 years ago, # |   +1 Great Contest It Was... Thanks To ZS-the-Coder !!! Waiting for your next one ...
 » 4 years ago, # |   +20 Div. 2 B solution with using regexes 20716509, Perl.
 » 4 years ago, # |   -10 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.
•  » » 4 years ago, # ^ |   +10 Consider this test: 4 4 5 0 3 0 1 0 1 3 0 1 2 2 2 3 1 After changing zeros to ones you get the shortest path from 0 to 3: 0-1-3Its 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.
•  » » » 4 years ago, # ^ |   0 I figured out after minutes why I was wrong :)).You are right.Thanks for helping :)
 » 4 years ago, # |   0 For Div2C, I'm getting some weird issues with submitting my Java answer. The output seems to match exactly, but for some reason I am getting rejected:http://codeforces.com/contest/716/submission/20721580I noticed most people have a BigInteger type as an answer, but I've seen long answers as well. For example:http://codeforces.com/contest/716/submission/20704524produces the same output as my program. Any ideas as to why my solution is getting rejected?
 » 4 years ago, # | ← Rev. 2 →   0 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://codeforces.com/contest/716/submission/20693471 My ac code: http://codeforces.com/contest/716/submission/20713665 Please help me out. Thanks in advance!
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 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;}
•  » » » 4 years ago, # ^ |   0 okay i got your point but in that case when i store it in a variable of int type ,why does it gives the correct answer? Is it because of type casting?
 » 4 years ago, # |   +1 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?
 » 4 years ago, # | ← Rev. 2 →   -21 hello
 » 12 days ago, # | ← Rev. 2 →   0 I know I shouldn't be asking this kind of question, butcan 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