Vovuh's blog

By Vovuh, history, 6 months ago, translation, In English,

Suddenly, this round will consist of 7 different problems also!

UPD2: The round will consist of 7 problems and one of them will be in easy and hard editions!

<almost-copy-pasted-part>

Hello! Codeforces Round #555 (Div. 3) will start at Apr/26/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD0: I also would like to thank my friend Adilbek adedalic Dalabaev for helping me with understanding problems difficulty and other help with round preparation!

UPD1: Big thanks to dreamoon_love_AA, Ashishgup, jeel_vaishnav and lizi_lzy for testing the round!

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 FloodBenz 8 282
2 maguihong123 7 347
3 dreagonm 7 373
4 DeathYmz 7 571
5 BaiBatyr 6 189

Congratulations to the best hackers:

Rank Competitor Hack Count
1 WileE.Coyote 448:-33
2 Disappointment 127:-20
3 wzw19991105 39
4 ismagilov.code 50:-23
5 Kucha 20:-3
919 successful hacks and 365 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A ImAlsoChildish 0:01
B BaiBatyr 0:06
C1 darshit_99 0:10
C2 Injetzk 0:16
D iamnotacoder 0:21
E BaiBatyr 0:12
F Injetzk 0:29
G Injetzk 1:15

 
 
 
 
  • Vote: I like it
  • +176
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

Vovuh get ready to surpass Petr in the contribution table

»
6 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Recovery Time of Rating. :)

»
6 months ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Nice round ID! I love it :)

»
6 months ago, # |
  Vote: I like it -14 Vote: I do not like it

Suddenly, this round will consist of 7 different problems also!

»
6 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Can explain how it is possible:

"I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table."?

I hack myself? or i submit from other accaunt and hack this submission? in this case, how to identify this?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Probably both. It is really easy to detect — cheaters will often have something like if(n==123445): print([obviously wrong number])

»
6 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Only if this was my last div 3 :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why does Vovuh mostly sets problem for Div3 and Educational Rounds only ??? P.S: I like his problems ;)

»
6 months ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

When round start me "body oh my losing all my rating"

»
6 months ago, # |
  Vote: I like it -8 Vote: I do not like it

In reference to the UPD1, what does it mean to "test a round" ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that means the testers will solve the problems of the round, and give feedback to authors if they found a bug or statement is unclear or something

»
6 months ago, # |
  Vote: I like it -7 Vote: I do not like it

What does it mean that "the penalty for the wrong submission in this round [...] is 10 minutes"? Does this mean that if I submit a program that doesn't pass test #47 then I will only have 1h 50min for the whole competition?

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Hint : With $$$x$$$ as your first number, you can construct array for all $$$n$$$ in range $$$(kx + k*(k - 1)/2, x(2^k - 1))$$$

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can first number be any integer? I took it as 1 and thought I can solve the problem with range updates easily by tracking max value of every index and what to add to reach N, but failed at TC 5. For first sample it is going like: [1,2,3,4,5,6] -> [1,2,4,5,6,7] -> [1,2,4,5,6,8]. Edit: Just saw TC 5, we can use any number as first number :)

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Interesting. It's actually not stated that $$$a_1$$$ has to be $$$1$$$. If this is the case, the solution could be much simpler.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Looks like I made problem harder during contest. Spent 1 hour to fix my solution and noticed it's extra easy when you can start with any integer. (This one wrong attempt, and this one after I understood the problem)

          • »
            »
            »
            »
            »
            »
            6 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can you please explain your approach

            • »
              »
              »
              »
              »
              »
              »
              6 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Take the example for N = 60 and K = 6, initial array is [1,2,3,4,5,6], and sum is 21. You need 39 to reach 60. int(39/6) = 6. Add this to each element [7,8,9,10,11,12]. 39 % 6 is 3 remaining value. Check if you can add that to last item (max value is 2*a[previous id]), in this example it can be 22, so it safe to make last item 15. If array was something like [1,2,3,4], and remaining was 3, you need to do same thing for last 2 item [1,2,4,6]. A quick explanation, hope it's clear :)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is 5th test case of E !? Can't find any mistake in my solution >_>

»
6 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Very Very Very nice round! interesting problems!!!!!!!!!! easy to understand! hard to solve!( for me ..)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate the part, where 12 hour phase of open hacks is written?

»
6 months ago, # |
  Vote: I like it -32 Vote: I do not like it

plz don't ask about the solution since the hack is still avaliable.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hacks in phase of hacks do not change anything

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! I am new on this platform, so didn't know about that!1

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone please confirm if my following submission has a time complexity of O(n*n) or not for E? According to me , it does. Link. Moreover, I would appreciate if someone can hack it as I am not really aware of the working of the test generator to generate such tests. Thanks !!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, it is o(n*n).try a=200000*0 b=200000*199999 , will get a tle

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hi. Thanks for replying. It got hacked but just to inform you, I think my solution will pass the test case provided by you as all the elements of input array a are same. So basically, it will only search once and in all the next iterations it'll just execute the O(1) operation. The test case over which it'll fail will be something of the type

      20000 0 1 2 3 4 ............ 19997 19998 19999 0 0 0 0 0 0 ..........0 0 0

      In this case, it will calculate the ideal mod for every entry in array a by going through every available value in b before choosing the optimal one.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

      ..

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey ! For problem C1 (https://codeforces.com/contest/1157/problem/C1) , I want to know what should be the output for these test case:

case 1 5 1 2 3 4 5

case 2 5 5 4 3 2 1

case 3 1 2

Thanks in advance

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    case 1 and 2 are invalid input for C1 since there won't be duplicates

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Those are invalid test cases for C1.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Case 3 -> 2 LR

    that's right? in case 1 and 2 are invalid for C1

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you get stuck on C1, consider cases like 3 5 7 6 2 4 1.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot.This case has just revealed a logical error in my code.

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      what is the expected answer for this test case 3 5 7 6 2 4 1?

      5
      1 3 4 5 7
      

      ?

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Case 1: Answer is 5. ( LLLLR ) or ( LLLLL )

    Case 2: Answer is 5. ( RRRRL ) or ( RRRRR )

    Case 3: Answer is 1. ( L ) or ( R )

    The cases are valid for C1, because the first number is N, so there are no duplicates.

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Any counter case where my solution fails for C2?
apparently codeforces is giving WA on TC 15, but string is of length>1000 so I can't dry run and see where it went wrong.
My submission

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    input 5 5 6 7 6 6 causes infinite loop, you don't handle well situation when A[left] = A[right]

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to know why my solution for C1 in java got TLE while the same solution in C++ got Accepted. Java version: 53356781 C++ version: 53359020

I'd also like to know why I got compile error when I used linked list of java to solve C1. It works fine on my computer. The version of my jdk is 1.8 by the way. 53350776

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Because in java String concatenation creates a new copy of the string so that the overall complexity is O(n^2). You should use StringBuffer and use append() method for the concatenation. It will work in O(K). K is the number of characters.

»
6 months ago, # |
  Vote: I like it +45 Vote: I do not like it

 Greedy Festival XD

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is multiset erase() faster than vector erase() ? My solution got accepted when I used multiset instead of vector in problem E.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    yep, vector erase() in O(n) and multiset erase in O(logn)!

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    erase in std::vector have the complexity linear to the size of the vector (it have to move the elements after the deleted element forward), while that in multiset is have the complexity log of the size of the vector.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, multiset is implemented as a self-balancing binary tree, for which deletion is O(log n).

    Vector deletion is O(n) in the worst case.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out why my solution is giving TLE on test 16 although similar solutions have passed all tests.

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Sorry, "Div3 round"… There won’t be a next time.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem A I used a set to add values which are not present earlier . After generating next number if it is not in set add it until you find repeating number in set . Return set.size()

Is the approach decent ?Started using STL more often now a days .

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes, I did the same but with using unordered map STL .

    Here is my solution.

»
6 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I wrote 2SAT for G, but I got TLE. It works O(const * N^3). For my opinion it must pass in 2 seconds :/.

UPD. Number of edges are N^2, so that all program works O(N^4) :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Need Help in Problem C1: why im gettting TLE in Testcase 10 whereas other similar soln's are working?? 53371370

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Yet another interesting case of cheating by 4ul_sharma and utkarshv3 who are from the same institute: Check here. MikeMirzayanov and Vovuh please look into it.

»
6 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Problems in this round are interesting and pretty good, thanks to Vovuh for setting these problems.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Take it for an example:

    7

    4 3 5 1 2 2 1

    Instead of putting people of different heights randomly with keeping the difference between two adjacent heights one (e.g. 2 1 1 2 3), you can try to find a maximum height and a minimum height and form a cycle with other heights in between them. To do it, you have to find the longest possible contiguous non-decreasing sequence of numbers with difference between adjacent numbers 0 or 1 in the sorted array of heights. Notice that we need at least 2 elements of same value except for the maxima and minima in our output sequence, else we cant form the desired cycle.

    For our example we go like this, if we take 1 as our minima and we can go upto 3 as our maxima. As we have only one 3 we can't accommodate 4 here. So we can form a sequence like this, 1 2 3 2 1. So we start from our minima, climb up to the maxima and again climb down to the minima. I hope you got the insight.

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In Problem B , What's wrong in this ? https://codeforces.com/contest/1157/submission/53365568 Gives WA on TC 7

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try this case:

    6

    234567

    1 1 4 4 6 7 8 1 1

    Your code stops at the 3rd element (4), while it is more optimal to continue.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, given a multiset m; does someone know the explanation behind lower_bound(m.begin(), m.end(), x) timing out in E(>2000ms): here, whereas m.lower_bound(x) gives AC with 233ms: here. I feel so frustrated and confused right now.

»
6 months ago, # |
  Vote: I like it +85 Vote: I do not like it

I really like problem G. With 1 clever observation, you can solve the problem in $$$O(nm)$$$.

There is a solution to the problem if and only if there is a solution with first row all zeros or a solution with last row all ones.

Proof: $$$n = 1$$$ is trivial. For $$$n \geq 2$$$, for a valid solution, as the array is sorted, the 0-1 boundary must lie on one row, and all the other rows should either contains all zero (rows before boundary row) or all ones (rows after boundary row).

Therefore, we can try check only 2 column configurations (1. flip all ones in first row, 2. flip all zeros in last row) to find the answer. The row configuration can be found by checking whether the row have a mix of zero and ones after flipping the columns.

Thanks for the great round! :D

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your great idea!:)

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very nice! thank you

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had a different idea resulting in $$$O(nm)$$$ time complexity. But mine was very laborous to code. Submission: 53355339

    Assume that the array is fixed. How do we check if it can be turned to only zeroes?

    1. Either toggle the first row or not
    2. Toggle every column with a one in the first row
    3. Toggle every row with a one in the first column

    Make an data structure that can maintain the state of this algorithm when we change bits in the original array, and make two instances of it, one with the first row flipped and one without. Then do the following:

    1. check if either datastructure can be made all zeroes
    2. If either could, output its current row- and column flips.
    3. Otherwise, toggle the last bit that is not yet toggled in both. This essentially changes the solution we want to produce from all zeroes to zeroes in all but some suffix.
    4. If there was no bit to toggle, output NO
    5. Otherwise, update the two structures, and go back to step 1.

    Why is this $$$O(nm)$$$?

    When you toggle a bit that is not on the first row or on the first column, the structures do not need to be updated, so the change can be done in $$$O(1)$$$. There are $$$(n-1)(m-1)$$$ such bits.

    When you toggle a bit that is on the first column but not on the first row, you have to toggle one row, which can be done in $$$O(m)$$$. There are $$$n$$$ such bits.

    When you toggle a bit that is on the first row but not on the first column, you have to toggle one column, which can be done in $$$O(n)$$$. There are $$$m$$$ such bits.

    When you toggle the bit both on the first row and column, you have to run the algorithm again in time $$$O(nm)$$$, but there is only one such bit.

    So in total, we do $$$O(1) \cdot (n-1)(m-1) + O(m) \cdot n + O(n) \cdot m + O(nm) \cdot 1 = O(nm)$$$ work.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D with binary search?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I will try to explain the idea of how i did.

    Suppose an integer x can be used as a1.

    Let the restritions:

    1. sum of all ai for i from 1 to k should be n;
    2. the condition ai<ai+1≤2*ai should be satisfied for each i from 1 to k−1.

    The min possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by one.

    The max possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by multiplying by 2.

    Therefore, to respect the restriction 01, the inequality down needs to be true:

    $$$x+(x+1)+(x+2)+(x+3)+ ... +(x+k-1) ≤ n ≤ x+x*2+x*2^{2}+x*2^{3}+ ... +x*2^{k-1}$$$

    The left side is a sum of arithmetic progression and the right side is a sum of geometric progression, so:

    $$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$

    Thus, we can binary search the x:

    • If $$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$, this x can be used;
    • If $$$\dfrac{(x+x+k-1)*k}{2} > n $$$, we have to decrease x;
    • If $$$ x*(2^{k}-1) < n$$$, we have to increase x.

    After find a possible x to be a1, we can binary the others elements of array a at same way.

    Complexity: O(k*log(N))

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I did the same but for finding k, I applied the formula: x= (n-sum(1 to k))/k.

      This will give you x in O(1) time. So I don't think it necassary to apply binary search.

»
6 months ago, # |
  Vote: I like it +20 Vote: I do not like it

"And for 1600-1899 the problems will be too easy" Not quite sure about this statement :o

»
6 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I overslept and finally I didn't participate this contest!Oh no.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody show me what I did wrong in my submission (problem C2).Here is my submission : https://codeforces.com/contest/1157/submission/53384089

»
6 months ago, # |
  Vote: I like it -18 Vote: I do not like it

what is trashforces without getting WA on at least one problem for making a stupid mistake that the shitty pretest couldn't alarm you about..............

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If S is a multiset. And what is the difference between S.lower_bound() and lower_bound(S.begin(),S.end())?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    According to documentation: Complexity of std::multiset::lower_bound is: Logarithmic in the size of the container.
    Complexity of std::lower_bound is: The number of comparisons performed is logarithmic in the distance between first and last (At most log_2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

    std::multiset::iterator is a bidirectorial iterator, but it isn't random access, thus std::multiset::lower_bound will work faster ($$$O(log(N))$$$ vs $$$O(N)$$$). In general, if you have to choose between container's method and an algorithm from std, the first option is more preferable. (There are some exceptional cases, but they are not related to competitie programming)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem G? I tried couple things, but nothing worked.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone

My submission 53393992 for problem E is failing on the first test case itself. But, when I run it on my terminal, it is giving the same output as the expected one. (same code on ideone.)

Can anyone tell me what's going on?

Thanks

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you never initialized the vector cnts

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought it is initialized by default to zeros. Isn't it so?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    if (it == s.end() && *it < n - a[i]) {
    

    Maybe you mean

    if (it == s.end() || *it < n - a[i]) {
    
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

editorials???

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me what's wrong with testcase 6 for my submission 53339053. The input is no correct.... The third line is mssing....

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you get n integers instead of 9 for the third line input in your solution.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my solution is giving wrong answer for Test case 10 on problem C1. Submission 53345673

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D,I the lower bound of num[i] is max(a[i-1]+1,(int)ceil((double)n/sumb(k+1-i))); what's meaning? why not a[i-1]+1?(I know it's worng,but why?) Thx!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wileE.Coyote Hackcount 448 Wow! good job!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what should be the answer for this test case for problem C1 test case

5

4 2 3 1 5

according me it should be 3

2 3 1

am I right ??

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    you misunderstood the problem. take leftmost or rightmost elements and make a strictly increasing sequence with those.
    5
    4 2 3 1 5
    the answer is 2
    LR
    take 4 (the leftmost elements) first and then 5 and make this sequence that is in increasing order{4,5}