Codeforces Round #765 (Div. 2)

Hello, Codeforces!

We invite you to Codeforces Round #765 (Div. 2), which will take place in Wednesday, January 12, 2022 at 12:05UTC. Note the unusual contest start time. This round will be rated for all the participants whose ratings are lower than 2100.

You will have to solve 5 problems in 2 hours. One of the problems will be divided into easy and hard version. The round is based on the problems from Belarusian Regional olympiad. We kindly ask all Belarusian pupils who participated in this olympiad, to refrain from taking part in this round and discussing the problems publicly before the round ends.

Thanks to everyone who helped to prepare this contest:

• Our coordinators, KAN and isaf27 for good coordination.
• Wind_Eagle, gepardo, VEGAnn, andrew for help in preparing the round.
• programmer228, Vladik for testing the round.
• MikeMirzayanov for making nice systems Codeforces and Polygon.

The scoring distribution: 500-1000-1500-2000-(2000+1250)

Good luck to everyone!

UPD: Finally the editorial is available.

• 2 days ago, # ^ |

  thanks, you too

  • 2 days ago, # ^ |

    I laughed at this more than I should've, XD. Newbies are so cute at times.

• 2 days ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 46 hours ago, # ^ |

    Don't be too much greedy with ratings.

    • 46 hours ago, # ^ |

      Yeah sorry, I didn't mean it but just wanted to know if there was such a correction or not, it didn't feel good to go down this way. Sorry, but isn't it too harsh to get so many downvotes asking for help :(. Anyways won't do this again.

• 3 days ago, # ^ |

  Can you please also wish for green to become cyan?

  • 3 days ago, # ^ |

    OK! I wish every green become cyan!

    • 3 days ago, # ^ |

      ← Rev. 2 →  

      +33

      Can you please also wish for every cyan to become blue?)

      • 3 days ago, # ^ |

        Ok, i wish every cyan to become blue!!

        • 3 days ago, # ^ |

          and how about for every blue to become purple?

          • 44 hours ago, # ^ |

            I wish Every blue becomes grey. Every cyan becomes grey with lower rating and every green becomes grey with 386 rating .

            • 43 hours ago, # ^ |

              I wish every P_key25dec become red.

    • 3 days ago, # ^ |

      I don't want to go back to cyan!

    • 3 days ago, # ^ |

      Thanks, I join this wish.

    • 2 days ago, # ^ |

      shrek tomorrow

• 46 hours ago, # ^ |

  Don't know about greys but i was green and now became grey.

• 3 days ago, # ^ |

  I think it will have standard codeforces problems, but the ideas of the problems are based from the Belarusian Regional olympiad

  • 3 days ago, # ^ |

    Thanks for your reply.

  • 3 days ago, # ^ |

    Yes, the contest will have a usual Codeforces format. For example, on the Regional Olympiad we have partial scoring for the problems, and there will be no such thing on the round itself.

• 3 days ago, # ^ |

  THank you CODEFORCES for round with 5 problems.

• 3 days ago, # ^ |

  Good luck then :)

• 3 days ago, # ^ |

  what is the second contest?

  • 3 days ago, # ^ |

    One of Codeforces and other of Codechef

    • 2 days ago, # ^ |

      but timing is different :)

• 2 days ago, # ^ |

  good meme (hahahahaha)

• 3 days ago, # ^ |

  Also div1 pupils.

• 3 days ago, # ^ |

  it's gone, hope you're happy now :D

• 3 days ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 2 days ago, # ^ |

    The comment is hidden because of too negative feedback, click here to view it

• 2 days ago, # ^ |

  You will see on the contest whether it's easy or not :) We cannot change the problem, as it is already prepared.

  • 2 days ago, # ^ |

    Really hope it's not about bitmasks or dp

    • 2 days ago, # ^ |

      B problem rare bitmask or dp

    • 2 days ago, # ^ |

      LOL! A was bitmask.

• 2 days ago, # ^ |

  Am i the only one who read it as easy forces.

• 32 hours ago, # ^ |

  It really took me around 10 mins just to understand the statement of A....due to which this contest became the first div 2 contest in which I solved B faster than A xD

• 2 days ago, # ^ |

  Essay Forces!!

• 2 days ago, # ^ |

  I wasted 1 hour in 1st problem

• 47 hours ago, # ^ |

  I participated in olympiad, this problem there today, so it's really easy

• 2 days ago, # ^ |

  ← Rev. 2 →  

  -45

  The comment is hidden because of too negative feedback, click here to view it

  • 2 days ago, # ^ |

    Participating in contests is a form of practice.

    • 2 days ago, # ^ |

      ← Rev. 4 →  

      -40

      The comment is hidden because of too negative feedback, click here to view it

      • 2 days ago, # ^ |

        what do you mean? div2 is rated for newbies to

        • 2 days ago, # ^ |

          ← Rev. 2 →  

          -27

          The comment is hidden because of too negative feedback, click here to view it

          • 26 hours ago, # ^ |

            ← Rev. 2 →  

            +8

            You're not enough eligible to advice others, go practice yourself and gain some ratings. And about demotivation, it's your theory that you are explaining to others, maybe for others things doesn't work that way. When i lose rating i feel little happy about it coz in some other contest i'm gonna get a huga +ve delta and also for current contest which i couldn't solve, will give me something new to learn.

            • 26 hours ago, # ^ |

              ← Rev. 4 →  

              -11

              to be eligible to advice others you should have high rating? lmao. not gonna read the rest of the comment cause this part show how smart you are. edit: downvote me toxic kids for talking facts anyway my pm is open if u want tissues <3

      • 2 days ago, # ^ |

        ← Rev. 2 →  

        +13

        Losing ratings is just because you did not perform well enough during the contest and also because of some hard problems in it. That might be a motivation for you to keep practicing and getting better to solve these hard problems to gain more ratings.

        And about quitting CP just because you can't solve problems and depressed because you have lost your ratings, I think it didn't really come from ratings, but you didn't keen on CP enough.

        • 2 days ago, # ^ |

          ← Rev. 4 →  

          -12

          in this contest really bad problem statement , thats the main reason :/ hopefully in future contest not like that long essay.

          • 47 hours ago, # ^ |

            You didn't solve the problem not because of statements. Don't lie to yourself.

            We had only 45 questions in a contest, which is far less than the average. Statements were crystally clear.

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +1

  I love pretest 5 and MLE on problem C.

• 2 days ago, # ^ |

  Wish the memory limit were 512Mb.
  Tried really weird things to make my 3D dp ~476Mb solution pass (array of maps and maps of vectors, lol).

  • 47 hours ago, # ^ |

    This was made on purpose to make you write 2D DP.

    • 46 hours ago, # ^ |

      Is there a way to do it using memoization in 2D DP? I did memoization + 3D DP but couldn't optimize it to 2D DP.

      • 18 hours ago, # ^ |

        See my approach I managed the 3rd variable using loop. Here is the code 142546595 Hope this would help.

  • 47 hours ago, # ^ |

    array of maps and maps of vectors, lol

    Sounds quite complex. The intended solution uses just a 2D array, and the memory limits were adjusted for this solution.

    • 44 hours ago, # ^ |

      Really enjoyed that, being new to DP, it was fun to optimize from 3D to 2D. Great contest you guys :) Thanks!

• 2 days ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 2 days ago, # ^ |

    actually they are not more clear the story is not useful, i mean shorter statement is better

    • 46 hours ago, # ^ |

      Would it be better if we rewrote the statements as

      Given an array aa of nn ℓℓ-bit integers, find an ℓℓ-bit integer yy such that ∑i=1nd(ai,y)→min∑i=1nd(ai,y)→min, where d(x,y)d(x,y) is Hamming distance.

      I tried my best to make the rewrite above as short as possible, without omitting essential details.

  • 2 days ago, # ^ |

    ← Rev. 2 →  

    +13

    Yes, but they are more clear and contain more explanations.

    Exactly, but this applies only if statements actually contain explanations, rather than random planet's moon.

    • 47 hours ago, # ^ |

      I know that I don't hold the popular opinion here. Still, I want to show that the problem A mostly contained detailed explanations, rather than "random planet's moon". See yourself:

      Image

      As you can see, the legend part is no more than a third of the statements, while the other part is actually explanations.

      To prove my point about clearer statements further, I want to say that this contest had much smaller amount of questions than other recent rounds I helped setting. The number of questions was even ~1.5 times smaller than my old Codeforces Round from five years ago, where the number of participants was ~3 times smaller than now.

  • 2 days ago, # ^ |

    actually no

    im pretty sure short statements are easier to understand than long ones

    long statements are confusing and unclear

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +9

  That's why i solved it in 7 minutes xD

• 2 days ago, # ^ |

  Let's say when your code is dealing with A, in array (X A X X X A X). Your code will mis-calculate (A* X X X A X) with (X A X X X A*) and offer an incorrect answer 11.

• 2 days ago, # ^ |

  With a simple greedy solution (eliminate a sign which is causing the largest delay at each step), I came till pretest 8.

  • 45 hours ago, # ^ |

    Can anyone tell what is wrong in this approach? Link to my solution by this approach: https://codeforces.com/contest/1625/submission/142540240

• 47 hours ago, # ^ |

  I don't know such solutions. Use dynamic programming.

• 30 hours ago, # ^ |

  ← Rev. 8 →  

  +15

  Greedy is not feasible for problem C.

  try this test case:

  10 18 3
  0 1 3 4 6 7 9 10 11 12
  2 3 2 3 2 3 2 3 4 3

  the answer is 42, meanwhile greedy approach is likely to give 45.

  Take a look at the illustration:

  

  So use dynamic programming, I hope my submission 142583078 may help you.

• 32 hours ago, # ^ |

  ← Rev. 2 →  

  +18

  Special case: if k=0k=0, the answer is all indices from 11 to nn inclusive. Hereafter we assume k≠0k≠0.

  Partition the values aiai into groups according to the prefix of bits higher than kk's most significant bit. Observe that you can consider each such group individually, as any two values from two different groups will xor into a prefix that's greater than kk's most significant bit.

  Now in each group, we can always choose at least one member, and at most two members, because if we choose more than two, there will be two values that will xor to zero in the position of kk's most significant bit, thereby producing a value less than kk.

  To find out if we can choose two values from a group, we find the pair with the maximum xor and compare it with kk. Finding the maximum xor of two numbers in an array is a well-known problem (but you'd need to modify the algorithm on this page so that you know the indices of the pair) and can be done in O(mlogk)O(mlog⁡k), where mm is the number of values in the group. Therefore the total time taken over all groups will be O(nlogk)O(nlog⁡k).

  • 28 hours ago, # ^ |

    can u give me an example how to partition such groubs. I think in each group the xor between its elements must make the bits that greater than most significant bit in k equal to zero, right???

    • 28 hours ago, # ^ |

      Say k=5=1012k=5=1012, and a=[27,31,17,13]=[110112,111112,100012,11012]a=[27,31,17,13]=[110112,111112,100012,11012]. The first and second element would be in one group, the third element would be in another, and the fourth in yet another, according to the bits highlighted in red, which is anything above kk's most significant one-bit.

      • 27 hours ago, # ^ |

        ← Rev. 3 →  

        0

        I get it thanks a lot

      • 19 hours ago, # ^ |

        I created strings for those bits like "11", "11", "10","01" and stored them in a map so that only unique ones are stored and then printed all the unique strings' corresponding index, but it didn't work, any idea why? 142643010

        • 15 hours ago, # ^ |

          From what I can tell you are indexing by bits ≥msb≥msb rather than >msb>msb, and I don't see anything recognizable as a max-xor-find there.

          142559786 Here's my solution for reference, it's in Rust though.

  • 27 hours ago, # ^ |

    Damn, I was stuck at that "well known problem". Thanks for the clarification!

• 24 hours ago, # ^ |

  Observation is that a minimum value of ai⊕ajai⊕aj is achieved at some two adjacent numbers after sorting.

  After sorting, you can write simple dynamic programming, dpidpi — the length of the longest subsequence that ends with ii. Transitions are very simple dpi=maxdpi=max {dp[j]+1dp[j]+1}, where ai⊕aj≥kai⊕aj≥k.

  It can be optimized using trie.

  • 6 hours ago, # ^ |

    ← Rev. 2 →  

    0

    But why only ai⊕aj≥kai⊕aj≥k?

    It is possible that whatever subsequence dpjdpj is storing in has a xor value xx and x⊕ai<kx⊕ai<k.

    Does this have something related to the optimization using trie?

    • 6 hours ago, # ^ |

      It is possible that whatever subsequence. No, because of the first observation.

• 32 hours ago, # ^ |

  hey! can you please explain these lines in your submission of B

  int dist1 = val1;

  int dist2 = (n — val2);

  ans = max(ans, dist2 + dist1);

  why are you only considering dist. left to val1 and right to the val2?

  • 23 hours ago, # ^ |

    because number of elements in left of val2>no. of elements in left of val1 same for right side val1 has more so considering min from both sides hope it helps

    • 23 hours ago, # ^ |

      thanks! I misunderstood the question, my bad!

• 2 days ago, # ^ |

  my solution passed with this complexity.

• 2 days ago, # ^ |

  I have O(n2⋅k)O(n2⋅k) and I passed pretests. 50035003 should fit if you don't do expensive operations.

• 2 days ago, # ^ |

  A was easy, It was based on bits and count of which is more 0 or 1, My submission My sub

  • 2 days ago, # ^ |

    Man , I am saying Statement is way too complicated for A . BTW I have solved it

    • 2 days ago, # ^ |

      Did you get B bro, Some hint would be nice

      • 2 days ago, # ^ |

        ← Rev. 3 →  

        0

        Hey, check my solution. It's quite simple. if you don't get it DM me. I'm on codeforces for the next 2 hours.

        Edit: I can't reply to my DM because of some restrictions by codeforces. It's showing You exceeded your quota of 3 distinct recipients per hour. so, sorry guys. dukhi_insaan.

        This is a small explanation: Take every pair of equal numbers (I did this by sorting and taking i and i+1) and place them in the same position of 2 arrays (hypothetical arrays). Now assume their positions in the actual array be a and b. A number of elements that can come in an array hypothetical array on the left of our number are a-1 and on left can be at max n-b-1. hence the length of the hypothetical arrays can be a-n-b-1.

        I hope you get some idea from this.

        • 2 days ago, # ^ |

          Ok Thanks bro

          • 2 days ago, # ^ |

            Answer is 7 because 3 + (11-7) = 7. I can't answer your talk. sorry.

            • 2 days ago, # ^ |

              OK sorry, I got the problem thanks, It's clear

  • 2 days ago, # ^ |

    I read problem-A for 20 mins..... So so complicated and there are lots of new words for me.

• 2 days ago, # ^ |

  Me reading all problems after 2 hours

• 2 days ago, # ^ |

  Hint : Try to think of 3 state Dp transition and optimize space complexity

• 2 days ago, # ^ |

  dp[i][j] = minimum time to reach L from ith speedpost (this speedpost is not removed) provided you are allowed to remove j speedposts in the middle.

  • 2 days ago, # ^ |

    So.. is dp[i][j] = min (dp[i+1][j], dp[i+2][j-1], dp[i+3][j-2],... dp[i+1+j][0])? That's O(n*k*k) right?

• 2 days ago, # ^ |

  Dynamic Programming. Lets iterate over the stops only. M(i,s) = minimum time to reach ith stop. ans = min {M(n,s')} where n-k <= s' <= n.

• 2 days ago, # ^ |

  it depends on how efficient your implementation is. I'm pretty sure that my 142503668 is log2log2, and it got AC in 1.6s

• 2 days ago, # ^ |

  problem B

  • 2 days ago, # ^ |

    Problem B Was a sore spot for me got pretest 4 wrong, damn rating will drop

    • 2 days ago, # ^ |

      same bruh, even idk wht was wrong, still dont know tht testcase

  • • 2 days ago, # ^ |

      what ？

      • 2 days ago, # ^ |

        change ~~~~~ int n, t[N]; ~~~~~ into ~~~~~ int n, t[N + 1]; ~~~~~

        • 2 days ago, # ^ |

          Thank you very much ！ I tried the local compiler and passed, in spite of ignoring the boundary.

• 2 days ago, # ^ |

  bit trie

  • 2 days ago, # ^ |

    can anyone of you please tell in problem B why it is sufficient to check only two consecutive indexes?

    • 2 days ago, # ^ |

      because you can use all the elements before the previous one to be your prefix, so at any position it's always better to maximize that number.

    • 2 days ago, # ^ |

      ← Rev. 2 →  

      0

      Let's say two numbers that are equal have index l1l1 and l2l2.

      Consider l1l1<l2l2 Now we'll see what is the length of the segment, for number at position l2l2 to be at the l1l1 position in its segment, segment must start at index l2−l1l2−l1.

      As we have to maximize the length we can take the endpoint of the segment to be n−1n−1.

      Now length of the segment becomes (n−1)−(l2−l1)+1(n−1)−(l2−l1)+1. You can see that if l2l2 and l1l1 will not be nearest index of some number then answer will become worse.

      • 2 days ago, # ^ |

        Thanks to both of you

• 2 days ago, # ^ |

  ← Rev. 5 →  

  +8

  I think the below approach is correct.

  Spoiler

  • 2 days ago, # ^ |

    Thank you!

  • 2 days ago, # ^ |

    Yes you are right! After seeing your approach, I modify my code and it AC, thank you!

• 2 days ago, # ^ |

  Fuck, I don't know how I missed that :(

  I hope this is not my mistake

• 12 hours ago, # ^ |

  Maybe an interesting extension for type 1 queries is to guarantee that s[l+1…r−1]s[l+1…r−1] is an RBS.

  Spoiler

  • 11 hours ago, # ^ |

    fun fact: actually expending queries of type 1 to even not guaranteeing the deleted brackets are paired can still be reduced to the problem you said above

• 2 days ago, # ^ |

  Yes, here is my code: 142512011

  • 28 hours ago, # ^ |

    Could you please explain the approach? How does the add/remove function work for this problem?

• 2 days ago, # ^ |

  Thats one hell of a complex algorithm, no wonder I could not solve it

• 2 days ago, # ^ |

  ← Rev. 2 →  

  0

  lmao , yeah. My O(n*k^2) memoization solution is giving tle.

• 47 hours ago, # ^ |

  Exactly, I also faced the same issues. in the end, I had to write the code in C++ ( which has the same time complexity and space complexity as of python code) and it got AC.

• 2 days ago, # ^ |

  I didn't get why you want to maintain the size of map entry to 2.

  I just collected all the indices and did the max among every two consecutive indices https://codeforces.com/contest/1625/submission/142480649

  • 2 days ago, # ^ |

    yeah i did the same after my frnd told me to simply run for all, basically looping for all indices am already selecting two indices of minimum diffrence

    • 2 days ago, # ^ |

      This is the issue I guess

      Let say indices for a number are 1 3 10 11

      U will initially store 1 3 then u will ignore 10 as 3-1 < 10 -3

      But u need 10 to take 10 -11

      • 45 hours ago, # ^ |

        ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh, bruh marry me

• 2 days ago, # ^ |

  Trie is not needed if you make use of the observation that choosing elements with different msb (most significant bit) are independent and to consider which elements of the same msb should be chosen, we just need to switch off the msb and consider the subproblem recursively.

  At the last step, when the msb becomes smaller than or equal the msb of kk, we can make use of this to check whether there exist a pair of numbers whose xor exceeds kk, and if otherwise we just pick any random number.

  • 2 days ago, # ^ |

    ← Rev. 3 →  

    0

    To handle groups of elements with MSB <= k, I also used the technique in the GeeksforGeeks article you linked during the contest, but I got TLE. I even tried replacing the set<int> that they use with an efficient hashmap, but still got TLE. In order to get AC when upsolving, I realized it was faster to use a 0/1 trie to figure out what the maximum XOR of any pair of numbers is. See the maxXor function in this solution.

    • 41 hour(s) ago, # ^ |

      My submission 142523115 was able to pass in 1560ms using set<int> though.

      • 41 hour(s) ago, # ^ |

        That is very close to the time limit, so my guess is that you have lower constant factor than my solution did, since you are using printf/scanf instead of cout/cin and also you are using __builtin_clz which I didn't know about before. Thanks for sharing your solution.

• 44 hours ago, # ^ |

  Hint — you can take at most 2 elements from a group of unique elements, not 1. Think about it.

• 47 hours ago, # ^ |

  ← Rev. 3 →  

  +5

  Let dp(i,j)dp(i,j) = min time to reach didi, by removing jj signs. Assuming dn=ldn=l, the answer is minimum of dp(n,j)dp(n,j) over all j<=kj<=k.

  Recursion: Consider computing dp(i,j)dp(i,j). One candidate for dp(i,j)dp(i,j) is dp(i−1,j)+ai−1∗(di−di−1)dp(i−1,j)+ai−1∗(di−di−1). But it's possible that we removed the (i−1)(i−1)th sign, so we drove at speed ai−2ai−2 from di−2di−2 all along, so dp(i−2,j−1)+ai−2∗(di−di−2)dp(i−2,j−1)+ai−2∗(di−di−2) is another candidate. Continuing with this reasoning, and also noting that we could not have removed more than jj signs, we get the recurrence:

  dp(i,j)=minp<=jdp(i−1−p,j−p)+(di−di−1−p)∗ai−1−p)dp(i,j)=minp<=jdp(i−1−p,j−p)+(di−di−1−p)∗ai−1−p).

  Base case is of course dp(0,∗)=0dp(0,∗)=0.

  • 33 hours ago, # ^ |

    Thank you for your excellent answer

• 2 days ago, # ^ |

  Among all possible (ans, prev) in dp[i-1][j-1], there might be such pair that the ans is bigger while the prev is smaller and it is better to transition from that pair.

  • 47 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Will you please elaborate more? Will this case arise only when temp1==temp2 has been happened previously?

    • 45 hours ago, # ^ |

      ← Rev. 2 →  

      +1

      4 100 2
      0 1 5 6
      1 2 3 100

      Your dp[3][1] should be 8(5+3, removing the 2nd), because if we remove the 3rd, the ans will be 1+2*5, which is worse.

      And prev[3][1] will be 3 because the 3rd is not removed.

      But the best transition is when dp[3][1]=11 and prev[3][1]=2.

• 32 hours ago, # ^ |

  I don't think there is any greedy solution for problem C as you cannot properly make an independent greedy choice for which sign to remove. I tried a greedy approach during the contest and it failed terribly. Later realized the pitfalls of the approach.

• 41 hour(s) ago, # ^ |

  Hey! Thank you for your video, it was really helpful. Can you please explain, what did you mean by "speedforces round"? I'm not sure I understand this term.

• 2 days ago, # ^ |

  for red guys only :)

• 44 hours ago, # ^ |

  ← Rev. 3 →  

  +1

  I don't think problem setters should avoid classical problems in div2 and div3. Div 2 and 3 are "educational" contest. Although problem D uses classical idea, not everyone (especially experts and below) have seen it before, and they can learn in this contest, which is good for them to study.

  The problem is good to use if only you are not able google the problem by the statement online.

  • 44 hours ago, # ^ |

    I don't think problem setters should avoid classical problems in div2 and div3. Div 2 and 3 are "educational" contest.

    I thought Educational Codeforces rounds were created as "educational" contests, not the regular Div. 2 rounds.

    • 43 hours ago, # ^ |

      Yes, there is educational contest, although the frequency is not much. But since problem D is a master level problem (difficulty rating > 2100), I think it's OK to use it in the div 2 since red and orange users are unrated.

• 43 hours ago, # ^ |

  Hello, no, I don't realize that. When I solved this problem, I did not remember anything like that.

  Moreover, I liked this problem more than all the others I have solved in the original contest.

• 20 hours ago, # ^ |

  Can you please provide any link, to learn about this classical problem? I am unable to solve it

• 47 hours ago, # ^ |

  These are original statements from BelOI.

  • 47 hours ago, # ^ |

    To be more precise, Russian version of the statements is the original version, and English statements are just translation near to the original. Also, there was partial scoring on the olympiad, but it was removed for Codeforces to allow only full solutions.

• 46 hours ago, # ^ |

  If a=[1,99,3]a=[1,99,3] and k=2k=2, do you include 33 in your candidates? (Clearly, removing both 99 and 3 is optimal.)

• 44 hours ago, # ^ |

  ← Rev. 2 →  

  +14

  Are u okay?

• 41 hour(s) ago, # ^ |

  ← Rev. 2 →  

  0

  That's similar to my experience: I woke up at 6:30 AM (normally I wake up at 8 AM or later) on US east and after reading problem A's long statement I started feeling dizzy and then gave up.

  • 41 hour(s) ago, # ^ |

    You didn't see statements with really long legends :) The problem here is in Russian.

• 40 hours ago, # ^ |

  Solve dp problems on timus for 3 days straight prior to the contest lol, totally not me

• 30 hours ago, # ^ |

  The simple answer is that if you can't prove your greedy solution, you can't be sure it works. In this case it's reasonably easy to construct a counter-example; in other cases it's more difficult. If you can't prove greedy and you can see a DP solution, it's likely to be safer.

• 36 hours ago, # ^ |

  Yes, I solved it with convex hull after the contest.

  Code : https://codeforces.com/contest/1625/submission/142559648

  dp[i][j] is min time required to reach ith city using j road signs. So the transition is like dp[i][j] = min (m<i) dp[m][j-1] + (d[i]-d[m])*a[m]

  The transition part can be written as a line like y = dp[m][j-1]-d[m]*a[m] + d[i]*a[m]

  The slope is a[m] and the intercept is dp[m][j-1]-d[m]*a[m]. We can pass in d[i] and get the minimum using convex hull trick.

• • 33 hours ago, # ^ |

    Thanks for replying, will definitely check this out.

• 30 hours ago, # ^ |

  Just try to solve 3 problems in div 2 contest.

  After the round read the editorial and solve D and E problems.

  Keep doing this, then you can nearly always solve at least 3 problems in div2 contests.

  You can be blue even purple then.

• 29 hours ago, # ^ |

  in my experience, you need to consistently solve ABC problems div.2 in 1 hour

• 30 hours ago, # ^ |

  I tried too...not working(I think might there be one). Now I'll think of dp

• 30 hours ago, # ^ |

  ← Rev. 2 →  

  0

  About why greedy is not working on problem C, take a look at my reply: https://codeforces.com/blog/entry/98913?#comment-877347

  I hope this will help.

• 6 hours ago, # ^ |

  @variety-jones Can you please work your magic to show what goes wrong with this submission (failing on test 14). Thanks!

  • 5 hours ago, # ^ |

    So I'm a personal assistant now? XD.

    Input

    A Valid Output

    Your Output

    Comment

    • 5 hours ago, # ^ |

      Apologies if it sounded like I took you for granted. You are the savior!

      • 3 hours ago, # ^ |

        No, it didn't. Happy to help as long as someone has put in decent effort to debug the problem by themselves first.

• 23 hours ago, # ^ |

  You can see my solution:-> https://codeforces.com/contest/1625/submission/142628388 I have provided necessary comments to make it easy to understand.

• 20 hours ago, # ^ |

  ← Rev. 3 →  

  0

  Yes, but we have only Russian editorial now.

  • 6 hours ago, # ^ |

    so u are going to wait for the official English editorial instead of publishing your own?

    • 5 hours ago, # ^ |

      There is no such thing as "official English editorial" in our Regional Olympiad, so we need to translate it.

      The editorial is going to be published today (considering UTC+3). Sorry for long delay.

  • 6 hours ago, # ^ |

    sorry but it's two days after the contest and there is still no editorial.

    coue any one explain how to solve E2, please?

    • 5 hours ago, # ^ |

      We hope to publish the editorial today (i.e. before 00:00 UTC+3). Sorry for long delay.

      • 5 hours ago, # ^ |

        Thank you for your effort anyway.

        Can't wait to read the editorial

        • 71 minute(s) ago, # ^ |

          ← Rev. 2 →  

          0

          It's available now. Thanks for your patience.

• 6 hours ago, # ^ |

  Apparently all their limited time got used up in storytelling about Martians. Priorities, you see.