vovuh's blog

By vovuh, history, 4 years ago, translation, In English

UPD: Pay attention to the changed start time of the competition.

<almost-copy-pasted-part>

Hello! Codeforces Round 627 (Div. 3) will start at Mar/12/2020 16:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

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

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

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

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

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

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

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

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD2: Editorial is published!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

Does this means that the problems haven't been decided ?

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

    No, Because it is almost-copy-pasted-part

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

    May not. I think it's just a general idea so that almost every contest could use this template. ^-^

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

Which contest coincided with the original timing?

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

»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Who else is hyped for Div 3 because can't get good rating from Div 2?

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

What does mean by "almost-copy-pasted-part"?

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

    The "almost-copy-pasted-part" is almost equal in the announcements of most contests

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

So excited for first contest. Good luck everybody!

»
4 years ago, # |
  Vote: I like it -42 Vote: I do not like it

How was your Holi celebration ? Was anyone not able to play due to coronavirus threat?

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

    So many downvotes :( . I haven't asked anything wrong :( .

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

      your question was right but on the wrong platform.

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

2 hours in Div 3 and 4 hours in Reply Code Challenge, it's going to be an exhaustive day.

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

Hope that I can solve A-B-C.

Good luck guys <3

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

well,is there anyone know what's the name of the other contest(1.5hours later) after this contest?

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Hope to become expert after this round

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

I hope to get blue in this contest

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

I don't think i can solve over two problems...

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

    if you think you can't, so you can't.

    Believing in yourself is the first step to success.

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

Hope problems will not be indirect like this

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

    Well, you can jump through the centre.

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

      Ya I can for that I require wings of Advanced mathematics and data structures. Anyways Good Luck to everyone for the contest.

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

Bad luck for me becoz i can't attend this contest.

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

.

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

Hope i will be green after this round :))

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

I use this site during contest :)

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

I got logged out 2-3 times during contest. Did it happen to anybody else or problem at my end?

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

    Same here :(

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

    Glad to see I wasn't the only one who faced the same issue.
    Made me wonder if my account got hacked or something :/

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

    Yes,this happened with me also. Maybe a coincidence, but it happened mostly when I clicked submit button.

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

    Me too. I thought it was my browser problem or something like that and erased cache and it happend again... :(

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

    Same to me ((

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

I feel it difficult to understand some of the problem statements,does anyone feel the same?

»
4 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it
  • A Done
  • B Done
  • C Done
  • Me Done
  • Nice Contest
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good to see that vovuh is the writer.

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

The problems are too easy so that more than 500 participants solved all the problems

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

Guys,I have a problem! do not have a point of 1900 or higher in the rating Is that means standings in contest is different from your rank which is the final standings?

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

    The contest will be rated for those participants who have a rating below 1600. However, participants with rating greater than or equal to 1600 can participate unofficially. Separate standings are available for official and unofficial+official participants.

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

During the contest, I automatically got logged out from codeforces. I had two tabs of codeforces open in firefox. When I tried to submit I got to know I am not logged in. This has happened thrice. Is it normal/minor bug or there is some other problem ?

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

For those who cannot understand what is subgraph and subtree. Click :(

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much for the rating friendly contest

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

How to solve D ;-;

My approach
My source code

Found Mistake: (wrong formula) cout << 1LL * n * (n + 1) / 2; -> cout << 1LL * n * (n - 1) / 2; Found Mistake: (integer overflow) ll res = q * (q - 1) / 2 + q * zero; -> ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero;

AC Code (Spoiler warning)
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can use binary search. create a diff array such that diff[i] = teacher[i]-student[i]. sort this array. at a particular point i calculate how much you'll need to compensate for when you choose j. e.g if teacher[i]-student[i] = -2. then we know we need diff[j] >= 3, so as to make teacher[i]+teacher[j] > student[i] + student[j].

    you can easily binary search this value in diff array.

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

    Let $$$c_i = a_i - b_i$$$. Now you have to count the number of pairs of $$$c_i$$$ with the positive sum. It can be done in $$$O(n log n)$$$ with binary search.

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

    Create an array of differences of a[i]-b[i] then use lower bound to find good pairs for negative numbers and zero numbers and for positive use binomial coefficient (ncr).

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

    I used PBDS.

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

      how?

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

        Let's just iterate over the array from the start, and since we need to find unordered pairs, so for a particular i, we need all elements before it such that: ai — bi > bj — aj or Let's denote bj — aj as val, then we need all such elements where : val < ai — bi So PBDS on pair of elements acts like a multiset with additional feature ,giving count of elements less than x too.So use that function for each i and get count of elements less than {ai-bi-1,inf}, and add it to answer and insert pair {bi-ai,i} to the pbds.

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

        Use PBDS as a multiset (comparator less_equal). Traverse from the end of the array and for each index, increment answer by order_of_key of $$$a[i]-b[i]$$$ (basically index of upper bound). Then insert $$$b[i]-a[i]$$$ in the PBDS.

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

          Yes, yes, yes, shooting pigeons with a cannon — that's my style! 73043201

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

      Can you share your code? I tried using pbds, but it gave wa on test 6.

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

        You can look it up in my submissions and if are not permitted, then add me as a friend and then look it up in standings submission. Sharing code here will scribble the comment section.

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

    It can also be done with sorting; if you have a sorted array $$$c$$$ and you want to know for particular $$$i$$$, how many $$$j$$$ satisfy $$$c[i]+c[j]>0$$$, then you can decrement $$$j$$$ from $$$n$$$ down to the first index where $$$c[i]-c[j]<=0$$$, and count $$$n-j$$$. Then if you iterate over increasing $$$i$$$, this $$$j$$$ can only decrease.

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

    What is wrong with my approach ? ;-;

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

    problem is similar to inversion count, so used BIT tree to solve it, after compression.

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

    Let c[i] = a[i] — b[i]. Now we have to count the number of pairs with positive sum. Sort array c.

    Set two pointers, one at index 0 (pointer j) and the other at index n-1 (pointer k). In each iteration decrease k by 1 and find the corresponding index j, by running a separate loop within the previous loop. Exit when j >= k.

    Initialize ans = 0, and keep adding (k — j) in each iteration, i.e. ans += k — j

    Note that j keeps on increasing in each iteration. We do not restart j from 0 each time.

    Time Complexity: O(n)

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

    thanks for taking your time to write an explanation.

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

Can any one give a hack on the following approach for D?

Sort them by $$$a_i-b_i$$$, then use binary search to find last okay one.

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

    Gradually sort?

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

      Can you explain it further please?

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

        I think simply sort will TLE. What's your method?

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

          Pasting my code here: (ignore the stable sort part, using sort fails also) Link

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

            We need ai-bi+aj-bj>0 instead of ai-bi>aj-bj

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

    sorting them will change the order of the indices

    and in the problem you need $$$j$$$ to be $$$>$$$ $$$i$$$

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

      That doesn't matter, if you are counting all distinct pairs $$$(i,j)$$$ which satisfy some property, then this will equal the number of distinct pairs $$$(\sigma(i),\sigma(j))$$$ which satisfy the same property, for any permutation $$$\sigma$$$

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

    Make an array of Ai — Bi, sort it and binary search the right one for each. That's the solution I think.

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

    Maybe you can use the Binary Indexed Tree in value.

    First discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

    Then for every $$$i \in [2, n]$$$, calculate all for $$$j \in [1, i)$$$ which $$$b_j - a_j < a_i - b_i$$$

    The time complexity will be $$$O(n \log n)$$$.

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

Lightning-fast system testing

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

    There is a 12 hr hacking phase, after which system testing will begin.

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

Why, i kept logging out after few intervals ,throughout the contest??

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

How to solve E? Also, what is the name of the concept used in E?

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

    I believe it's called dynamic programming.

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

    Dynamic programming. $$$dp_{i, j}$$$ is the number of good times when we consider the first $$$i$$$ times ($$$0$$$-indexed) and did this $$$-1$$$ "operation" $$$j$$$ times. The answer is $$$\max\limits_{j=0}^{n} dp_n$$$.

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

      what's the meaning of the first $$$i$$$ times,I can't get it

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

        More correctly, $$$dp_{i, j}$$$ is the number of "good times" when we consider first $$$i$$$ values $$$a_i$$$ and used $$$-1$$$ $$$j$$$ times. Transitions are also pretty easy: if the sum of the first $$$i$$$ values $$$a_i$$$ is $$$s$$$ then $$$dp_{i + 1, j} = max(dp_{i + 1, j}, dp_{i, j} + [(s - j) \% h \in [l; r]])$$$ and $$$dp_{i + 1, j + 1} = max(dp_{i + 1, j + 1}, dp_{i, j} + [(s - j - 1) \% h \in [l; r]])$$$. $$$\%$$$ is modulo operation ofc.

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

    state are index and modulo

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

in problem D , solution of 10^10 was giving TLE for test case 12,althought time limit was 2 seconds, http://mirror.codeforces.com/contest/1324/submission/73076815 i thought 10^10 solutions can run in 2 sec

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

    I think a bound of 10^(7-8) is good for 2 secs, 10^10 is taking it too far.

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

Downvoted because the sentence in problem E is completely unreadable.

The sentence "The i-th time he will sleep exactly after ai hours from the time he woke up" and "Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours." sounds inconsistent.

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

for problem D, i Stored two arrays one array has (ai-bi) values and the other has (bi-ai) values and i ran a nested loop from i to n-1 & j=i+1 to n-1 and counted the number of elements that are greater than current element. what could i have done better?

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

    In fact, you can first discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$.

    Then use a Binary Indexed Tree to count all the values.

    The time complexity will be $$$O(n \log n)$$$.

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

    Use a binary indexed tree.

    Insert $$$a_i - b_i$$$ into it after checking how many elements there are before $$$i$$$ which satisfies $$$a_j - b_j > b_i - a_i$$$. Discrete all $$$a_i - b_i$$$ and $$$b_i - a_i$$$ first thing first.

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

UPD: Sorry for the comment. I didn't think much, it's my bad.

Appologize for the round, sorry.

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

    Do you write is serious? The "subSTRING" problem, as you say, is not "more interesting" and can be solved in $$$O(n)$$$ considering $$$3$$$ or $$$4$$$ consecutive characters.

    D — data structure problem? The problem "sort the array and do (lower bound or binary search)" is data structure problem?

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

      Sorry for that. I didn't think too much.

      I am terribly sorry for the words.

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

      How to "sort the array and do (lower bound or binary search)"?

      It seems very interesting.

      I used binary indexed tree after discretion.

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

    Can't the substring problem be solved in O(N)?, I did that only after I misread the problem! :( Just check all "3 consecutive characters substring" and "4 consecutive characters substring".

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

Interesting fact for myself: Everytime people celebrate a rating-friendly contest, I lose ratings; Everytime people complain about toxic problems, I gain ratings.

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

You did not think that the tasks are too simple even for div 3 ?)

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

    Speed is really need. lol

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

    vovuh made them easy to please div3 ppl

    here

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

      Haha, that's funny. I don't know how to prepare "good" round. I prepare slightly hard round, people say "omg that's div.1, not div.3!". I prepare slightly easy round, people say "loool 2ez4me that was not even a round". I don't know what to do.

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

        Lol. You should ignore comments made by candidate masters on div3 rounds. A candidate master saying div3 is easy is like a pupil / grey guy saying div1 is hard.

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

        actually, vovuh, you did well, i really appreciate as most of div.3 contests are made of you

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

        Don't coordinate anymore divs 3 rounds )

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

        Actually, vovuh, you are the best. You prepare quality Div 3 contests, and I enjoy participating in your contests. Also, I participating out of the contest; I get to learn new concepts and techniques from your contests. I hope you keep up this great work and keep contributing to more such awesome contests.

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

        I really liked D problem of this contest. I've been focusing on pbds/fenwick last 2 weeks and this problem really put my knowledge to test. I like how I saw 3 different approaches on this problem(bin search, pbds, fenwick and treap). The problem really managed to capture the creativity of the community. Well done, our Div.3 King

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

        Great job vovuh, don't give in to the hate. As it is, it's hard and time consuming to create problems and test cases, let alone deal with criticism such as this.

        Personally, I think this is a good level of difficulty, otherwise how do we differentiate between Div 2 and Div 3 problems. Once in a while, problems in Div 3 are easier compared to other Div 3 contests — but I think many people in Div 2/Div 3 enjoy the opportunity to solve a few problems (that are in reach and where we can apply what we've learnt recently) and then learn from the other unsolved problems.

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

    I think that this is the perfect difficulty level for Div 3. Myself being an Expert (Rating: 1734), I was only able to solve A, B, C, D. So, I believe that it justifies my claim.

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

Speedforces

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

Tried E for the first time in my life. Got wrong answer test 40! I think I made a silly mistake but couldn't figure out yet. My submission: 73079617

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

    It failed for me as well, test case is involving l = 0 I guesss, and I had counted t = 0 case, which is wrong. Removing that gave me AC.

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

Why these two submissions using PBDS for problem D got different verdicts vovuh please look into the matter.

Correct SOlution:-73082017 Rejected Submission:-73079109

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

    It's because, in your case, it couldn't contain same elements.

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

During contest I was logged out several times. Does someone know why?

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

It's quite easy. Even my i got more rating, but i think i wouldn't satisfy with those.

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

Why I am getting ILLEGAL CONTEST error while pushing "hack it"? Please fix

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

    you must go to submission link and then press hack it there instead of hack from status

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

Hello? I'm a bit curious about how to solve F, can someone help me? Thanks

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

can someone please explain the reason for TLE in my submission of E my code -link

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

    Because at last where you have done dp[id][sum][f]=ans, your value of sum is changed, but your dp[id][sum][f] should use original value of sum not the updated one.

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

1 5 2 2 2 2 4 why this will give yes in A?

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

    NO, since all elements must have same parity (either odd or even), then only answer can be "YES"

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

    Is it a full test or a single case? If it is a full test(i.e. 1 represents number of cases,5 represents number of columns) then simply put blocks in column 1-4 If it is a case(i.e. there are 7 columns),the answer is NO.

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

+104 -> +8, thx for B pretests, goodbye expert:(

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

    exactly same problem.... :/ why would they create such weak tests?

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

    Actually, it means we should be more careful, and find out all special cases.

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

      the thing is , the hacks arent even special cases, the hack could have easily been in the example test.

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

        If you didn't consider something, for you it was a special case I suppose.

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

          how did you figure out your rating change?

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

            Chrome extension "CF-predictor"

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

              Oh thanks. I can't see the prediction, I guess I was supposed to have it before the contest too?

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

Hack for B?

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

!!NEED HELP!!

My solution for problem-D : 73076688

According to me,it's complexity nlogn, but i m getting time limit. Can anyone explain why it is happening or where m i wrong??

TIA

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

    sum+=(ll)distance(it,ms.end()); has linear complexity -> O(n^2logn)

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

      If I hack my own solution, then will that be an advantage?? like my scores would not reduce

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

        No, you'll just hack your own solution instead of someone else.

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

quite sad that my solution for B got accepted in the first place , was it intentional to make the test cases all weak for only an odd length palindrome / 2 different numbers only? would've solved 5 problems in one contest for the first time.

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

Hi, can anyone explain why this solution 73084554 is giving WA. While this solution works 73037149 by tmwilliamlin168. Thanks in Advance!

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

Problem B $$$O(N)$$$

73087070

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

I liked this contest vovuh. Good job. I'm interested to know your thoughts on the difficulty levels of $$$D$$$ and $$$E$$$ if this was a Div $$$2$$$ contest. Do you think $$$D$$$ is harder than $$$E$$$ ?

How to solve $$$F$$$ ?

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

    I think D is between the div2B and the div2C, while E is between the div2C and the div2D.

    However, you may just wait until when these problems are recorded in PROBLEMSET and the difficulty of them will be visble for you.

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

      I think segment trees are too difficult to be asked for $$$B$$$. It might be a $$$C$$$.

      Can you please tell me how to solve $$$F$$$ ?

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

        In fact, you don't need segment tree for D since the binary search is enough for it.

        For problem F, I apply DFS twice on the trees.

        In the first DFS, I regarded no.1 node as root and regarded the trees as a rooted trees. In this DFS, I get the correct answer for no.1 node.

        In the second DFS, I started my DFS from no.1 node and calculated the answer of other nodes in my traversal.

        For more details ( since I'm poor in English but good at C++ ), you can look up my code.

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

          Nice ! I never thought of binary search for counting inversions ! :)

          My main doubt was in the second DFS. Thanks !

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

          I implemented the same algorithm in Java, but failed test case 3. I couldn't figure out why it fails. Can you help me? My submission is: 73110580

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

            It seems like ts3 is just a random tree whose node is all black. So you can just make a small test to see what happens in your program.

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

              My tree building logic was wrong, I need to build a 0-rooted tree recursively, thanks anyway!

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

    Root the tree arbitrarily and let $$$dp_x$$$ be the answer for $$$x$$$'s subtree. We can do this with a single dfs.

    But then $$$dp_x$$$ won't necessarily have its full answer (because we didn't consider the path through $$$x$$$'s parent). So do a second dfs and for each parent node $$$y$$$ update each of $$$y$$$'s child's $$$dp$$$, (child may benefit from path via their parent $$$y$$$), but be careful to not to over count that child's contribution from $$$dp_y$$$.

    for clarity you can see my submission: 73067648

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

      Ah ! The overcounting is tricky ! We should subtract only if $$$f(c) > 0$$$. The reason is that if $$$f(c) > 0$$$, then we never added $$$f(c)$$$ to $$$f(v)$$$

      Thanks !

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

it is the first time i tried in E

but i got WA on 40

any one can help me why it is wrong

https://mirror.codeforces.com/contest/1324/submission/73078402

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

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

Can someone please explain to me the DP state for problem E?

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

    Before considering sleeps #$$$i,i+1,\ldots,n$$$, suppose you last slept at time t. Then under these conditions, dp[i][t] is the maximum number of good sleeps among $$$i,i+1,\ldots,n$$$. The question asks to find dp[1][0].

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

Can B be solved in O($$$n^2$$$) will it pass?

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

    i think. YES, as n=5000

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

    Yes, but if you have a constant factor $$$a$$$ you will have runtime $$$O(a * n^2)$$$, which may TLE because worst case scenario you will do something like $$$a * 5000 * 5000$$$ operations which may not be executed in time (I hacked a couple ppl with this idea)

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

Can someone explain why the order (i<j) won't matter in problem D ??

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

    i<j simply means that pair (i,j) and (j,i) are same. so you can ignore this statement and divide it by 2 at last to consider it only once.

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

    It is another way of telling that pairs (i,j) and (j,i) are the same. And they have to be counted as 1.

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

Is problem F a classic problem? Because i notice that many people write similar code in their dfs. If it is, please tell me. Thanks is advance :)

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

Could someone help me figure out my mistake in Problem E 73091842. Thanks in advance.

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

vovuh you are great author your problems are amazing

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

Hack case of B . 1 3 2 2 2

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

how is this O(n^2) solution timing out on B for 2 secs??.Link

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

    It seems like you are using map<int, int> which takes $$$O(\log n)$$$ time for adding and looking for element. Also, std::map is especially slow (big constant factor) so your solution has time complexity $$$O(n^2 \log n)$$$ with big constant factor.

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

      Ah, wow. i always thought map was constant access and insertion. thanks btw

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

        I think what you want is unordered map which uses hash. It has constant access time on average (but can be up to $$$O(n)$$$ worst case). It also is quite slow since internal structure is somewhat complicated. I mean, don't expect something like a array-access speed.

        Also, since it uses random, it can be hacked if some experienced coder tries to craft specific testcase to kill unordered map.

        I think there was a good blog on CF about this (and also how not to get hacked from that) but I can't find it now.

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

      So this should time out too? 73028508

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

        I don't think so. Your code is performing $$$n$$$ map access operations which make the whole complexity like $$$n \log n$$$. The code originally asked was using about $$$n^2$$$ map access.

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

          Thanks. I was misinformed about the access time of maps, now its clear.

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

    I think map takes O(log n) time for searching thus complexity goes to O(n^2logn)

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

When it's my first time to solve 4 problems and I've a new high rank:

HACKS:

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

Nice Contest! My solutions: A. Check the parity of all elements. If the parity is same, then the answer is YES, else NO B. Its always enough to check for palindrome sequences of length 3. So considering each element as center, check if the right and left parts contain atleast 1 element in common. C. its always beneficial to use R and not L. (why? bcoz with L you can only reach back to reach some R, which anyway you would have reached before reach the cell with L). so find the largest gap in reaching a R. D. Compute ci = bi-ai and sort this array. Then for each ai and bi count the number of elements in array c less than ai-bi. Also make sure to consider the edge cases where you have counted the same element again. E. Use dp. The state is (i, time), where i is the day (or the ith sleep) and time is the current time. Write transitions to each of ai and ai-1. F. Assuming you run bfs from some initial root node, Compute max(wi-bi) for each node i in its subtree rooted at i. Now we need to compute the value in parent part. This can be done using tree rerooting technique.

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

Could someone help me with my problem E submission. I am not able to figure out the mistake.Thanks in advance[submission:73096035]

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

    Corrected code 73127806

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

Can anyone tell me why this 73097950 passes and this 73098017 does not ?

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

    they will give different output when v contain same value more than once.Check this 3 6 6 6 2 2 2

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

![ ](2-24510-trollface-deal-with-it-troll-face-png)

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

I got TLE error during contest instead of WA! even after the contest when I was submitting correct answer I was getting TLE. I got frustrated and then copy pasted solution of another user then also I got TLE. Also, I was logged out multiple times automatically during the contest!! solution link: https://mirror.codeforces.com/contest/1324/submission/73104474

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

Will there be any system testing after the hacking round is finished??

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

    Yes

    All of the AC solutions will be rejudged with original tests and successful hacks once the hacking phase is over.

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

Why I want to hack a solution and it shows Illegal contest ID ?

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

    Try to hack solutions via the Status page instead of the Standing Page

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

      Ok I get it. Appreciating your help !

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

Can Somebody please explain why this solution is not giving compile time error on pretest cases and arbitrary cases on offline compiler Solution for Problem 2

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

When system test will start?

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

What's wrong with my solution for E problem? 73075794

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

I am wonder that when the system test will begin.

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

Anyone who solved problem D using two pointers? Please explain your approach

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

Why did it keep on logging out during the entire contest? It was so irritating whenever I was to submit my solution It logged out :(

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

Each time Vova sleeps exactly one day (in other words, h hours).

What a lousy problem statement for E.

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

When will the ratings change?

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

I have a solution on F that seems to be different from everyone: Let's hang the tree at vertex 1 and calculate dp[v] — the maximum answer for the subtree of v. This DP solves the problem for the vertex v if the root is the vertex v. How do we fix this? Let us remember when recalculating the DP for root 1 which vertices we included in the answer. Then we’ll introduce a push push that will push dp[v] into dp[u] depending on the benefits. That is, if our vertex u was included in the answer, then we push dp[u] = max(dp[u], dp[v]) into it, otherwise dp[u] = max(dp[u], dp[u] + dp[v]) The answer for vertex v is dp[v]

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

    I did this too (submission towards the bottom) but I think it is more or less the same as everyone else. It just condensed the if/else that others used into a smaller form.

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

      I do not completely agree, because the majority (70-90%) passed the "resuspension" technique for O (1)

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

When will the rating be changed?

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

    You need to wait for system test first.

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

      But Hasn't the system test finished?

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

        I think so as it says final standings.

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

          But all the finished matches said final standings.

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

            You can check the submissions' judge time in standings page to see whether the system test have done or not.

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

I kept getting logged out of my account. Did this happen to anyone else ? Why did it occur ?

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

Is it rated?

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

    I think it's rated. If it isn't rated, they will declare it.

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

Is the system testing done??

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

when will our rating change?

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

    I hope it changes soon, I have refreshed my profile page atleast 50 times to see if I reach expert after the rating change.

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

      I have lost count of the number of times I refreshed my profile. xD xD

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

        Yeah me too XD. I was so excited after solving 5 questions for the first time that I couldn't sleep last night.

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

Hacking phase finished more than 6 hours ago but no system testing till now!

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

How long does it take to give rating????

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

    System testing just started, I think it'll take an hour more

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

When will the ratings change?

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

Maybe they are thinking to do system testing together with round 628. It happened once afaik.

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

waiting for the rating change...

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

Why another system testing?

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

Testing is stuck at 78%

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