Wind_Eagle's blog

By Wind_Eagle, 5 weeks ago,

Choose the way, five paths there for you to find
Turn the page, the question lies between the lines...

Hello, Codeforces!

I hoped that once there will be my second round, and finally, here it is!

I am very glad to invite you to the Codeforces Round #741 (Div. 2), which will take place in Aug/26/2021 17:35 (Moscow time). This round will be rated for the participants with rating lower than 100000110100 (2100).

My thanks to:

• antontrygubO_o for rejecting problems A his great coordination of this round! Thanks!

• gepardo made a lot. There wouldn't have been this contest if he didn't help me. Thanks!

• EIK this is the person who taught me competitive programming — my Informatics teacher. Thanks!

• MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

• You for participating in this round. Thanks!

You will have 2 hours and 15 minutes for solving 6 tasks, one of which will be divided into easy and hard verions.

One of the problems will be interactive. So, it is recommended to read the ultimate guide on your favourite type of problems before the round.

I hope you will enjoy the round!

Round testers: kefaa2, BigBag, DreamingLeaf, Kuroni, programmer228, hu_tao, Vladik, bWayne, kassutta, asrinivasan007.

Score distribution: 500-1000-1250-(1250+1250)-2750-3500.

UPD: It was decided to add a sixth task to the round to balance the difficulty.

UPD2: Editorial is here!

UPD3: Congratulations to the winners!

Winners
Some other people who deserve congratulations

• +520

 » 5 weeks ago, # | ← Rev. 3 →   0 good luck every one :)
•  » » 5 weeks ago, # ^ |   +33 do you know why you got so many downvotes?
•  » » » 5 weeks ago, # ^ |   -37 Probably some people don't want his opponents to improve. And also they will downvote me.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +55 i think it's because he copied the comment of upsolving from the deltix round blog and people at cf don't like cheating or copying either in contest or in blogs:)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -6 CF comment voting is so weird and unpredictable. See?
•  » » » » 4 weeks ago, # ^ |   +95 Yes, never write comments if you aren't red
•  » » » » » 4 weeks ago, # ^ |   0 So, why did you write the comment with the advice not to write comments? :)
•  » » » » » » 4 weeks ago, # ^ |   +11 Because I want negative contribution, but I didn't make it this time :)
•  » » » » » 4 weeks ago, # ^ |   -197 And if you are red then any trash you comment will get upvotes.
•  » » » » » » 4 weeks ago, # ^ |   +60 Now I know 1-gon comment can also get downvotes.
•  » » » » » » 4 weeks ago, # ^ |   +4 Exactly, if you are not 1-gon
•  » » » » » » 4 weeks ago, # ^ |   +9 it seems the rules of getting upvotes or downvotes are continuously changing ... lol
•  » » » » » » 4 weeks ago, # ^ |   +2 hi
•  » » » » 4 weeks ago, # ^ |   0 People get downvotes when they write comments only with the purpose of getting upvotes :)
•  » » 5 weeks ago, # ^ |   +6 Please, Update Score distribution.
•  » » » 5 weeks ago, # ^ |   +33 I am not the author you should say this to Wind_Eagle
•  » » » » 4 weeks ago, # ^ |   +10 I wanted to give haha in this comment.Should codeforces introduce reactions like haha??(Asking Everyone)
 » 5 weeks ago, # |   +18 Ready for a binary problem :') SpoilerThis round will be rated for the participants with rating lower than 100000110100 (2100).
 » 5 weeks ago, # |   +17 for rejecting problems ALol.
 » 5 weeks ago, # |   +97 If I could say.."100000110100(2100) = 2100**11 + 2100**5 + 2100**4 + 2100**2 ~= 3.5e36. Now we are all rated, so yay!"
•  » » 5 weeks ago, # ^ |   +10 Hope to see you GM post this round, Best of luck :P
•  » » 4 weeks ago, # ^ |   0 Your rating graph even after refreshing 3-4 times :| PS : Not my first time seeing something like this
•  » » » 4 weeks ago, # ^ |   0 You just zoomed in on the graph.
•  » » » » 4 weeks ago, # ^ |   +2 Nope, zoomed in/out won't produce such graph. Additionally, u can see highlighted highest rating at left corner :P
•  » » » » » 4 weeks ago, # ^ |   0 Just check the timeline it is starting from jan 1970 . and Yes, zoomed in/out produce such types of graphs.
•  » » » » » » 4 weeks ago, # ^ |   +2 Give a try on another profile & show pic
•  » » » » » » » 3 weeks ago, # ^ |   0 Better luck next time!
 » 5 weeks ago, # |   +1 your last round had a problem related to Bit manipulation , i am guessing this round has one too ^_^
•  » » 5 weeks ago, # ^ |   +28 Well lots of bit manipulation is already going on in comment section.. damn they are already practicing for the problem.. BitForces
 » 5 weeks ago, # |   0 ok
 » 5 weeks ago, # |   +6 pikachu theme? sounds interesting :))
•  » » 4 weeks ago, # ^ |   -6 bad round, no pikachu theme...
 » 5 weeks ago, # | ← Rev. 2 →   0 What is full form of P.S.??
•  » » 5 weeks ago, # ^ |   +20 Post Script.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +63 Play Station of course, do not disinform people
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 I thought it was Play Safe
 » 5 weeks ago, # |   0 Nice! P.P.P.S. Very nice.
 » 5 weeks ago, # |   0 Ah! the poetic side of the author, the P.S.(Pre-Script) is noice!
 » 5 weeks ago, # |   +3 Useful Resource to watch before this round.!Best of Luck Everyone!
 » 5 weeks ago, # |   +99 So, this is a Div. 10 round where we have 10 hours to solve 101 tasks ?
•  » » 5 weeks ago, # ^ |   +38 Yes, exactly.
 » 5 weeks ago, # |   +76 Who is the VIP tester this time? The suspense is killing me.
•  » » 5 weeks ago, # ^ |   +3 I thought it is always you :)
•  » » 5 weeks ago, # ^ |   +71
•  » » 5 weeks ago, # ^ |   +5 Umm... Not you this time?
•  » » 4 weeks ago, # ^ |   0 NOTED
 » 5 weeks ago, # |   +10 this is the person who teached me competitive programming Should be taught lolReally looking forward to this round!
•  » » 5 weeks ago, # ^ |   +51 I wonder if I get negative contribution, will it balance out and give me positive delta
•  » » » 5 weeks ago, # ^ | ← Rev. 5 →   -7 Unfortunately real world is not like this
 » 5 weeks ago, # | ← Rev. 2 →   +11 Really kind of yours to thank your CP teacher EIK. Looking forward to participate in your contest!
 » 5 weeks ago, # |   +3 i guess next time is: PSPSPSPS congratulations to the winners
 » 5 weeks ago, # | ← Rev. 3 →   +3 teached taught
•  » » 5 weeks ago, # ^ |   +21 Thank you for teaching me English! You have taught me how to write the verb taught!
•  » » » 5 weeks ago, # ^ |   +39 https://codeforces.com/blog/entry/94218?#comment-832737sad violin music
•  » » » 5 weeks ago, # ^ |   +12 SPELLFORCES!!!!!
 » 5 weeks ago, # | ← Rev. 2 →   0 Everybody here talking about Wind_Eagle's typo mistake of taught ,but nobody noticing the beautiful 2 liner poem at the top right corner of blog.
•  » » 5 weeks ago, # ^ |   +21 Actually, it is not mine, just google it.
 » 5 weeks ago, # |   0 scoring?
 » 5 weeks ago, # |   0 Orz
 » 5 weeks ago, # |   0 Good luck to everyone
 » 5 weeks ago, # |   -8 Good luck to everyone, and i hope i can be cm after the contest.
 » 5 weeks ago, # |   0 Hoping to gain rating in this tournament..!
 » 5 weeks ago, # |   +18 So this round is about pikachu? Spoiler
 » 5 weeks ago, # |   0 Best wishes to all
 » 5 weeks ago, # |   0 I want to go back to green name
 » 5 weeks ago, # | ← Rev. 2 →   +2 I think it should be available and not availible. Wind_Eagle
 » 4 weeks ago, # |   +1 Hoping interactive problem to be D or E. I don't like interactive problems but still, will participate in this contest.
 » 4 weeks ago, # |   0 Just VCed your last round, problems were super cool!!, Looking forward to this round
 » 4 weeks ago, # |   +4 As a tester, you don't know if I tested or not
 » 4 weeks ago, # |   0 give the scoring distribution in binary form too along with the decimal scoring distribution Wind_Eagle
 » 4 weeks ago, # | ← Rev. 5 →   -6 D1,d2 require 1 correct soln
•  » » 4 weeks ago, # ^ |   +61 Well, you are kind of correct: tasks D1 and D2 require a correct solution.
 » 4 weeks ago, # |   0 "the ultimate guide on your favourite type of problems"(INTERACTIVE) -Not really
 » 4 weeks ago, # |   +10 Where is the announcement of the testing round I just participated in?
 » 4 weeks ago, # |   0 Any astrologer out there, Will i become blue today .....?
 » 4 weeks ago, # |   +60 Why is rating updation being done right now, in last round I went back to below 2100, but due to rating changes being updated it shows I am above 2100 right now which creates confusion whether this round will be rated for me or not ?
 » 4 weeks ago, # |   0 Can I expect a Easy A??
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Why not?Every A of CF is easy!Sometimes it looks harder but has an easy solution.Like last round's A was pretty easy.But most of us thought that bruteforce wouldnt work :(
•  » » » 4 weeks ago, # ^ |   +3 Ahh let's Be honest this time...Implementing A took me 2-3 mins but understanding A took me 20-22 mins last round!
•  » » » » 4 weeks ago, # ^ |   0 Yeah, the implementation of A just involves a few if else and for loops, but still it takes time to figure out what exactly we need to do in the question :(
»
4 weeks ago, # |
-51

When my Brute Force Solution passes all the TCs.

 » 4 weeks ago, # |   +3 By this line rating lower than 100000110100 (2100) , I think there will be good concepts of bits in the problems
 » 4 weeks ago, # |   0 Could you please provide the editorials in JAVA as well.
•  » » 4 weeks ago, # ^ |   +20 Editorials will be provided only on English and Russian, I think :)
 » 4 weeks ago, # |   0 when will the tutorial be released
•  » » 4 weeks ago, # ^ |   +10 Right after the system testing I guess.
 » 4 weeks ago, # |   0 How to solve D2?Is it somehow related to finding the K-th one in the segment tree?
•  » » 4 weeks ago, # ^ |   0 I didn't submit anything for the contest, but I think you might be able to keep the indices of positive/negative in a set, get the lower and upper bound for each query in logn, and just greedily pick from there.
•  » » 4 weeks ago, # ^ | ← Rev. 7 →   +8 Much easier :)From D1 you should already know, that answer is always $1$ for odd segments and $2$ for even, if sum inside is not equal $0$. So, firstly we will reduce problem to odd segments by taking first element of even segment to answer, for example. Then, you need to find such element, that sums before it and after in segment the same. Suppose we have query $[l, r]$ and we want to delete element $x$. In terms of prefix sums we will get $pref[r] - pref[x] = pref[x- 1] - pref[l - 1]$, that equals to $pref[x - 1] + pref[x] = pref[l - 1] + pref[r]$. And all you need — is to count $pref[x] + pref[x - 1]$ for all elements and add to some associative container such indexes, let's call it $C$. The answer- lower_bound in $C[pref[l - 1] + pref[r]]$ by $l$. 127111849
•  » » » 4 weeks ago, # ^ |   0 I did the exact same thing just that I am trying to find the element that divides the segment into two equal sums. so if for an odd segment the sum is 2*a+1. I am trying to find the element responsible for making the sum a+1. So that on the removal of that element the two segment right and left of it will have the same sum. But for some reason, I m getting wrong answer on test 2. Submission: 127143195 Can u help?
 » 4 weeks ago, # |   +4 Very balanced and cool contest! Thank you very much <3
 » 4 weeks ago, # |   +74 GuessForces
•  » » 4 weeks ago, # ^ |   0 fr
•  » » 4 weeks ago, # ^ |   0 Broo exactly!
 » 4 weeks ago, # |   +6 How to solve E?
•  » » 4 weeks ago, # ^ |   0 I can think of O(n^2 logn). But I don't think that's meant to pass.
•  » » » 4 weeks ago, # ^ |   0 My solution was O(n^2 logn logn) I guess, I got tle, what's your o(n^2 logn)?https://codeforces.com/blog/entry/94218?#comment-833236
•  » » 4 weeks ago, # ^ |   0 Wait for editorial :)
•  » » » 4 weeks ago, # ^ |   0 Wind_Eagle I generated all the substrings pairs (l, r) and sorted it using binary search + hashing in my compare function, so there is an extra log factor in the binary search, then I get the LIS, but this gets TLE, any tweaks for (binary search + hashing) idea to work or that didn't meant to pass?https://codeforces.com/contest/1562/submission/127137681
•  » » 4 weeks ago, # ^ |   0 I used suffix array with an O(N^2) dp, got the pattern when writing out the suffix array of the first sample test and try to get the result from that.
•  » » » 4 weeks ago, # ^ |   0 Actually you can precompute LCP in $O(N^2)$ with something like this:$lcp[i][j] = s[i] == s[j] ? 1 + lcp[i + 1][j + 1] : 0$That makes the code really clean.
•  » » 4 weeks ago, # ^ |   0 I tried an O(n^2) dp approach. solutionI utilised the fact that the answer for the reverse of the expansion will be the longest decreasing subsequence. By reversing the string, we can enumerate all the substrings that end at any particular character such that they are in the same order as in the original expansion. Now let dp[i] be the LDS such that we necessarily took the substring ending with char s[i].So for calculating dp[i], the answer will be at least i+1 as we can take all the substrings ending at s[i]. Now we can iterate and check if we can add all these substrings to any previous answer only if those answers are greater than all substrings ending at s[i] (as it's always best to include these substrings).SO to check two substring families ending at s[j] and s[i] (j < i), I pre-calculated g[j][i] which tells me after which length of a substring starting from j towards 0, it becomes greater than the substring family s[i] and use this value to subtract the initial substrings starting at j which are smaller than substring family s[i].Now final answer is max of all dp[i]PS:- sorry for my bad explanation.
 » 4 weeks ago, # |   0 How to solve C?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +4 Greedy .... lets say you have a string 1101 which is x (let's say) then to get a number that dividides it is simply 11010 which is 2 * x So basically all we need is a 0 to find a multiple .... let place = index of last 0 (from 1 to n) Case 1 — 0 exist in 1 to n/2 then just print from that place where 0 is to n and place+1 to n Case 2- 0 exist after n/2 then print 1 to place , 1 to place -1case 3- 0 is at n/2 ... print from n/2 to n and n/2+1 to nCase 4 — all numbers are 1 ... then print 1 to n/2 and n/2 to n or 1 to n/2 , 2 to n/2+1
•  » » » 4 weeks ago, # ^ |   0 I the case that all the numbers are 1 i took 1 to n/2 and 1 to 2*n /2 but that did not work
•  » » » » 4 weeks ago, # ^ |   0 I made a dummy mistake in the case that every thing is one , i output the interval in the wrong order.It's 1 to 2 *n/2 and 1 to n/2
•  » » » » 4 weeks ago, # ^ |   0 chika10 Can you help me in Problem C.Idk where I'm making a mistake.127118923
•  » » » 4 weeks ago, # ^ |   0 Ohhhhhhh shittt, i was so close to this solution i just didn't noticed it man damnnnnnnn. Thanks for your explanation it was crystal clear!
 » 4 weeks ago, # |   0 A bit difficult for me. Is answer for D <= 2?
•  » » 4 weeks ago, # ^ |   +13 Yes
•  » » 4 weeks ago, # ^ |   0 Problem name of this problem is a big hint to reveal the same.
 » 4 weeks ago, # |   -23 Today I'll loose my "newbie" virginity
•  » » 4 weeks ago, # ^ |   0 NOTED
 » 4 weeks ago, # |   0 Lol, guessed the solution for D1 but tried implementing with sparse tables instead of prefix sums for some reason...How to prove D?
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   +7 actually if alternative sum is 0 -> ok, if it's odd then of course there exists 1 rod which divides interval into 2 intervals with equal alternative sum(total sum / 2) so this will be the rod to be removed(and after it second sum will become: -sum and hence 0 in total). if sum is even -> just ignore first rod in current interval and sum will become odd, now do the same as above.(p.s. here it can be proved that in 1 deletions it's impossible to make things good(of course even in 0 deletions) the reason is simple: making alternative sum in 1 deletions simply means that there should be 1 rod without which the remaining sum should be split into 2 equal alternative sums which is impossible(odd isn't divisible by 2))
•  » » 4 weeks ago, # ^ |   +5 These two observations must be enough to get to a solution.Observation 1: If rod at Index i is removed,the subarray [i+1,N] gets multiplied by -1.Observation 2: If Sum is odd (of the form 2*a+1), we can find the index at which sum[ l ,i-1 ] == a && sum [ i+1, r ] == a and remove the rod at index i.
•  » » 4 weeks ago, # ^ |   +3 Observe that once you remove a character the net value of the sequence following it till the end gets multiplied by -1. Now coming to the question There are 2 cases, either the sequence length is odd or it is even Case odd: When the length of the sequence is odd then the total sign-variable sum must be odd. Now every odd number x can be written as odd = even + [+/-] + even. Now if you strategically remove the [+/-] then the net value becomes even — even = 0. Hence the answer for odd length is always 1. Case even: When the length of the sequence is even then the total sign-variable sum must be even. If the total sign-variable sum is already equal to 0, then no rods need to be removed hence answer is 0. Otherwise, we can write even = [+/-] + odd. Now to you have to remove one rod to get the net value odd and we saw that every odd value can be made 0 by Furthur removing one rod. Hence the net answer for this case becomes 2.
•  » » » 4 weeks ago, # ^ |   +4 Respect + notshivam
 » 4 weeks ago, # |   +11 In B, the highest left digits is 2 right?
•  » » 4 weeks ago, # ^ |   0 Right.
•  » » 4 weeks ago, # ^ |   +1 Yes.
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 Applied the same logic but what is wrong with this solution for B? 127124498
•  » » » » 4 weeks ago, # ^ |   0 Your code is giving wrong answer for n = 233Expected output : 2, 33 Your o/p : 1, 2
•  » » » » 4 weeks ago, # ^ |   0 for 5, you checked 52 & 55, but not 57. 57 is not a prime number, you should check that also.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Thanks,this 127132446 worked I cant believe I wasted like an hour on this.
•  » » 4 weeks ago, # ^ |   0 i got this approach when i was done with coding by taking so many cases.
 » 4 weeks ago, # | ← Rev. 2 →   0 Deleted because people hate this contest and this comment.
 » 4 weeks ago, # |   0 I think problem B is for those who want good questions on implementation.Like ME!!
 » 4 weeks ago, # |   0 Balanced an implementation heavy contest. B and C could be solved easily if you have pen, paper and time.
 » 4 weeks ago, # |   +120 Some relevant meme.
•  » » 4 weeks ago, # ^ |   +24 I've prooved all the solutions :)
•  » » » 4 weeks ago, # ^ |   0 I'd be waiting for the editorial then :D. And memes apart, themks for an amazing contest! The problems were very interesting!
 » 4 weeks ago, # |   0 D1 I only saw sample test and guess :)) then I pass pretest :V cool :)
 » 4 weeks ago, # |   +8 012Forces
 » 4 weeks ago, # |   +43 The keyword for today's contest is "answer <= 2".
 » 4 weeks ago, # |   0 how to solve C?
•  » » 4 weeks ago, # ^ |   +3 Just search for one zero For example you have 10111 then ans is 0111 111 k=1 and if the zero is after half the string like 11101 then ans is 1110 111 k=2
•  » » » 4 weeks ago, # ^ |   +1 Did the first thing but missed the second one during contest,couldn't catch the left shifting observation...I am gonna kill myself
•  » » » » 4 weeks ago, # ^ |   0 I got the second one but failed to understand the first one, and got stuck in this problem.
•  » » » » » 4 weeks ago, # ^ |   0 Why can't I see any of your submissions of the contest?
 » 4 weeks ago, # |   +16 Every other problem is casework lol. Nothing to learn from the first 4 problems.
•  » » 4 weeks ago, # ^ |   0 Finding out the cases is problem solving too, no?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Sure it is, but so are puzzles. None of these problems involved programming or designing a data structure or an algorithm I'd say. I'm not saying these problems are bad, but it's nice to have a variety in contest problems. There is so much possible with graph/tree, DP, DataStructures, geometry, string algos. So it's a little disheartening to see the first 4 problems just being ad-hoc.
•  » » » » 4 weeks ago, # ^ |   0 Task E? It involved algorithms lol.
•  » » » » » 4 weeks ago, # ^ |   +1 Yeah, I can barely make it to the 5th or 6th problem with enough time in a 2hr contest. I used to like Topcoder SRMs for this reason because one can actually get to the harder/nicer problems in time since there are only 3 problems. But i guess I'm digressing here, I'll give it a try when i find time to upsolve. Thanks.
 » 4 weeks ago, # | ← Rev. 4 →   +43 Did you changed the checker for B?Because my code passed sample in contest but failed on the same test case on sys test.Mentioning Wind_Eagle My code failed system test:And it failed on the sample case:
•  » » 4 weeks ago, # ^ |   +24 Same for me. I print the wrong length of the string. I always print 1, even when I have to print 2. The code passed pretets but failed systests. In fact, my solution should fail sample test, so it should have failed pretests as well. There's something wrong here.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +17 Yes, this is the same mistake I made. I think they changed the checker without any announcement.This is unfair.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 gepardo Wind_Eagle Could you look into the situation please? It's as though there are different checkers for pretests and systests. Both of us could easily correct out the code without even losing 50 points for the wrong submission as we fail on the sample test. I understand that it's still our mistake and we should have been more attentive. I cannot prove that I had the AC on B during the round, but do believe me. There could be more casualties.
•  » » » » » 4 weeks ago, # ^ |   +16 I have a proof. See my Submission(127073976) for B that gave runtime error on test 2, but actually prints wrong answer for test 1 as well. It was very unfortunate that they had incorrect checker for B, that made my obvious incorrect solution pass. The previous Codeforces had weak pretests for D1 and D2, that allowed my solution with integer overflow to pass but it failed on system tests. It is too sad and demotivating to lose rating continuously due to others mistakes. (ofcourse some mistake was mine as well, but in ideal cases I will consider them as other's mistake).
•  » » » » » » 4 weeks ago, # ^ |   0 same things happening to me :(A screenshot from round 738
•  » » » » 4 weeks ago, # ^ |   +5 And my code passed after fixing the size.I was about to get somewhere around +100Now its -8(;﹏;)
•  » » 4 weeks ago, # ^ |   +35 I don't know why B asks for outputing the length, it makes no sense, just annoying.
 » 4 weeks ago, # |   +66 In last Div1 round my rating decrease by over 100 so I become Canditate Master after that; but because ratings are temporarily rollbacked, and when I register the current round I noticed that I'm "out of competition". I will be rated after undoing rollback? or be unrated as my rating is temporarily still > 2100?
•  » » 4 weeks ago, # ^ |   +26 Will be rated.
•  » » » 4 weeks ago, # ^ |   +12 lmao I guess I will be unrated so I give up debuging D2 and start to write E.
•  » » 4 weeks ago, # ^ |   0 I'm also in the same situation, let's see how rating changes after the contest.
•  » » 4 weeks ago, # ^ |   -21 I can tell from your picture that you are Chinese.
 » 4 weeks ago, # |   0 How to solve D2?
 » 4 weeks ago, # |   +12 $Trickforces.$How sneaky: "such that $f(t)=f(w)⋅k.$"
•  » » 4 weeks ago, # ^ |   +13 It is to make sure you can print f(t)=f(w)=0.
 » 4 weeks ago, # | ← Rev. 2 →   0 deleted.
 » 4 weeks ago, # |   0 In C is f(t) and f(w) both are 0 allowed? that would make k become any integer.
•  » » 4 weeks ago, # ^ |   0 Yes, such case is possible, and $k$ can be any integer in this case.
•  » » » 4 weeks ago, # ^ |   0 OK, Thank you for clearing doubt
 » 4 weeks ago, # |   +45 Ad-hoc problems nowadays are getting to the next level.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -13 Deleted
 » 4 weeks ago, # | ← Rev. 2 →   0 Deleted
 » 4 weeks ago, # |   +16 SpoilerMe trying to become master for the first time.codeforces:
 » 4 weeks ago, # |   0 I am so sleepy today... especially I only sleeped for 20 mins in the afternoon;But the problems are quite challengeable.wu... it is 1:00 now,i gotta sleep;
 » 4 weeks ago, # |   0 In C, first testcase, would "2 5 3 5" be a permissible output? We have t="0111" and w="111", hence f(t)=7=f(w)=f(w)⋅1
•  » » 4 weeks ago, # ^ |   0 Yes I guess.
 » 4 weeks ago, # |   0 Solid contest
 » 4 weeks ago, # |   0 The questions were quite good.
 » 4 weeks ago, # |   0 Liked the problems.
 » 4 weeks ago, # |   0 Great questions with nice explanation of each terms used in problem statement.
 » 4 weeks ago, # |   +20 I personally like this round,because the problems require a lot of thinking,and some of them need you to process all those tricky corner cases,the difficulty is quite suitable for me. but I think the Examples in D1 "spoke too much",I guessed a solution via Examples and after checking through some queries having odd length,I submitted and got AC.I would've never guessed it if there weren't so many Examples
 » 4 weeks ago, # |   -6 Great Problems, Thanks to the authors
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -22 My contribution will suffer because of this comment. Edit: typo
 » 4 weeks ago, # | ← Rev. 2 →   0 it was really a cool contest, thanks Wind_Eagle
 » 4 weeks ago, # |   +1 Editorial?
 » 4 weeks ago, # |   +2 Is there any good website conducting contests on DS Algo?
 » 4 weeks ago, # |   0 Hello may I ask why haven't I got my ratings. Sorry guys I am a newbie.
 » 4 weeks ago, # |   0 Is problem B not accept for string is the answer?
 » 4 weeks ago, # | ← Rev. 2 →   0 In problem B, checker log says 'wrong answer Number is too big! (test case 101)'. What am i doing wrong? Can anyone help. 127129777
•  » » 4 weeks ago, # ^ |   0 You are doing way too many calculations you should have checked the string in n^2 complexity considering all pairs of two digit number after the one digit number
•  » » » 4 weeks ago, # ^ |   0 I have an O(n) idea, you see it in my submisson.
 » 4 weeks ago, # |   0 Eagerly waiting for the solutions
 » 4 weeks ago, # |   0 How to solve E?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Note that if we take some subarray, we can take all the suffix which has the prefix as this subarray. compute the prefix array for every suffix using the z algorithm, Then we do normal LIS dp. The comparison will be, let x = z[j][i] for all j < i. Then if s[i + x] > s[j+x], dp[i] = dp[j] + n-i-x+1. Take the max of all dp. SubmissionUnfortunately I din have time to implement this during contest even though I copied the code for z algorithm from geeksforgeeks.
 » 4 weeks ago, # |   0 I solved B with bitmasking. if k<=9, I checked all subsets of the string with bitmasking and chose the one that isnt prime with minimum length. Otherwise, it is guaranteed that we can obtain at least one of the following: - A 1-digit non-prime. - A 2 digit even number. - A number with 2 equal digits that doesn't equal 11. - A number with 3 equal digits. I had trouble calculating the complexity though so if anyone knows, please do tell. https://codeforces.com/contest/1562/submission/127128738
 » 4 weeks ago, # |   0 I think I will turn to an expert after two huors.
 » 4 weeks ago, # | ← Rev. 4 →   0 EDIT — Problem solved!
 » 4 weeks ago, # | ← Rev. 2 →   0 In question B , what is this issue , "Number too big!"? Did we had to perform maximum deletions? Edit:- Never Mind , Got it
•  » » 4 weeks ago, # ^ |   0 Yes we do. I got that one wrong at first too. But then I read the second line it said "what is the maximum number of digits that can be removed".
 » 4 weeks ago, # |   0 My solution 127123174 was rejected during the contest. However after the contest this submission of mine is accepted: 127130827 Now both the submissions are literally same except in line 67 and 68 where I have essentially just printed (l2, r2) before (l1, r1). I think this was allowed. Am I wrong?
•  » » 4 weeks ago, # ^ |   0 You had to print l1 r1 before l2 and r2, that was asked.Since, f(substr(l1,r1))=K*f(substr(l2,r2)), and K is an positive integer, do it was essential for the decimal representation of the substring formed by l1 and r1 to be >= decimal representation of the substring formed by l2 and r2, so you needed to print l1 and r1 before. And, it was even mentioned in the question itself For every test case print four integers l1, r1, l2, r2, which denote the beginning of the first substring, the end of the first substring, the beginning of the second substring, and the end of the second substring, respectively.
•  » » » 4 weeks ago, # ^ |   0 Yes I got it
 » 4 weeks ago, # |   +4 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 EDIT — Problem solved! (My sieve function was getting out of bounds, which caused undefined behavior, thus resulting in my code getting RTE in competition and got accepted afterwards)
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +63 Mike, will the rating after this round be applied after the rating changes in round 740 return? Or there would be a mess? I'm afraid that i won't be rated.
 » 4 weeks ago, # |   +9 Wind_Eagle Nice Dream Theater references in A&B!
•  » » 4 weeks ago, # ^ |   +1 Thanks :)My other favourite bands include Yes, Rush, Van der Graaf Generator, Pink Floyd, ELP, King Crimson, Magma, Symphony X, Fates Warning and some other progressive bands.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Sorry, misread
•  » » » » 4 weeks ago, # ^ |   0 Umgh... Where is the Rush reference in D?
•  » » » » » 4 weeks ago, # ^ |   0 I thought it was a reference to the 2112 album after seeing Dream Theater and Oldfield references.
•  » » » » » » 4 weeks ago, # ^ |   +4 Progressive Rock & Metal <3
•  » » » » » » 13 days ago, # ^ |   +1 You know what, I can understand now that the half of the contest was a bit 'Rush reference' (album 2112): at least in tasks B, C, D there were magic numbers 1 and 2 (most commonly the answer).
 » 4 weeks ago, # |   0 127118923 I don't understand why my solution for problem C is failing on pretest 2.Can anyone review my solution or at least provide some test cases.Thank You :)
 » 4 weeks ago, # | ← Rev. 6 →   0 Can somebody review this simple code for problem B? I tried brute force for 2 digits solution, if one digit composite couldn't be formed. I am unable to see failed test case in my submission. What does "Number too big" error mean? https://codeforces.com/contest/1562/submission/127124101
•  » » 4 weeks ago, # ^ |   0 In the isPrime function, it should be " i*i<=n "AC submission: https://codeforces.com/contest/1562/submission/127139793
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 Thank you!!
 » 4 weeks ago, # |   +1 How to solve D?
 » 4 weeks ago, # |   -34 Motivating everyone for competitive coding.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 Thank You So much sir It gave me goosebumps
•  » » 4 weeks ago, # ^ |   +2 Much needed content here
•  » » 4 weeks ago, # ^ |   +2 Thanks sir. Much needed motivation
•  » » 4 weeks ago, # ^ |   +2 much needed motivation thanks bro
•  » » 4 weeks ago, # ^ |   +2 Thanks buddy
•  » » 4 weeks ago, # ^ |   -7 Thanks for such motivation.
 » 4 weeks ago, # |   0 Thanks to the authors for the contest, and to Mike for codeforces.
•  » » 4 weeks ago, # ^ |   +5 Thank you for participating!
 » 4 weeks ago, # | ← Rev. 3 →   0 Hi everyone,  Just tried to solve problem B during the contest, and ended up wasting my last hour and a half trying to figure out if I was missing some edge case :P (I am a noobie still) Can someone kindly point out what I was missing? Still trying to understand.. Here's my submission: `127114107 Details: answer Number is too big! (test case 289)
•  » » 4 weeks ago, # ^ |   0 Check this case Case:13573Correct output is 57 but your code prints 573, which is too big.
•  » » » 4 weeks ago, # ^ |   +1 You are absolutely right! Thanks!! Can't believe I spent an hour and a half looking at these four numbers and didn't realize 57 wasn't a prime :p Thanks once again!
•  » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 https://codeforces.com/contest/1562/submission/127124101 Ozgur Can you please point out one failed test case in this submission too? Thank you :) UPD: I was missing "=" sign in my isPrime function
•  » » » » 4 weeks ago, # ^ |   0 Happy to hear that :)
 » 4 weeks ago, # |   0 The questions were really nice. I also appreciate the dream theater references! Wind_Eagle
 » 4 weeks ago, # | ← Rev. 2 →   +11 Apart from the tricky string questions(which are hard for me to solve), it's a very good round and i really had fun.
 » 4 weeks ago, # |   0 I think the statement for problem C was way too convoluted/complicated. So many formal, mathematical equations in the text make it really difficult to understand what is even asked. If you said it in text, in some kind of story, the statement could have been 5 times shorter. A good story helps us understand the problem, but the "Frodo and Bilbo" and "gold and silver" were just distractions, the actual task had no story, just a set of 4/5 conditions that had to be satisfied. (And the f(t)=f(w)*k condition is super weird)