Snezhok's blog

By Snezhok, 5 years ago, translation,

Hello everybody!

Congratulations to the platform Codeforces with an Anniversary 450th round!

We are glad to report that Codeforces Round #450 (Div.2) takes place on December 11 19:05 MSK. The round will be rated for Div.2 participants. Traditionally, we invite Div.1 participants to join out of competition. I hope stronger participants also will find interesting problems for themselves:)

The problems are created by me and Nikita slelaron Kostlivcev. We want to show our great appreciation to Nikolay KAN Kalinin for round coordination, mike_live and Arpa for testing the problems and of course Mike MikeMirzayanov Mirzayanov for great platforms Codeforces and Polygon.

You will have 5 problems to solve in 2 hours.

Scoring as usual: 500 — 1000 — 1500 — 2000 — 2500.

Good luck to all and enjoy the problems!

UPD: Contest is finished! I hope you enjoyed the round:)

UPD: Editorial. The problem E will be posted soon.

UPD: The problem E was posted.

Congratulations to the winners!!!

Div 1

Div 2

• +269

 » 5 years ago, # |   0 Jubilee for codeforces, the first for me)Good luck :D
•  » » 5 years ago, # ^ |   -20 What's Jubilee?
•  » » » 5 years ago, # ^ |   +16 Anniversary round.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +23 Thanks. Changed in the post.
 » 5 years ago, # |   +36 5 div2 contests and 1 div1 in 9 days? already best december gift
 » 5 years ago, # |   +42 is it semi-rated ?
•  » » 5 years ago, # ^ |   +72 Actually that's interesting point. You can generalize it a little bit. I saw previously some comments whether it would be 0,25 rated, 0,1123 rated, etc. I would go even further. For example it could be 2 rated, which means that rating change would be doubled. It could even be -1 rated, which means the better you do, the worse rating gain.It could be an x rated round with x being a real number. We could also count the expected value of rating ratio. I think currently it might be something around 0,75-0,8 rated round.
•  » » » 5 years ago, # ^ |   +61 What if we add complex numbers too, so a contest can be z-rated. Therefore we’ll need to add another dimension to the rating graph.
•  » » » » 5 years ago, # ^ |   +122
•  » » » » » 5 years ago, # ^ |   +28 And now there are even more possibilities by adding the "Educational" prefix to the previous ones.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +48 Is there exists a real number such that it is x-rated?
•  » » » » 5 years ago, # ^ |   +6 +18
•  » » » 5 years ago, # ^ |   +21 And the fun part begins when participants can choose the value of x before the round. So its like a gamble you take before seeing the problem. Could be a fun little thing to do in codeforces.
•  » » » » 5 years ago, # ^ |   +3 But you can still look at the authors. :P
•  » » » 5 years ago, # ^ |   0 The setter must have seen all these values in the comments and hence comes div2 B.
 » 5 years ago, # |   +27 he did not say "the scoring will be announced shortly before the start of the contest." This is a miracle xD
 » 5 years ago, # |   -6 Five contest in ten day
•  » » 5 years ago, # ^ |   +7 NANI!
 » 5 years ago, # |   -8 Guys, knowledge that cins/couts are very slow on big inputs/outputs is important on contests, and in this task this was one of the problems
 » 5 years ago, # | ← Rev. 2 →   +16 Typical Div 1 users: "I will just create a new account participate with it. So I can ruin other Div2 users."
•  » » 5 years ago, # ^ |   +10 Why would we do that? My skills have regressed so much that I can't even clear a div2 round ... (*sobbs in a corner)
 » 5 years ago, # | ← Rev. 2 →   +91 5 contests in 9 days Indians be like:![ ]()
•  » » 5 years ago, # ^ |   +19 Google translate has left me even more confused"Bro if someone will choke me and chill, lots of fun will do the code for fores"
•  » » » 5 years ago, # ^ |   +14 It means that if someone will tell me to chill and have fun then I will do Codeforces Rounds!
 » 5 years ago, # |   +22 Been looking at red username for so long I thought Anniversary was a person
•  » » 5 years ago, # ^ |   +28 i am, although not red yet :(
•  » » » 5 years ago, # ^ |   +5 Anniversary hmm...
•  » » » » 5 years ago, # ^ |   +3 Too bad the account was made 13 hours after the blog.
•  » » 5 years ago, # ^ |   +8 I only realized it wasn't a person when I clicked it.
 » 5 years ago, # |   +21
 » 5 years ago, # | ← Rev. 2 →   +1 Deleted
 » 5 years ago, # |   0 Hope you make progress and show yourselves!
 » 5 years ago, # |   +1 For God's shake resolve servers' issues before the contest!
 » 5 years ago, # |   +2 3 rated contests in a week, week of the FINAL EXAMS for God's sake...
•  » » 5 years ago, # ^ |   0 Meanwhile in China we have the ICPC East Continent Final in the upcoming weekned, failing final exams here I coooommmmmeeeeee
•  » » » 5 years ago, # ^ |   0 add oil la
 » 5 years ago, # | ← Rev. 3 →   -26 Before the contest : The contest is rated.During the contest : we are sorry for the long queue.After the contest : The contest is going to be unrated because of technical issues.short sad story
 » 5 years ago, # |   0 It's to late for Chinese coders. I can only participate the next one. 555
 » 5 years ago, # | ← Rev. 2 →   +7 Why the frequency of div1 contests so low? We want more div1 contests.
•  » » 5 years ago, # ^ |   -29 Because div2 users> div1 users.
•  » » 5 years ago, # ^ |   +3 it is hard to create hard div1D-div1F problems so just relax
•  » » 5 years ago, # ^ |   -13 More difficult to think up div1 questions presumably
 » 5 years ago, # |   0 gud luck to all :>
 » 5 years ago, # |   +32 May God bless the servers !
•  » » 5 years ago, # ^ |   -42 May God bless you too !! Hope so you will not become newbie as you seem again. I would suggest work on the problems rather than just complaining. Also in case of server doesn't work well it will anyway don't affect your performance because you are still not capable of solving even C problem in any contest :D
•  » » » 5 years ago, # ^ |   0 Trying to get upvotes lol -7 contribution xD
•  » » » » 5 years ago, # ^ |   -32 I said the truth. Why are you defending her? Is she is your sister or girlfriend? I wrote the truth because I usually got annoyed when someone who is not at all good in cp and just keeps on complaining about Codeforces which I personally feel is the best competitive programming site in the world.
•  » » » » » 5 years ago, # ^ |   +4 maybe after writing this she became my girlfriend lol
•  » » » » » 5 years ago, # ^ |   +10 Servers affect everyone, sometimes people will end up being higher than they would have if there was no server issue, and sometimes they will end up lower. Whether or not you are good does not change the randomness that affects you with server issues. You can be "bad" and still place lower than you should have.Moral of the story: Codeforces is a good competitive programming site but you're a douche.
•  » » » » » » 5 years ago, # ^ |   -28 I m sorry if the truth hurts you as well !! Isn't better instead of finding mistakes like pragya_123 stupid girl is doing we should suggest how to improve the Codeforces and make mike and other Codeforces team motivated so that more learning can take place.
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 [deleted]
•  » » » » » » » 5 years ago, # ^ |   +10 Nothing is perfect in this world! Yes, I'm not able to solve C problem. But, it was my general comment for all the coders who suffers sometimes due to slow server! If I'm trying to improve myself, so should codeforces too so that everyone can perform efficiently during contest!
•  » » » » » » » » 5 years ago, # ^ |   -13 Ohh really you are trying to improve yourself but i m sorry your graph shows the opposite. After 14 months you are a pupil and you say you are improving :( Anyways don't you get you are not made for competitive programming after so many failures you have? Rather you should try modelling or reporting who keeps on complaining.
•  » » » » » » » » » 5 years ago, # ^ |   +3 Lets not pass personal comments
•  » » » » » » » » » 5 years ago, # ^ |   0 It seems she hired you as an advocate because she doesn't have her own mouth.How much she paid you btw? I pay her more when se comes to my house :D
•  » » » » » » » » » 5 years ago, # ^ |   0 Maybe you are not worth replying. So, peace off from my side, too.
•  » » » » » » » » » 5 years ago, # ^ |   0 First learn how to write in english peace off My God you are seriously a illterate person. FYI its piss off not peace off.I can't able to control my laughter ROFL.
•  » » » » » » » » » 5 years ago, # ^ |   0 1 pupil defending another pupil really fascinating to watch!!
•  » » » » » » » » » 5 years ago, # ^ |   0 You are hilarious. Yes, piss off can be used for you, as you suggested. But here's what peace off means : https://www.urbandictionary.com/define.php?term=Peace%20offSee, you just proved how literate you are :)
•  » » » » » » » » » 5 years ago, # ^ |   0 Seriously, man. Peace out. I've got much important work to do.
•  » » » » » » » » » 5 years ago, # ^ |   0 Yes i completely forgot that you have to clean my shit...so sorry carry on. Also clean the bathrooms as well.
•  » » 5 years ago, # ^ |   0 First, have a look at your last 6 contest performance just 1 problem solved? Still, will you blame the Codeforces server?
 » 5 years ago, # |   +20 KAN+Anniversary=Kanniversary
 » 5 years ago, # | ← Rev. 3 →   +30 Just In case what we all expect happens =)
•  » » 5 years ago, # ^ |   +13 Reminds me of Lucy
 » 5 years ago, # |   +14 Hello darkness my old friend..
 » 5 years ago, # |   -27 Very long queue
 » 5 years ago, # |   -12 I dedicate my success in today's round to my two senpais: RedFlea and nibabin! Btw I hope nibabin didn't cheat today!
 » 5 years ago, # |   -6 What the... video
 » 5 years ago, # |   +36 There is one thing i have to say: You guys have made the BEST round ever! Your statements are the BEST!
 » 5 years ago, # |   -12 OMG D is so easy!! I wish I didn't waste my time attempting to hack. :(
•  » » 5 years ago, # ^ |   -11 Okay, maybe not as easy as I thought. we can't just do "distribute k sweets among i students" because we also need to make sure gcd doesn't become some multiple of x.
 » 5 years ago, # |   +3 What is test 3 in C?
•  » » 5 years ago, # ^ |   0 Try 4 1 3 4 2 
•  » » 5 years ago, # ^ |   0 Test cases in C : 62 3 4 1 5 661 3 2 4 5 622 1
•  » » 5 years ago, # ^ |   0 Probably: 2 2 1 Not sure though, ans = 1
•  » » » 5 years ago, # ^ |   0 Ahh, thanks :)
•  » » » 5 years ago, # ^ |   0 My solution failed on third test too, but it gives a correct answer to your test.
 » 5 years ago, # |   +13 write brute force find sequence google it find sequence on OEIS with formulae == DIV2 D
•  » » 5 years ago, # ^ |   0 Link?
•  » » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 doesn't to_string() works on codeforces ??
•  » » » 5 years ago, # ^ |   0 if for B you will get precision error, i think to_string() works on cf
 » 5 years ago, # |   0 Is the answer to question D-Unusual Sequences simply 2^(floor(y/x)-1)-1??
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   0 How do I use this?
•  » » » » 5 years ago, # ^ |   +1 There is code on python below ("Prog")
•  » » 5 years ago, # ^ |   0 I tried the same thing but I got WA
 » 5 years ago, # | ← Rev. 2 →   +8 Really cool problemset. Hope more like it are coming!
•  » » 5 years ago, # ^ |   0 Is it possible to have 1 test everday ??
 » 5 years ago, # | ← Rev. 2 →   +3 How to do D? Got it down to finding all sequences of numbers that sum to y/x with gcd 1.
•  » » 5 years ago, # ^ |   0 Yeah, even I got it that far then I didn't know how to proceed
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 DIV2 D https://ideone.com/PvYJio This is the link to my DP code. Just got 1 minute late in the contest.The DP code itself is self-explanatory.
•  » » » 5 years ago, # ^ |   0 I'm not sure I understand lines 105 to 115. How do I show that the number of sequences summing to x with gcd != 1 is the sum of solve(i) for each divisor i of x?
•  » » » » 5 years ago, # ^ |   0 Exactly what Alei said.
•  » » » » 5 years ago, # ^ |   0 For finding number of sequences summing to x with gcd != 1: You can substract sum of solve(i) { Sum of number of sequences summing to x with gcd = n/i where i is a divisor of x } from power(2,x-1) { Total number of sequences summing to x }
•  » » » 5 years ago, # ^ |   0 Time complexity of your solution?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +26 Inclusion-exclusion: add the number of ways when the numbers are multiple of g. remove the ways when the numbers are multiple of g multiplied by a prime add the ways when the numbers are multiple of g multiplied by two distinct primes ... and so on
 » 5 years ago, # |   0 What is the idea behind B & C ? :(
•  » » 5 years ago, # ^ |   -8 B: Java BigDecimal with "a lot" of extra decimal places, then just string.indexOf(c). That pass the system pretests.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0
•  » » » » 5 years ago, # ^ |   0 I said pretests.
•  » » 5 years ago, # ^ |   +4 For B, you could actually code it like you'd do long division in real life. Store the digits of the quotient in a vector. Whenever an intermediate dividend is attained twice, break the loop, possibly using a set. Then just check if c exists in the vector. If it does, just print the position(1-indexed) and if it doesn't print -1.
•  » » 5 years ago, # ^ |   0 For C maintain a map/dictionary/hashset with int, bool with values for if the number is a record before removing any number. Then take max(p[0], p[1) as maxsofar and the other as secondmax. Now iterate through all numbers. If they are bigger than the secondmax then that means you only need to remove the maxsofar element to make that element a record. Store the frequencies of what number must be removed in a map. Then just check the max value of frequency and in case of a clash, the minimum of the two. You'll also need to subtract one of the frequency for a particular element if it was previously a record because in removing that number you'll also reducing a pre-existing record.
 » 5 years ago, # |   +21 The problems and the statements were excellent. Although to me E seemed a bit easier than usual.Good job :)
 » 5 years ago, # |   +16 You can find D here https://oeis.org/A000740 Is it okay?
•  » » 5 years ago, # ^ |   -6 Yes
 » 5 years ago, # | ← Rev. 2 →   +1 Can anyone explain how to solve problem C?
•  » » 5 years ago, # ^ |   0 How much time did you have when you reached C ?
•  » » 5 years ago, # ^ |   +3 sorry my poor englishh, you can compute current records, if i'th element less than only one element on previous all elements, you can push vector > these elements, first is p[i], second is only one element that (p[i] < p[j] && j < i) p[j], if i'th element equal this vector's second element current_ans + number of vector's elements (v[i].second == p[i]) then, if i'th element also record element current_ans — 1, you can finish this problem.
•  » » » 5 years ago, # ^ |   0 Is the first element considered as record?
•  » » » » 5 years ago, # ^ |   0 yes
•  » » » » 5 years ago, # ^ |   0 Yes, since there is no "j" such that 1 <= j < 1. Anyways, even if you consider it to not be a record that won't change the answer as removing no element will change its status(whether it is a record or not).
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 A somewhat different(maybe) approach:For each element find number of elements less than it and before it in the permutation. Get all elements such that there is exactly one element before it that violates the condition of this element being a record. Say we store them in c Now for each element find all elements greater than it c. Observe that we can get number of records in O(1) for each element being dropped.Note: All of the above computation can be easily done by a merge sort tree
 » 5 years ago, # |   +2 thanks for very short conditions))
 » 5 years ago, # |   -21
•  » » 5 years ago, # ^ |   0 semi rated meaning ? sorry I am new !
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 for division one ranking is not taken into account
•  » » » 5 years ago, # ^ |   -15 It's only rated for Div.2 users
 » 5 years ago, # |   +6 This was the best codeforces contest so far.
 » 5 years ago, # |   -21 In my opinion problem B,C,D,E were from almost same difficulty level. So the order one attempts the problems matters a lot in the standings. This is certainly not good for the contest.
•  » » 5 years ago, # ^ |   -16 In my opinion problem B,C,D,E were from almost same difficulty level.Please tell me it is joke.
•  » » » 5 years ago, # ^ |   0 When did you reach on problem C , I mean what was the time ?
•  » » » » 5 years ago, # ^ |   0 What do you mean? B was easy problem, but I stuck on it, so I read C and googled solution of B (fortunately, found). C was quite standard problem, it was easy to get idea fast.
•  » » » » » 5 years ago, # ^ |   0 I meant TIME , no problem if you didn't understood .
•  » » » » » 5 years ago, # ^ |   +4 What's the point of googling the answers though
•  » » » » 5 years ago, # ^ |   0 you can see standing on this round
•  » » 5 years ago, # ^ |   0 if you tell me about it during contest, i would solve D, E.
 » 5 years ago, # |   0 Problem E can be solved with FFT?
•  » » 5 years ago, # ^ |   +11 yes with fft we can find from what all positions there is a possibility of t being there. the idea is for finding at pos i we need ((s[i+j]-t[j])^2)*(s[i+j]) summation over j from 0 to m-1 to be equal to zero assuming value for character '?' to be zero and rest some positive value. This we can find for all i using convolutions(which can be solved by fft).NOTE: We are not using any special knowledge about t here.
•  » » » 5 years ago, # ^ |   +22 E can be solved without FFT, bcs of t="abababa..."we need FFT when t is arbitrary string
•  » » 5 years ago, # ^ | ← Rev. 2 →   -18 Yes, the idea was finding the number of wildcard matching in strings, which can easily be solved using FFT. I was trying the same, fell short of time. After this was a simple DP solution.For fft, technique try to find the following sum, . The places, it is 0 are the places where the string T can match string S, from position i. Expand the expression, which is simply prefix sums and one convulution using FFT. Using FFT in this problem, we can do it for general strings as DP is independent of it. This is actually what is explained in above comments too.
•  » » 5 years ago, # ^ |   +8 http://codeforces.com/blog/entry/49613?#comment-335977 this can be used to solve it for any pattern (not limited to "ababababa...")
 » 5 years ago, # |   0
•  » » 5 years ago, # ^ |   +1 Nice background for coding :P
 » 5 years ago, # | ← Rev. 3 →   0 In problem D, I forgot that the answer is 1 but no 0 when x=y...sad story:(
•  » » 5 years ago, # ^ |   0 is that corner case?, if yes too sad
•  » » » 5 years ago, # ^ |   0 My friend and I always wrong answer on test 3... And when x=y our answers are same to 0 :(
•  » » » 5 years ago, # ^ |   0 it is not corner case.
 » 5 years ago, # |   -7 system testing too slow :(
 » 5 years ago, # |   0 How many iterations do we need to prove our "-1" answer in B? I did 1e5, it passed final testing, but I saw div. 1 users did more, just for precautions?
•  » » 5 years ago, # ^ |   +21 I couldn't find any answer greater than 50. You can prove a bound O(B) using the pidgeonhole principle on the number of steps until finding a cycle.
 » 5 years ago, # |   0 Nice problems! Thanks!
 » 5 years ago, # |   0 nice problems, can't wait the editorial. short statements <3 ++respect
 » 5 years ago, # | ← Rev. 4 →   -8 Update: I'm sorry for such a comment. I understood.LOL problem setter,poor test case on problem "B"-div-2.if input is 22 4 5answer should be 1.but I have found -1 from many accpeted code.How how how????????????
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 And why should the answer be 1 and not -1 can you please explain?4/22 is a repeating fraction and 5 never comes in the sequence. Please have a look once before posting
•  » » » 5 years ago, # ^ |   0 sry.input 22 4 5I have found -1 from many accepted code
•  » » » » 5 years ago, # ^ |   +4 Read the constraints.a
•  » » » » » 5 years ago, # ^ |   0 uffffffffffffffffff... I got it.. Sorry for the comment......
•  » » 5 years ago, # ^ |   +3 Ummm.. Answer is definitely -14/22 = 0.(18)5 cannot be found.
•  » » » 5 years ago, # ^ |   0 sry, 22 4 5 input
•  » » » » 5 years ago, # ^ |   +1 Because they guarantee a < b
•  » » » » » 5 years ago, # ^ |   +4 uffffffffffffffffff...I got it..Sorry for the comment......
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 They've stated a < b. Read the statement before making a comment about setters.
•  » » » » » 5 years ago, # ^ |   0 uffffffffffffffffff... I got it.. Sorry for the comment......
 » 5 years ago, # |   +1 tests of problem C were weak some incorrect solutions passed system tests. For example simple test 2 2 1
•  » » 5 years ago, # ^ |   0 There was no repeating numbers in the sequence, so your example is invalid.
•  » » » 5 years ago, # ^ |   0 2 2 1 
•  » » 5 years ago, # ^ |   0 From the statements: a < b.
•  » » » 5 years ago, # ^ |   +3 Hey mike, talking about problem C
•  » » 5 years ago, # ^ |   +3 If n <= 2 output is always 1
 » 5 years ago, # |   +2 How to solve C?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 You basically keep current maximum and second maximum on the array as you iterate. Removing maximum element will add record if(a[i] > maximum2 && a[i] < maximum). The rest is easy from here.
•  » » » 5 years ago, # ^ |   0 Could you please clarify a bit more. I had thought something like this during the contest but my doubt is this.Suppose we have 1 2 5 4 3 Now when a[i]=4 we have a[i]maximum2 so removing this should add a record. Well it does make 4 a record but how is the number of records maximized? In 1 2 5 4 3 we have two records 2,5 and in 1 2 4 3 we still have 2 records. So the number isn't really maximised is it? And since the question says that we need print the smallest number which maximises the total (which we cant in this question) shouldn't we print 3 as its the smallest but the number of records are still 2?
•  » » » » 5 years ago, # ^ |   0 In my opinion, I think it should print 3……emmm...what is Judy's answer?
•  » » » » 5 years ago, # ^ |   0 Thats why I said in my comment, you have cnt array which tells change, and you set cnt[i] to -1 if i is initialy record (not index i, but value i of course). So here you would have cnt[5] = -1. Later , cnt[5] gets increased only once, because only 4 will become record, so cnt[5] =0. Since cnt[1] = 0, solution will be 1, not 3 or 5 as you said. So we dont look who makes most new records, we only look for change in records. Thats why answer will not be 5, but 1, since cnt[1] = 0 ( it is 0 because 1 is not initial record, we only set cnt[i] to -1 if it is initial record). Hope this helped.
•  » » 5 years ago, # ^ |   0 I implemented a solution which is n log n My solutionWe will keep an array V, such that V[i]=the amount of new record numbers created if i is deleted. Then for each element Ki, we ask, is there only one number smaller than it in the range [0,i-1] if so, to that position in V we add 1 since by deleting that number we add 1 new record number (namely Ki) after, we Iterate through V again and if i was a record number we subtract 1 from V[i] since deleting would remove 1 record number.Finally we find x so that v[x] is maximum and print x
 » 5 years ago, # |   -14 i became purple for the 8th time
 » 5 years ago, # |   0 9 9 5 8 6 3 2 4 1 7for the given case how the answer be 9? here if we remove 1 then the permutation will be 9 5 8 6 3 2 4 7 and we get the maximum record which is 3 (2, 4, 7) isn't it?. then shouldn't the answer 1?
•  » » 5 years ago, # ^ |   0 No, if we remove 1 the record numbers are (9) and removing 9 they are (5,8)
•  » » » 5 years ago, # ^ |   0 that's mean the record always starts with the 1st element?
•  » » » » 5 years ago, # ^ |   0 there is no "record" to keep, being a record number is a property defined in the problem statement, read it again
 » 5 years ago, # |   0 For problem C, the pretest 3 is:54 3 5 1 2Accepted output is: 1My program gave output: 3I didn't understand why the output is 1. Probably I have misunderstood the problem.For this input, I thought that if 3 removed then there would be 2 records: 4 and 5 ( because after removal of 3 the sequence would be- 4 5 1 2, the increasing sequence is 4 5 and then 1 is less than 5,so sequence breaks here)But if 1 would be removed then there would be only one record: 4 ( because 3 is greater than 4, so the increasing sequence would break here)Where I had misunderstood? Thanks in advance.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 The sequence will be 4 3 5 2 .. 4 (larger than 3) and 5(larger than 3 and 4) are records.since 1 < 3 then the answer will be 1The problem isn't asking for the longest increasing subsequence, it's asking for the number of indices such that a[i] is larger than a[j] for all 1 <=j < i
•  » » » 5 years ago, # ^ |   0 How 4 is a record? def says 1<=j
•  » » » » 5 years ago, # ^ |   0 The first number in the sequence is always a record since it's already larger than all the previous numbers(in this case none).
•  » » » » » 5 years ago, # ^ |   +3 Thanks Understood now.
 » 5 years ago, # |   +14 Hi!In problem D, I found a correct solution that should be TLE.If I run the code in this accepted submission: http://codeforces.com/contest/900/submission/33138278 , against case "1 999999527", it lasts like 15 seconds.It really surprised me that it got Accepted.
 » 5 years ago, # |   0 Why the answer is 1 in prob. C,why not 4? 5 4 3 5 1 2
•  » » 5 years ago, # ^ |   0 Something is wrong with the input. The numbers are permutation of the first n numbers.Also in the question it was mentioned that we need to print the smallest of all the elements which when removing gives us the maximum number of records
•  » » » 5 years ago, # ^ |   0 The input is 5 4 3 5 1 2 The Prob.C says that "a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai." And if I delete number 1 , then it is "4 3 5 2", only a1...a1 is ok But if I delete number 4 , then it is "3 5 1 2",the a1...a2 is ok? If I misunderstand the meaning , please tell me ,thank you
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 The way i've interpreted the problem, which I'm not entirely sure is correct is something like this.When we have 4 3 5 1 2 there is only 1 record 5 as for only this i we have a[j]
•  » » » » » 5 years ago, # ^ |   0 Oh, thank you. Let me see your doubt...
•  » » » 5 years ago, # ^ |   0 Oh, I see ,does it mean that the a1...ak don't have to be consecutive? For example , as "4 3 5 2" I can choose a1,a3 to be a record?
 » 5 years ago, # |   0 What category of question does problem E, fall into? Can someone suggest similar problems.
•  » » 5 years ago, # ^ |   0 Dynamic Programming http://codeforces.com/problemset/tags/dp
 » 5 years ago, # |   +10 Wow..That's my first time solved all problems in div2,Thanks for writers!
 » 5 years ago, # |   0 How to solve problem C?