By KAN, 7 years ago, translation, In English

Hello everybody!

Today, on March 4th 2018 the final round of Technocup olympiad for Russian-speaking high school students is held. The round starts at 11:30 Moscow time.

After the round starts, you can watch the current results.

For those who want to compete on the same problems, we will host two Codeforces rounds: one for the first, and one for the second division. The rounds will start at 15:35 UTC, don't miss them!

If you compete in the Final Round today, you can't compete in the rounds at evening.

The problems are prepared by Endagorion, komendart, rationalex, AndreySergunin, fcspartakm, MikeMirzayanov and me. For testing the problems many thanks to demon1999, Belonogov, vintage_Vlad_Makeev, adedalic, budalnik, GreenGrape, Neon! Also many thanks to vintage_Vlad_Makeev for his help in hosting the round at Codeforces!

P.S. Because of the olympiad, some Codeforces features may be disabled today.

Good luck!

UPD: Congratulations to Technocup winners!

  1. qoo2p5
  2. dima_z
  3. 300iq

Congratulations to winners of Codeforces rounds!

First division:

  1. V--o_o--V
  2. Petr
  3. Merkurev
  4. Benq
  5. dotorya

Second division:

  1. Deanamic_Programming
  2. kiber
  3. shad0w_walker
  4. Vitalya
  5. Geothermal
  • Vote: I like it
  • +156
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it -65 Vote: I do not like it

is it rated?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So why”Codeforces Round #468”disappeared now?In”Contests”

»
7 years ago, # |
  Vote: I like it -43 Vote: I do not like it

Hope the problem statements are as short as the announcement.

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Hope to see some quality problems A & B for <1200 contestants like me

»
7 years ago, # |
  Vote: I like it +41 Vote: I do not like it

The contest overlaps with Barcelona's match

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

*Forgets to thank Mike and Polygon*

*Mike TRIGGERED*

»
7 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Because of the Olympiad, some Codeforces features may be disabled today. ??

»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

I think Problems Scoring is not important nowadays :|

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Clashes with IEM Katowice finals.

»
7 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Will #468 be rated ?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually it'll be reverse rated! The problem setters decided that the person with the lowest rank in the contest will get the biggest positive rating change. So you should try your best to do as bad as possible! Good luck!

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

      I am following your advice. Let's see how it goes !

»
7 years ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

The one who wrote problem Div-2 D has very bad English skills (hardly understood what the problem setter had in mind).

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

    Div1-C was even harder to understand for me, I spent 10 minutes trying to understand who would be lying about what.

    (Not like I managed to solve it after I understood the question)

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

      Well maybe. As you can see from my rating I haven't even approached that problem.

»
7 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Oh, how I missed this improvised English on Codeforces!

Seriously, I understand some random amateur setter letting this happen, but given all those commonly mentioned names in the announcement, is this really what we get?

It is also very funny how sometimes people with obviously bad grammar and limited vocabulary decide to throw in a few uncommon words, who knows why (Div-1 A).

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    Div-1 A has a pretty good statement. I think you meant Div-1 B, which fits well your description.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The only problem with good statement I saw was Div-1 E. My last sentence from the previous comment was specific to Div-1 A.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    It's not the best English, but everything seemed pretty clear even if you had to reread once

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When it comes to languages, my definition of pretty clear never coincides with German speakers' xD

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      I'm a native english speaker and I thought it was unclear, especially for C

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

RIP rating...

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't I see any hacks? Were pretests particularly thorough?

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

    There were a few. I could have had a successful hack on C, had I seen it earlier since somebody in my room messed up N and M.

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How did NotSoStupid manage to solve B in 20 seconds?

»
7 years ago, # |
Rev. 2   Vote: I like it +56 Vote: I do not like it

In my noob opinion, first 3 problems were way too easy, now ranks 70-350 of div1 are all decided by time.

Now anyone who fail system testing basically goes back to div2.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    That is how it is in Div 2? how about stop crying?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    What was Div1C about ? For me the easiest way was to find the biggest subsequence whose cnt values are increasing then decreasing, but I could not find a way to do it in a reasonable complexity.

    I saw everybody solving it, did I miss something obvious?

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

      Longest increasing subsequence with segtree is n log n

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Compute the longest increasing subsequence ending in each point and longest decreasing subsequence starting in each point (LIS on reverse array) in n logn each and then one linear pass. (passed pretests at least)

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      just find for a position pos longest increasing that ends there, and longest decreasing that starts there

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

      This problem is pretty standard. It can be easily solved using segment tree. In segment tree at position x we store longest increasing subsequence which ends at some position with height x. So longest increasing subsequence for every position i is maximum in range [0, height[i]] (for all values with smaller index j, j < i) + 1. The same can be done for longest decreasing subsequence.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        Can be done in an even easier way using only vector+lower_bound.
        Refer here

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    still only one solution failed :(

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The segment tree actually isn't necessary. To identify the longest increasing subsequence we can maintain an array of the lowest value at the end of an increasing subsequence with length X we've discovered so far. Then we can binary search to find the longest increasing subsequence ending at the next index. We can do one pass forwards and another pass in reverse to get the longest increasing and decreasing subsequences ending/starting at each point. Then consider all of the possible values and find the maximal value of the sum of the increasing/decreasing subsequences for that value minus one (since that particular element will be double-counted).

    The complexity is O(N log N). https://en.wikipedia.org/wiki/Longest_increasing_subsequence A similar algorithm is outlined here (for longest increasing subsequence).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack for B?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can somebody explain to me the answer of 3rd sample of Div1-B, why is it 0.1 the probability? The statement wasnt clear for me either, that thing of open a letter I never really understand it.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    aabaabbbbb abaabbbbba aabbbbbaab abbbbbaaba . And bbaabaabbb baabaabbbb baabbbbbaa bbbbbaabaa bbbbaabaab bbbaabaabb. If the 1st letter is a, vasya can choose 3rd letter and say since it is the only letter containg a in 3rd pos and in 1st. so the ans is 1 / 10.

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

      I dont understand you if the first letter is "a" and you choose third letter then you have for example: aabaabbbbb aabbbbbaab

      which both have "a" in 1st position and "b" in 2nd position so the cycle is not uniquely determined.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the first letter shown is "a", you can ask to see the 5th letter of the resulting string. If it is another a, you know k=2.

    Thus, you can win iff k=2, which has a probability 0.1 of happening

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    All the possible shifts were

    bbaabaabbb
    baabaabbbb
    aabaabbbbb
    abaabbbbba
    baabbbbbaa
    aabbbbbaab
    abbbbbaaba
    bbbbbaabaa
    bbbbaabaab
    bbbaabaabb
    

    If he gets a b first, he cannot determine the shift. Otherwise, if the shift gets an a in the beginning, T can now be one of the following:

    aabaabbbbb
    abaabbbbba
    aabbbbbaab
    abbbbbaaba
    

    If Vasya opens the 5th letter, there is a 1/4 chance it would be an a. If he instead opened any other letter, he would not be able to determine the string. Because of this, there is a (4/10)*(1/4) = 1/10 = 0.1 probability of he winning.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! I finally understood.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      a a b a a b b b b b

      a b a a b b b b b a

      a a b b b b b a a b

      a b b b b b a a b a

      Here only 4th one have 'a' in the 7th position(similarly, only 2nd string contains 'a' in the 3rd position). So, if he would have instead opened it then also he can uniquely determine the shift. so, isn't the probability of winning is 0.3? Please correct me where i am going wrong.

      UPD : sorry for this! I understood now. Thank you :)

»
7 years ago, # |
Rev. 2   Vote: I like it +53 Vote: I do not like it

seriously horrible long statements.

Could someone explain what problem Div1C is asking for :3

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Took me a while to understand, but I think it asks for the most amount of points you can query without knowing if the opponent is lying. Problem statement is highly misleading. At least this understanding passed pretest.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh!. this means after finding how many seg that each points belongs by an aux array and find the longest non decreasing subsequence in the result right?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes, you want to find combination of longest nondecreasing subsequence to a point + longest nonincreasing subsequence after the point

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

    Let (c1, ..., cm) be the answers to the queries for every possible x. How many of these do we need to change, so that there exists a set of intervals S and an integer x, such that li ≤ x ≤ ri for all intervals in the set?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve task D (div 2)?

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

    Count the number of tree levels with odd number of nodes.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    answer is the number of heights such that the number of apples on that height is odd

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But then in testcase #3, shouldn't answer be 8?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no because there's only 4 heights

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        draw the tree and you will see (p_i is the parent of i+1)

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to prove that?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        Apples can annihilate only if they have equal tree level, so we can say that for each level all apples go to the first node and they annihilate there

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

    In the first second you are interested in the nodes that will fall into node 1, let's call these nodes D. In the second second you are interested in the nodes that will fall into D (because the next second (3rd second) D will fall into 1)... etc

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

      I get it now, and feel terribly stupid :P btw thanks :)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how the answer for teoder is not lying for 2nd case is 5

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hack for B: 8 4 5

»
7 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Stuck at 11 pretest on C.... impossible, where did i go wrong? any hacks guys? 11 WA and for over an hour couldnn't find any test case to make my code return WA -_-

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

    It was necessary to check examples of such a if 1 2 2 3 then you can send 2 2 2 2 or 1 3 1 3 I also understood when there were 2 minutes left) but did not have time

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    6 1 2 2 2 2 3

    yours -> 4, 222222 answer -> 2, 111333

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try with:

    6
    1 3 2 2 2 2
    

    Answer should be:

    2
    1 1 1 3 3 3
    
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Div-2 D description was totally weird.. I couldn't tell what it says. ;(

»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

does the writer of the problem D statement even speak english? that text is totally weird...

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think The problem description should be more concise >.<

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Personally, I really liked the problems for this round, D has a very clever solution and E was pretty interesting too. C was difficult to understand for me, admittedly, but I don't think it was a bad problem. A and B for me I don't really care because I solve them quick, but they didn't seem bad

»
7 years ago, # |
  Vote: I like it +66 Vote: I do not like it

Div1C has the most confusing statement I've ever seen. Setters should really be careful when translating.

»
7 years ago, # |
Rev. 3   Vote: I like it +185 Vote: I do not like it

Inflorescence number 1 is situated near base of tree and any other inflorescence with number i (i > 1) is situated at the top of branch, which bottom is pi-th inflorescence and pi < i

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    That's when you stop reading and look at the tests and explanations.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me with this.

Div 2, problem C, test 3: Input:

7

-10 -9 -10 -8 -10 -9 -9

my output was:

5

-8 -8 -8 -9 -9 -9 -10

I think this should be right but I am getting wrong answer.

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

    The sum of the two sequences are different, so their averages are different, which violates the first constraint.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the sum of your numbers is -61 but it should be -65

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    original measurements --> the output --> the minimum between them (number of equal measurements)
    
    {-10,-10}             --> {-10}      --> 1
    
    {-8}                  --> {-8,-8,-8} --> 1
    
    {-9,-9,-9}            --> {-9,-9,-9} --> 3
    

    so, the total number of equal measurements in your answer is 6 not 5.

    EDIT: sorry i miscalculated, it is 5 lol :D 
    
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Too UNCLEAR problems

»
7 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

I think this contest would've been better if div2 C and D were swapped, and each division has 6 problems.

Div2C was really nice and actually has less solves than D.

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

    well they have the same score.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Problem A on div1 was actually div2D, and div1 has only 5 problems

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well C is just implementation, but for D you need to know some tree traversal algorithm, i think that's why it was chosen.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think Div2D was easier to read, so it was attempted/solved first by many. The solution was also pretty easy to implement when you get the trick. I don't think D was easier than C though.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think this contest would've been better if div2 C and D were swapped, and each division has 6 problems.

    No, it wouldn't. I was so glad when I read Div2C and realized that it's not in Div1.

»
7 years ago, # |
Rev. 2   Vote: I like it -40 Vote: I do not like it

Too unlucky contest for both Contribution and Rating!

»
7 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Not sure if my bad performance today is due to my bad forms, bad English translations, or both...

One example for my latter point is Div1B.

Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability.

And I thought I have to calculate the possibility of him guessing the answer at circumstances that he has no certainty at all, wasting me at least 20 minutes in trying to understand pretest 2 of it.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    same here

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That problem was clear once you read "Note that Vasya wants to know the value of k uniquely, it means, that if there are at least two cyclic shifts of s that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win."

    Div1C was another story...

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Ouch, heck....

      Oh, and Div1C, after reading a few first lines, knowing I had only 10 minutes left, I instantly gave up.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain why 2nd example's output of Div2 E is 0,333333? I thought it should be 0,5.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Why do you think it's 0.5?

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

      This was how i thought: If you the first letter you got was 't' or 'c', you lose cause you couldn't pick the next letter to make sure about k. If the first letter you got was 'a' or 'i', you win cause you can pick the next letter to guess the k. So the probality is 2/4 = 0.5

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The probability that you get 'a' or 'c' however is 4/12, as explained in Renaats' comment below.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have 4 letters "t", 4 "c", 2 "i", 2 "a". For each "i" and "a" you have a probability of 1, while for "t" and "c" it's 0. ((0*(4+4))+(1*(2+2)))/12=(0+4)/12=4/12=0,3333

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why div2c should be so harder than div2d? and have the same point can anyone explain this to me?! :|

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I personally found 2C pretty intuitive--just two important observations: that you should rescale so that you're working with zeroes, ones, and twos (or some other three values, but these work best with the array setup), and that you should either transform pairs of ones into a zero and a two or sets of zeroes and twos into pairs of ones, whichever is more advantageous. There might be some alternative solution you could come up with that doesn't work so well, though--

    I agree that D was quite a bit easier, but I don't think it's too unreasonable, especially considered they were worth the same amount of points.

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

      i used those observations but i got WA on testcase 119 (:D). but anyway I spend 2 time more than div2E on this problem maby it shows that the imlementation was a bit awkwark.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey can someone plzz help me to find bug in my code for Div2(D) , i am getting wrong answer for 12th pretest. solution link : http://codeforces.net/contest/931/submission/35945047

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

For those who still wonder what inflorescence is :D

Definition:

a : the mode of development and arrangement of flowers on an axis

b : a floral axis with its appendages; also : a flower cluster

Picture
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think is better to use plain English for description when you are not good at it.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Too amazing submission... for C problems, because he inserted all elements into set and got them to vector afterwards sorted the vector!

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

http://codeforces.net/contest/931/submission/35943874 got the wrong answer on Laboratory problem (C)...... what is the best way to solve this que.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    6 1 2 2 2 2 3

    Answer:

    2 1 1 1 3 3 3

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

      but its already mentioned in the question that it's guaranteed that the difference between max and min is 2.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        6 in the first line is the number of numbers in the input. 2 in the 3rd line is the number of differences between the input and output.

        They should have been on different lines to be more clear.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        He meant

        Input

        6

        1 2 2 2 2 3

        Output

        2

        1 1 1 3 3 3

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain div2 F

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

    So other people have been saying that they've seen this problem before, but I haven't, so I'll try to explain it as if you haven't seen it before either.

    First thing's first, we notice that if a point is not in all segments, that is equivalent to saying that you can find two segments that are disjoint (draw a picture, you will see why this is true).

    Next thing, we notice that if the number of segments decreases and then increases, there must be a pair of disjoint intervals (that is, Sasha is sure Teodor isn't lying). Let's look at sample test 2 to see what I mean. If you were to query the number of segments at each point going from left to right, you would get 1 2 2 1 2 2. Because at points 3, 4, and 5, the queries are 2, 1, and 2, that is, they go down and then up, so we know that there is some interval that ends at 3 and some other interval that starts at 5, so we have two disjoint intervals, and Sasha is sure there is a point that is not in all intervals. HOWEVER, if we were to only query points 1, 2, 3, 5, and 6, Sasha's knowledge of the above array would be 1 2 2 _ 2 2. If the blank was filled in with a 2, he still could not tell whether Teodor was lying. If you play around with the numbers more, you'll see that this is the case for any non-increasing sequence, non-decreasing sequence, and unimodal sequence. For example, other arrays like [1 _ _ 3 _ 5 6], [8 _ 2 2 _ 1], or [1 2 4 _ 6 _ _ 2 1] would not give Sasha enough information to tell whether Teodor is lying.

    Thus, we can reformulate the question as follows: what is the longest unimodal subsequence of the array a, where a is the array such that ai is the number of intervals at index i.

    This is easily solvable if you know LIS algorithm, since we just find LIS at each index, and LDS at each index, and test each possible point to be the peak, which will be linear, making the whole thing . Also, constructing the array a is easily done in linear time, since we know all the segments in advance, so we can just increment left endpoints, decrement 1 past right endpoints, and calculate partial sums to get a.

    My code: 35953013

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I still don't get why we can't tell Teodor is not lying if we see 1 2 2 _ 2. My reasoning is we know there is a point that is only contained in one interval and a point that is contained in two intervals. Therefore the point contained in one interval cannot be contained in all intervals.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What you've shown is that there exists one point that does not belong to all intervals. What we're trying to show is that all points do not belong to all intervals.

        For 1 2 2 _ 2, this could be created by the intervals [1, 5], [2, 3], and [5, 5], or it could be created by [1, 5], [2, 5]. In the first case, Teodor is not lying, because all points do not belong to all intervals. In the second case, there are several points that belong to all intervals.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks. I misinterpreted what the question was asking.

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

      Thanks! Your explanation and submission were really helpful

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone plz tell me what is wrong in my code for E https://ide.geeksforgeeks.org/yLo7pWenjV

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Watching Messi's brilliant free kick while coding and making a stupid mistake in indices results in wrong answer on last test for Div2/E :)

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

    Heck, look on the bright side, if that was a WA on Div2B, it would be truly ironic for you :-P

»
7 years ago, # |
  Vote: I like it +26 Vote: I do not like it

wow i have 211 rating now

»
7 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

For Div1-C Sasha should not be sure that an point exists that does not belong to all segments. So naturally I thought that if there are 0 segments at a point Sasha cannot know about it because then that point belongs to no segments so definitely it cannot belong to all segments. So I didn't include such points in the count and got a wrong answer. Am I interpreting the question wrongly?

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

    Yes, it asks for the max. number of queries such that you can't know that there is no point that is covered by all segments. Not whether there is one point that is not covered by all segments.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah my bad, I get it now.
      The confusing language didn't help either :(

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I made the same error and wasted thirty minutes on that. The zeroes can count for the same reason yassin described.

»
7 years ago, # |
  Vote: I like it -18 Vote: I do not like it

The problems didn't really have unique Ideas. Add "Bad Grammar" to it. It was really hard to understand the problems' english.

»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Here's a clarification for Div. 2 E if anyone else had trouble interpreting it: After being given the string and a character, we want to choose a shift in the index for each letter that gives us the highest probability of being able to uniquely determine what the k was.

For example, in the third sample, if the randomly selected character was an 'a', then if we look at the character two spaces to the left and it is also an 'a', then we know that the first 'a' is in the 4th character in the original string. This turns out to be maximal, and if we get a 'b', then we cannot determine the shift. So, our strategy will basically work for 1 character out of 10, so the probability is 0.1. So, we look at all possible indices and for each distinct letter ('a', 'b', etc), we find the shift that gives us the highest number of letters that only appear once.

35950009

»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Editorial?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Are there any other problems similar to Div 2 D? I think problem D is very tricky, so I want to practice more like that. Thanks

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Div.1 D ?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Firstly, if a black stone has the same parity as the white stone (in chessboard-style colouring), then it can never block the white stone. So the problem can be split into two separate subproblems by parity.

    A possible strategy for white is to always move to the right. So for black to win, there must be a black stone that can intercept white on the right i.e. for which xb — xw > abs(yb — yw). Similarly, there must be black stones which can intercept white on the left, top and bottom. It is then not too hard to prove that these four stones can keep white boxed in and block it in finite time. So one needs to count the number of places white could start that are boxed in on the four sides.

    This can be done by rotating the problem by 45° and then using a line sweep to count the number of position for each y value. With the right data structure (a multiset in my case) it takes O(N log N) time.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, I've understand the algorithm.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share the reasoning for your first statement?

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem E is just straightforward segment tree.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can be solved even without segment tree, but with queues ))0)0

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach? Did you use coordinate compression?

»
7 years ago, # |
  Vote: I like it +46 Vote: I do not like it
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is the 2nd time I see you reporting this guy, and the 3rd time I've seen him being reported.

    Wondering if he just simply prevailed like that?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    KAN, MikeMirzayanov what's going on with this? These guys stole rating from other participants, who placed behind them — for example me. It is also not the first time they were reported. Why is there no action from codeforces against them?

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

When will the tutorial be available?

»
7 years ago, # |
Rev. 2   Vote: I like it -53 Vote: I do not like it

Div2F / Div1C was easy to solve using google. Just search "longest increasing subseqence" and you will get ready code.

Russians could open, for example, this site and get code from there (minor change and it it adapted for task): http://e-maxx.ru/algo/longest_increasing_subseq_log

Also task on this algorithm was on ACM semifinal 2014.

P.S. More minuses, more.. Of course, I did not say something cool and did not posted any (stupid) funny picture, I should be punished :)

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I think that the main difficulty of this problem is realizing that answer is longest increasing-decrasing sequence, not implementing it.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I realized it at once after I drew 2-nd example on the paper. Tried to code something on my own, then google this algorithm and get up with this task after I saw search results.

      Interesting task, I am not trying to prove that is was bad or boring, but authors could confuse it a bit more to make real F problem.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you are professional. Because when I solved this problem, most of the time I spent on searching and substantiating the idea, and only 2-3 minutes on implementation of all of this. So, for me this problem is more difficult in understanding the idea than in implementing the solution.

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

          That's why you are professional programmer, but not me.

          And that's actually why I wrote about it. Participiants who know about this algorithm implemented idea faster than others, who spent more time on making up logic/googling (or did not solve it at all, as me).

          But I really understood it fast.Do not ironize about it.

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

            So, are you saying that people that knew how to implement algorithm implemented it faster than those who didn't? Like... really? I'm lost :)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please someone tell me what is wrong with this solution. My idea is that: if max-min==2, then for each pair of (max,min) i substitute both the elements of this pair by min+1. Here is my submission: link

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    what about replace 2 numbers min+1 with min and max?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay this case I was missing. But does this mean, for max-man==2 (max,min)->(min+1,min+1) ----case(1) (min+1,min+1)->(min,max) ----case(2) Do I handle case1 and case2 seprately and print the minimum one? After you point out the mistake I did it this way, but same I am getting error in 11 tc

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should check what case will be better and apply it. With case 2 you should also check this: you can only apply this case if "max" is in the original array, because the bounds condition. Maybe my submission helps you

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please add editorial. It is very much needed now

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there any idea about div1 E? Thank you.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    let's imagine that one of sides of coin is 0, other is 1.
    First of all you need to compress coordinates. Then try to develop some kind of dynamic programming approach. All line will be divided to segments. dp[i][j] — equals to combinations for first i segments j — it is five states. There three types of segments "ones" — segments that consists of only 1; "zeros" — segments that consists of only 0; "zeroones" — segments that consists of 1 and 0. Let's describe our states.
    0 state — it is state where last segments is "ones" and before some "ones" it have "zeros" segment. For example this combination is described with this state
    (...any segments... , "zeros", "ones", ..., "ones").
    1 state — where last is "zeros" and before some "zeros" it have "ones";
    2 state — last "ones" and before some "ones" it have "zeroones";
    3 state — last "zeros" and before some "zeros" it have "zeroones";
    4 state — last is "zeroones";
    Transitions is obvious.
    Also you must store for 0 — 4 states coordinates where the last segment of second type was (for example for 0 state first type is "ones" second typed is "zeros", for 3 state first type is "zeros" second type is "zeroones".
    And when you have coordinate of end of some segment (from queries) that requires for example 1 you need to delete all combinations with states 1 and 3 that have coordinate of last segment of second type strictly less than L coordinate of current segment(from queries). For this purpose you can used four queues with pairs(last_coord_of_second_type, combinations).
    For details see my solution
    Sorry for my English.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you very much! I'm reading your post right now.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For me it is much easier than div1 D

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "you need to delete all combinations with states 1 and 3 that have coordinate of last segment of second type strictly less than L coordinate of current segment(from queries). "

      I think that the hard part for this problem to me is how to manipulate any specific regions satisfying some states. I just want to make clear of "How to calculate any specific regions instead of regions from starting point".

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you describe your question in more details

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I've understood the general idea in your code. It's the part "function ers()" in your code that is most tough for me to understand clearly and completely. For example, how can it be guaranteed that a queue will work correctly, not missing any part that need to subtract. For this part, I haven't got that clear. And another crucial point is, the idea to divide situations with "111.." at last into situations with "0111..", and it can be shown there's no aftereffect (for segment before 0, it's guaranteed by definition of dp[], for segment after 0, it's guaranteed by containing at least one '1' and one '0'). This part is something I haven't thought of, very nice idea!

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ok, I will try to describe how things goes in function ers(). First of all purpose of this function is to delete some combinations from witch we can't update our future states. It happens because when we have segment L, R that requires "1" and we are going through coordinate R, in future steps we can't update our states with dp[0] where coordinate of last '0' is less than L because in this case we will get that all our segment [L, R] will be covered with "0" (it is invalid), therefore we subtract from dp[0] such values than responsible for dp[0] and their last "0" less than L. Why do we can use queue? Because we erase values that is less than something and add values that is bigger than every value in queue now (there "value" means coordinate of last secont type)

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              "to delete some combinations from witch we can't update our future states." I had stuck on this point a long time, not being aware of any ways to remove this aftereffect. "therefore we subtract from dp[0] such values than responsible for dp[0] and their last "0" less than L."And I wanted to solve this too. In your function ers(), you simply subtract dp[] with q.front().second, and pop it out, so why is that correct? /*I think that in your code, for any segment that has been processed, it's left point is left to the q.front().first, so to gaurantee the value is just invalid for the processed segment and valid for others processed before, and how to deal with segments before*/ Ok I'll try to use pictures instead, because I find that I can't explain my thought very well just by words. ^_^

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I guess that the part in purple color is processed by segment before, also by ers(), but can't make it very clear.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Eventually, that purple color situation do not need to concern about, they just won't exist.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                and there is still situation that q.front().first is right to the left point of processing segment.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  And for this situation, just ignore it as well, as your ers() won't process anything too.

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              OK, I think I've make every situations clear! Oh it's fantastic to consider using queue, and indeed it can hold any of those complicate situations. Thank you!

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          And I'm studying this code http://codeforces.net/contest/930/submission/35970918. It seems he doesn't use structures similar to queues.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      At first, I spent a very long time in thinking about Inclusion Exclusion Principle and Probability Theory, and wasted a very long time.

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When will the editorial be published ?

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Tutorial is up. Link

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't understand the problem.. Descriptions are so suck.