GlebsHP's blog

Codeforces Round #401 (div. 2)
By GlebsHP, history, 8 years ago, translation, In English

Hello everybody!

Tomorrow round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by feldsherov, ch_egor, halin.george, ipavlov and GlebsHP.

Hope to see you in the standings!

P.S. Scoring distribution is standard.

UPD Congratulations to the winners!

  1. Mr.Stream

  2. mamka

  3. funtik

  4. HE_MATEMATIK

  5. HollowAngel

UPD2 Problem analysis is here.

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

Comments Comments (232)
| Write comment?
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been translated by GlebsHP (original revision, translated revision, compare)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -37 Vote: I do not like it

    Этот раунд рейтинговый? Просто в тексте не было информации об этом!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      рейтинговость раунда определяется состоянием системы codeforces)

      the rating you get is the rating than CF just want to give)

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +273 Vote: I do not like it

programming competition for school students of grades from 6 to 9.
I was playing Mario when I was in the sixth grade
God bless my childhood

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

    I practice for typing when I am grade 6. Who bless my childhood? please!

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

    G0D_FaTHER what were we doing when we were in 6th class ? I remember spending time in school ground!

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

    some of this students are red on codeforces. for example voidmax he is 9 grade btw (he was red)

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

      Oh no...
      maybe they have to make a div1 round for them not div2

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

    Man ,I didn't have PC when I was in the sixth grade :(

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

      I didn't know what's a computer when I was at 6th grade!

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

        That's nothing! When I was in 6th grade, we had to walk to school 30 kilometers every day, uphill both ways!

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          As a kid I lived in Manhattan and it was mandatory to walk a different route every day!

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

            that's when you realised how important dp and graphs are.

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

          both ways uphill? :) I had only one way uphill

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

    I started learning programming at 5th grade because our "modern" PC died and qBasic was about the best "game" I managed to find for the older one xD

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

Why is my 3rd hacking attempt still waiting while my 5th attempt has been judged?

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

Can you change the contest time, please? .. In Egypt we have a weekly prayer time in that time, an hour after that will be perfect.

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

    The contest time is bounded by the time of onsite competition. It should start after the onsite competition has started and finish before it has finished. I'm sorry, but there is no way we can change the competition time.

    → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I hope to change the time as it time of prayer in most of arabic countries

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This is the worst timing you can put for arabic muslims :D

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

number of problems ?

→ Reply
»
8 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Seems like the King got resurrected .

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

change the time please. it's our week pray time .

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

These days number of problems <= number of problem setters. Get prepared to read long problem statements and strong pretests. I wish I perform well :)

→ Reply
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

It seems like I am the ONLY arab who will participate in this contest

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

    Why aren't you in the same situation as the others?

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

    I wanna take a moment of silence to thank god who created me an atheist so i can peacefully take part in today's round :D

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

Canada I am coming.

→ Reply
»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

you will notice a decrease of contestants because of the Arabian issue

hope to change the time of the contest

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

    Please, keep in mind that Codeforces always tries to vary competitions time to give more people an opportunity to participate in at least some of the contests.

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

      Exactly. As much as the typical time may work well for arabs, russians and other europeans, the contest usually ends at 2-5am in Korea, Japan, etc. This is a global community and any time chosen would not work for some people. Also it is well explained above why this time cannot be changed as it has to work around the on-site competition.

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

    But when most of competitions carry out in night time for east regions, it's ok for you and you don't have any problems. Think about others sometimes.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

This happens when you don't thank MikeMirzayanov, warning! :P

→ Reply
»
8 years ago, # |
  Vote: I like it -84 Vote: I do not like it

To all the people who have pray time during the contest: which one is more important, Codeforces or praying in the name of some god who might or might not exist? I personally think that skipping one day of prayer is justified ;), this can be a secret between you and me, nobody else has to know.

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Thank God I don't believe in God.

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Since the king is back, I hope this round will go smoothly :)

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

I don't like long problem statement , please try to keep it short like atcoder!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How many to problemset?

→ Reply
»
8 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Can you change the contest time, please? An hour after that will be perfect.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Before writing such comments, pls read the previous comments about it! There are only 39+1 comments till now.

    P.S sorry for my poor English :)

    → Reply
»
8 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Is this round will be rated?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will CF beat the tortoise today?

→ Reply
»
8 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Rating prediction for this contest could be found here (after contest begins)

Extensions:

About CF-Predictor

Good luck & high rating for everyone!

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the round will be interesting.Good luck to all participants!

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

points distribution?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    Come from back and do this : string s = v[i]; while(s > v[i+1])s.pop_back(); v[i] = s; I don't know whether this will pass sys tests

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Iterate from (n-1)th string to 1st string, go on comparing with next string and trim this string till it is not greater than the next one.

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

      But since n can be 5*10^5 and length of string can be 5*10^5,

      won't that solution with its ~ 2.5*10^11 operations be waaaay to slow? (in worst case)

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

        sum of lengths of all strings is 5e5

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

          Thanks, apparently I need to pay closer attention to the problem statement.

          → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

Best Div2 Round ever?

→ Reply
»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

I think B is harder than D ...

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

    If RoyalWyvern above is correct I agree. Had only 13 minutes left after A, B and C. Normally I quit, but I thought what the heck... Past pretests on D... |-)

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

      I had only 10 minutes left after A,B,C. I finished coding D 1 minute late.

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

        Well, at least you solved D 2 minutes quicker than I did!

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

My first comment....Please Upvote me

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Make a set of a,b,h using set < pair<ll,pair<ll,ll> > >
    where first element of pair is b and second is pair(a,h)
    then sort the set.
    Then apply dp a[next_i] < b[i]

    check for the maximum possible height.

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

    Sort by B values. Then dp[i]=dp[next[i]]+height[i] where next[i] is the nearest ring to the i'th ring such that a[next[i]]<b[i]. Incase no such next[i] exists then dp[i]=height[i].

    Then the answer is the maximum of dp[i] where i varies from 1 to n.

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

      What do you mean by the "nearest". What is the order on ai?

      → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

My exact same solution gave me AC in c++ whereas it was giving me TLE in python. This wasted my 15 mins and also 1 incorrect submission

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My correct output is weirdly getting wrong answer on 1st test case itself -_-

Looks like CF knows dark magic to make correct output wrong.

Is D to be solved with trie? I constructed the trie from nth element to first.

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

    not needed ... keep the last string as it is... then greedily check the max prefix you can keep from bottom to top

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why WA in pretest 1 in D? all samples matched... :/

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

    Same with me.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    First test may be different from the first example.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      No it's not. I asked them. In custom invocation also, it's producing wrong answer instead of correct one for sample test case 1. Something's wrong with CF server.

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

        It might be that CF compiler does not give the same answer for the test as yours.

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

    It may be because the way you outputed the strings. Initially i was changing all the characters that shouldn't be outputed to '\0' and it didn't work,but the next time I just printed the characters I had to and ignored the others(and passed the pretests)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I checked that too. The problem is with server. I ran custom invocation, and my variables are getting incorrectly assigned on CF servers. I had a variable whose value I explicitly set to 0, but CF is taking it to be 1.

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

        i dont think there is a problem w cf server if it is only your code that is running wrongly. Maybe there is some ambiguity somewhere? why not share your code for us to find out?

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

          http://ideone.com/w9V6KY

          Run this code on test case 1.

          My output from custom invocation is this

          output from custom invocation
          → Reply
»
8 years ago, # |
  Vote: I like it +113 Vote: I do not like it

First div 3 round :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    I disagree. For me it was Div 1.89 =)

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

      So you are claiming this is harder that the usual div 2 round?

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

        Yes, for me it was harder than usual.

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

        I think A and B are harder than usual but D and E are easier.

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i tried to hack a solution using generator but it was showing some return 3 error from validator.exe
Here is the program ,what is wrong in it

generator code

what is wrong with it???

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it

    After sync_with_stdio(false), you cannot mix cout and stdout. Calling fflush(stdout) might be the problem

    EDIT: Nevermind, it seems to be another problem

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

      endl automatically does that. Why did he even used that. :P

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

      no ,initially fflush was not there, I added fflush when it was showing error

      I feel there are extra spaces at end of rows of input

      Does i care about those extra space?

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

        There shouldn't be extra spaces in the end of the line. Validator checks for it.

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

When you spend all your time solving C and then realize that D was easier(atleast for me) and should have tried that.

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

    Cannot agree more. Even E is easier than C

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

      I just saw the problem E. Is it graphs and CC?

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

        I cannot code it in time (cuz my stupidity makes me waste around 40+ mins on problem C). However, I am pretty sure it is sorting, dp and segment tree.

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

        Its on simple greedy and sortings

        → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How do you solve C without using bitsets? They make the total complexity of my submission O(k*m/64), and that probably won't pass in 1 second ;( upd: yep, it did not

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

    I used segment trees with range max query and it passed pretests.

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

    For each row i calculate min row that can be reached, call it mni. Then if mnr <= l then answer is yes else no.

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

    p[i] — the first index where an increasing sequence begins, which comes to the i (this sequence can go on). Then check

    if (p[r] <= l) answer is Yes;

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 6   Vote: I like it +6 Vote: I do not like it

    You can store in the array the ranges with the maximum size, that contain sorted column.

    int range[100100]; // range[left] gives right side of the range: int right = range[left]

...

while (k--)
{
  int l, r;
  cin >> l >> r;

  bool inside = range[l] >= r;

  cout << (inside ? "Yes" : "No") << '\n';
}
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do you compute range[]? Isn't computing it O(n^2) making it TLE?

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

        what I ment was O(n*m) making total running time O(n*m*k) ~ 10^10

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

          But you only need to compute it once, which gives the time of O(n*m + k)

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

            Thanks, I think I need to go back to sleep.

            → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        Look at the example. We can split this matrix into disjoint sorted columns:

        We read this matrix from top to bottom, row by row. When we encounter a value which is smaller than the previous value in that column ( if (val < prev_val[col])) that means we have just met the right end of some sorted range. For example, look at the first column: 1 3 4 5 4. After reading first 4 values 1 3 4 5 we encounter a value 4 which is smaller than the previous value 5. Now when we've found boundaries of the sorted interval 1 3 4 5, we should record them. We know that this interval started at l and we know that it has finished at r. We do a loop for (int i = l; i <= r; i++) and record what we have discovered: 

        for (int i = l; i <= r; i++) range[i] = r;

        How many times will we touch an element of the matrix? At most 2 times. The first touch happens when we read it. The second touch is when we record the interval with a for loop.

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

          Thank you for the amazingly detailed answer.

          I think we can even go bottom-up from n-1 to 0 for each column j, so that every time we descend we remember the largest row index we started descending from and update each a[i][j] accordingly, only needing a single for loop.

          Thanks again!

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

            When we go top down, we don't need to store the original matrix. So top-down traversal should have a smaller memory footprint than bottom-up.

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

              I understand range[l]>=r but why range[l-1]>=r?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                ← Rev. 3   Vote: I like it 0 Vote: I do not like it

                I don't know :)
                In the original idea I came up with during the contest I wanted to find 2 intervals which are closest to the given index l. So, I have thought about the following configuration: [l1, r1] l [l2, r2].
                I wanted to check that I fall inside of either the first interval or the second interval.

                But in the algorithm that I have described we need to check only one interval. I will edit my comment.

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

    I solved it by just traversing the 2d array
    and maintaining a index of minimum and maximum element
    http://mirror.codeforces.com/contest/777/submission/24969962

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

    You can use Dynamic Programming. You have dp[i][j]-the longest non-decreasing subsegment(continous subarray) of the j-th column that ends in the i-th line.To get it,you simply look in dp[i-1][j] and check if a[i-1][j]<=a[i][j]. If it's true,dp[i][j]=dp[i-1][j]+1,else dp[i][j]=1. Also,you need best[i]=the maximum of dp[i][k] with k in range 1..m At each query,you check if best[r]>=r-l+1 and print the answer depeding on the condition.

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

    store in one dimension array

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

    3 cases: 1) n==1 YES for all requests 2) m<=1000 you can over 1000 colomns all one in O(1) * 100 000=k so it take O(10^8) 3)m>1000 ,so n<= 100 so I just build table answer[100][100] for all possilble l and r

    http://mirror.codeforces.com/contest/777/submission/24975294

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it okay to ask some questions here? I have joined the contest now and also yesterday but I was unable to submit atleast one solution. I wonder why my rating didn't go down yesterday. Will my rating go down now?

→ Reply
»
8 years ago, # |
  Vote: I like it -11 Vote: I do not like it

KAN please look into what's weird with D? Correct solutions are getting wrong answer!

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

What was the 4th pretest of E about?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    sorting by bi > bj, ai < aj not ai > aj

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

      But why the order of a matters? Doesn't the prefix length where we search for the maximum depend only on b? Since any processed aj lesser than b should be ok.

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

        Yes, it does matter. Unfortunately, I only realized it in the last 2 minutes of the contest. Consider rings with the same b, then we should end the segment with the smallest possible a so that we can use more rings later.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        This order matters because, since a smaller ai can cover many more rings to come, hence, for same 'b', a ring with smaller 'a' should come later, so that it adds up to a greater dp value. Otherwise, your answer can be lesser than it should be.

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

        Thank you!

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

      Couldn't figure it out till the end,was checking my segtree implementation for every WA. Anyways, it was easy but good problem.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When you about to click submit button for D and the contest ends. Hope my solution was wrong.

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

With some Arabs praying and some other people sleeping or working Codeforces was deliciously responsive today! Thanks!

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The test should be at most 256 kb .

Then how can i hack o(n*m*k) solutions at C or o(n*l) solutions at D?

→ Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Looks like the Div.2 rank.1's solution was written by multiple people.

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

    ha ha... 5 codes and 4 different templates :p They could've atleast used the same template.

    → Reply
»
8 years ago, # |
  Vote: I like it -42 Vote: I do not like it

My request to feldsherov, ch_egor, halin.george, ipavlov, GlebsHP and KAN

Please look into D. Something's wrong with CF server!

Here's proof

http://mirror.codeforces.com/contest/777/submission/24975275

http://ideone.com/Mxgyyt -> exactly same node, not even a character has been changed. You can compare diff if you want.

Results are so different!

I don't want to lose points because server's fault. Please look into it!

Thanks!

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

    It's not server's fault. You have UB somewhere.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      No. I have checked with custom invocation. My array len[] is getting incorrectly assigned inside insert function.

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

    You are blue, but u talk like a complete newbie. By now, you should know that compiler versions differ on different Online platforms, and thus produce different outputs.

    Don't u feel like taking a second off and thinking about what may have gone wrong before blaming the CF server and taging all admins ?

    This is sheer stupidity, and complete newbie attitude. How many times have we seen this same query from multiple multiple people ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      I challenge you to find a UB in my code! If you do, then you can call me newbie :) Deal?

      If you can't find bug, then you by default admit I am right, and I should get my ratings back.

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

    You used the memory returned by malloc without initializing it, which may behave differently by environments.

    → Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Anyone else solved E with sorting and a stack? I can explain my solution if there is interest.

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

    Really? How? I used segment tree + heap, but I'm pretty sure BIT can be used instead of segment tree.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +11 Vote: I do not like it

      Well, here's a description of my solution:

      First, you sort the disks in a descending order, prioritizing the variables in the order b, a, h. (Note: my code actually swaps the names of a and b) Then, you go through the disks in the sorted order. You remove as many disks as you need to from the stack, until you can place the currently processed disk on top. You maintain the current total height of the stack, and also a maximum achieved height. The maximum height is the answer.

      I couldn't come up with a proof for this, but neither could I come up with any counter-example, and it surpassed all the tests. It just felt like it could work.

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

        I also have no idea why that works :)

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        I was 30 minutes late to the round. I solved from a fake id. I did this way :)
        This is not cheating :P I didn't submit from multiple id's :P

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

        I am sorting according to outer radius (bigger outer radius first).If outer radius is equal ,then sort by inner radius (again bigger inner radius first ) . Now let's say I have kept two data in my stack for every element (the inner radius and the height) . I maintain a global height variable 'gh'. What I do in every step is that I pop the stack elements till I get the top of stack element whose inner radius is lesser than the current element's outer radius.And then I come out of the loop and push the current element on the stack. In every push and pop operation I update the global height variable gh. And in every iteration of loop I update the final answer.

        Why this would work ? Everytime one pops an element whose inner radius is greater or equal to the current element's outer radius , it's guaranteed that the popped element can't be used in the future as we have already sorted by outer radius so the element's coming later on also won't fit on top of this ring.

        Complexity : NlogN for sorting and N for the main loop with stack operations.

        My solution

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

    same here :)

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The first time I have solved 4 problems.

→ Reply
»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

My skill is like Petr's or tourist's when they were in 6th grade.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A: AC

B: FST (WA)

C: FST (TLE)

What happened to my brain?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E with segment tree?

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

    Compress the inner and outer radiuses so that all radiuses are less than 200000.

    Sort all the rings by outer radius in the decreasing order. In the case of a tie, sort them by the inner radius, also in the decreasing order.

    For each ring, calculate the maximum height of a tower with that ring on top. This is obviously the height of the ring + maximum height of towers where the top ring has inner radius less than the outer radius of the current ring. Solution with segment tree becomes obvious now.

    → Reply
»
8 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I am shocked by the programs of THE RK1. I don't think a people will code in more than FOUR different code styles. I don't mean he has cheated,just curious.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +38 Vote: I do not like it

I know a little about the rank 1[user:Mr.Stream] but I know he is about 60 years old. What an unbelievable achievement!!! Could i make friends with you? Thx!

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

    you will make friends with 4 people QwQ

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

    Although the rank 1 is used the name of XianYou Xu,but I guess he is not the 60 years old man,maybe it is just a joke by his student.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

I'm too stupid.I use memset and strlen() in the for loop.And I got TLE in C and D

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Contest was easier than usual, D was little easier than C.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

About the Rank 1...

There was a legendary man called HangZhou Blade Master...

and now you see that...

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

Actually i can't why My E Programme TLE ON 13..... And i want to say congratulation to rk1[Mr.stream]

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

D is the worst question, why is it D, I think A is harder than D, liked solving C. Why is it like that.

→ Reply
»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

A shoutout to all those who stumbled at pretest #4 in problem E cuz of the sort :D

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When can we see the solutions？

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Could anyone please tell me why my solution on E got a Wrong Answer on test 39? I tried to solve it by using set and multiset instead of a segment tree,but it failed. Is it possible to solve E this way?Thank you! Here is my solution : http://mirror.codeforces.com/contest/777/submission/24972634

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

    I came up with a group of input to prove my code incorrect. And I found the elements I intended to put into the set actually failed to be inserted. Can anybody tell me why?

    Here is the data:

    5

    2 3 1

    2 4 1

    2 5 1

    2 8 1

    1 2 1

    The expected answer is 4,but I got the incorrect answer 5.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some interesting bug I discover. So my submission 24970450 got wrong answer on pretest one. But when I run it on custom invocation, I got the same answer.

#b

#big

#big

Whereas the output from the judge is

#b??

#big

#big

I know the error comes from my failure in resizing the string, but shouldn't the custom invocation gives the same output as the judge?

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

    I guess, that "??" is just to show, that there are space characters. In custom invocation there are 2 spaces instead of "??"

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

      but why does whitespace matter when u print? i can always print excess whitespace at the end of the line and still get AC

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

    '\0' and ' ' are different.........

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

      that should make my code even more correct. cause cout will automatically ignore everything after '\0'...

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

        char[] and string are different. string won't ignore '\0'.It records the length directly.

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

          read link

          It says there "This function overloads operator<< to behave as described in ostream::operator<< for c-strings, but applied to string objects."

          If you dont believe me, try writing something like:

          string str = "Chestnut\0Zun";
cout<<str<<endl;

          the result would be just Chestnut.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 3   Vote: I like it +3 Vote: I do not like it

            char[] ends with '\0',so when you convert char[] to string,it will only convert chars before '\0'.

            You can try this

            string str = "Chestnut-Zun";
str[8]='\0';
cout<<str<<endl;
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              ok, looks like i am wrong then. This is indeed interesting, I got ChestnutZun when I print to my terminal(which looks like '\0' being ignored) but I got 4368 6573 746e 7574 005a 756e 0a when I print to a file. Do you have any idea why?

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

                Maybe '\0' was ignored by your terminal.It looks like a space on mine(Windows cmd).

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

                  i run it on my terminal, cf and ideone though.all of them ignored '\0'

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

                  most of browsers ignore it too..... Custom invocation and online ide don't escape '\0',but submissions page do....

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

                  oh ok, thanks.

                  → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is it possible to use fenwick tree instead of segment tree for problem E? I'm got AC with segment tree but WA with fenwick. However, I've used fenwick on prefix RMQ problems before (i.e. when we query for prefixes only) and they've all passed. So now I'm wondering if it's possible or not?

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

    24965518

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

      Maybe this is a stupid question, but why was it necessary to group a and b into the same array and operate fenwick on that array? Wouldn't it be correct to update on the indices of the given array from input?

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

        The values are large enough and distributed randomly, so maybe this is a stupid question, but how can we use indices instead of real values?

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

          Maybe my algorithm is stupidly wrong, but this is what I did so far 24985290. Code is easy to read IMO

          → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the complexity analysis of my solution to problem C. Submission Link

My approach was to store all the increasing sequences in in each column ans push the starting and ending points int the map, along with size of sequences and the column in which it occurs. I also store the length of increasing sequences in "pts" vector. This vector is then sorted and duplicates removed from it. Now, for a given query, I simply iterate for all possible length >= (r-l+1) and check if I can get an answer from it. For a given "j", the answer exists only when the pre-computed range covers the entire length. This can be broken down into 3 cases (Similar to linear inequalities). If answer is found at any point of time, I stop the process else I brute force for all possible values of "j" and all possible positions in the matrix.

I think this solution of mine can give TLE on some cases where number of answers "NO" is very large. But even I was not able to come up with a test case where my solution fails. (I have tried this technique in few questions earlier too, but never failed). But still can anyone help me in analysing the complexity of my solution. ?

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

    Yeah, This does seem like it should have TLE'd. Since your query answering time can possibly be linear. So your complexity should be n*m*Log(n*m) + n*m*k

    Former is for the preprocessing on finding non decreasing sequences, while latter is for query answering. As for each of the K queries, in the worse case you might have to iterate through all of the n*m (max possible number of sequences) to find your answer.

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

      Now, I feel the complexity analysis can go as follows. The are sqrt distinct values below given N. So, in most cases, it perform query in O(sqrt(n)). But there is one particular case where it will TLE. The case is as follows. All the columns should be strictly decreasing. So cnt in this case is 1 everywhere. Now, if each query is (n, n), then k in my case will be 1 and I will have to iterate through each of the (n-1)*m grid points to tell the solution.

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

        I don't get how you got sqrt distinct values ? sqrt(n) distinct values of what ?

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

          Number of distinct values in "pts" vector.

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

            Only iterating distinct values >=(r-l+1) isn't gonna get you the answer right ? You need to know the starting point too. So in the worse case it is still n*m*k right?

            Even if for each distinct size length the list of starting indices is sorted so you can binary search for the query start. It still adds another Log factor to the sqrt, which shouldn't pass the time limit.

            → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There has been some time since a saw sneaky pretests like these. They were all really light weighted and I forgot how painful it's to discover it after the contest is over.

Yesterday I was Specialist, today I'm sad.

=(

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What's about announcing the winners of the contest?

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

    It's annoying when you are in Top 5 of Div. 1 participants, but author announced only winners from Div. 2.

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Waiting for the editorial! Someone please tell me how to do problem C??

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    My solution solves the queries offline.

    For each row x find the minimum row i, such that the interval [i..x] on some coloumn is non-decreasing.Then iterate through all the queries which end in x and if i < q[x].l , then the answer for the query q[x].order is "Yes" , else it's "No".Thus the complexity is O(n * m + k).

    Check my code for better understanding.

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

About problem E. Many people thought why greedy solution works. The answer is simple: tests are weak.

I wrote my greedy by sorting on bi in non increasing order and ai in non decreasing and failed pretest 4. Then I changed the order on ai to be non increasing too and it passed. I was angry that I did not notice that during the contest. Here is the submission: http://mirror.codeforces.com/contest/777/submission/24979922

I did not notice that property, as it does not work. Here is the counter example, where sorting by ai in non decreasing order gives a better result:

2
2 2 3
1 2 3

The answer is 6, but my program returns 3. It is a pity that these tests were so weak and so many incorrect solutions to the hardest task were accepted.

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

    This is an invalid input because bi must be greater than ai.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Right. In that case greedy works as you would be always able to cover all coverable ai, with bj.

      Edit. How to solve the task with ai <= bi?

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

        Note that if we place some ai = bi ring, we cannot stack any rings more on it (contradiction: bi >= b_(i+1) > ai = bi) So first we solve the problem with ai < bi rings, and process ai = bi rings later.

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

    I think Greedy Works always :)
    I faced a nearly same problem as you
    24985372 WA on test #22.. Using >= in sorting.
    24985387 AC only removing that = sign :(

    But I don't know why... Shouldn't I sort in Non-Increasing Order?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for problem E gave WA, but I can not understand what I did wrong. Here is my approach:

  1. Sort the rings with respect to 'b' in descending order.

  2. Now consider the rings in the sorted order.

  3. For the ith ring, get the maximum height achieved by i-1 rings with 'a' less than 'b' of the ith ring (used coordinate compression and segment tree for this).

  4. Add the above height to the height of the ith ring and store this value for the ith ring.

  5. Maximum achieved height by all rings after all of them have been processed is the answer.

Link to the solution : http://mirror.codeforces.com/contest/777/submission/24974400

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

    click

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks...but now I dont understand why Pretest 4 did not cause a problem for me. My solution failed on test 20.

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

        I think because in that test a's are sorted initially in correct order

        → Reply
»
8 years ago, # |
← Rev. 10   Vote: I like it 0 Vote: I do not like it

UPDATE: Sorry...wrong thread...it should be under round 402

http://mirror.codeforces.com/blog/entry/50658?#comment-346176

→ Reply