Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

vovuh's blog

By vovuh, history, 2 years ago, In English

Hi everyone! I'm glad to invite all of you to participate in Codeforces Round #574 (Div. 2) which will take a place in Jul/17/2019 17:35 (Moscow time).

This round is based on SIS team contest. You will be given 6 problems and 2 hours to solve them. This round will be rated for Div. 2 participants. In other words, this round will be rated for the participants with rating lower than 2100. As usual, participants from the first division are welcome to join out of competition.

Problems was invented and prepared by Nebuchadnezzar, Kurpilyansky, meshanya, TsarN, sava-cska, ima_ima_go and kraborak. I am just a coordinator of this round, I made a small amount of work such as English translations and editorials. I want to thank Mikhail MikeMirzayanov Mirzayanov for amazing systems Codeforces and Polygon, all authors of this great contest, KAN and cdkrot for help with difficulties estimating and choosing the problems and my dear friend Ivan BledDest Androsov for help with round preparation!

Good luck everyone and see only green system testing messages! :)

UPD: The scoring is 500 — 1000 — 1500 — (1000+1500) — 3000 — 3500.

UPD2: I would like to thank testers galloska, NatInTheHat and AlexPop28 for help and advices about the round!

UPD3: Editorial is published!

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

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

It is usually a good contest if vovuh is a coordinator. Good luck

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

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

Why some people participate out of competition even though their raiting is < 2100?

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

    It will be fixed.

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

      sir i submitted solution when 20-30 seconds remaining for problem D1 and D2 ,but it's not showing into mysubmissions please look into it.. i am on a very good broadband network, submit button was also working(not inactive) at that time. how it's possible??

»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

I hope to become cyan again.

»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Will vovuh surpass pikmike

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

I hope to become white after this contest.

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

I hope to become blue finally. :D

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

I see people hoping to improve their colors (ratings). But I hope to have no WS, more ACs and a lot of fun :)

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

Clashes with topcoder SRM 763!

»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Some codeforces round will delay the start.I hope this round will not be like this.

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

I'm noob so i wanna know what's the difference between div 2 and div 1 :D thanks

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

    Generally,div.1 is harder than div.2

    div.2 C=div.1 A

    div.2 D=div.1 B ....

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

    There are three divisions (the more digit the easier problems):

    • div3 — usually for pupils
    • div2 — students
    • div1 — high-skilled students, engineers etc.
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm sorry that I can take place.

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

    you're sorry that you can take place!!!!???? Hey everybody, I'm sorry that I'm alive lol :P

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

If i can solve Div 2 A,B,C regularly,can i ever become a specialist?

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

    yes, if u regularly solve 1,2,3 u can become specialist u can also get high rating in div 3

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

    Absolutely yes!

    And if you are lucky enough,you can even become an expert.

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

What is SIS contest?

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

What does it mean to coordinate a round ? What does the coordinator do ?

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

    Coordinator finds mistakes in problems statements

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

Will the pretests of problems in this contest be strong, like those in Educational Codeforces Round 68?

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

    I agree that Educational Codeforces Round 68 had very strong pretests, which made hacking very difficult.

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

    Oh, you are strong enough, and you won't be afraid of the strong pretests.

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

What will scoring distribution be like?

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

Please let me see my repay! ->Codeforces Round #574 (Div. 2)

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

This round clashes with Codeforces Round #574.

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

i will be cyan today....waiting for div3 vovuh (^.^)

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

    i will be master today....waiting for div1 vovuh (^.^)

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

    Challenge accepted :)

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

A friend is saying me every contest "I'm gonna be specialist this contest" but he keeps dodging contests. This time again. Should I block him on messenger ?

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

What is SIS team contest ?? Can't find any relevant info about it on dd

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

    SIS stands for summer computer school, so SIS team contest means team contest held in SIS.

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

500 — 1000 — 1500 — (1000+1500) — 30003500

Is it even div.2 ???

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

    Easy div1 :)

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

    Just one more div2D and this would've been a beautiful round with 2 divisions.

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

GOOd luc to all ! .. xd hope rating get

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

No Hackforces or Queueforces please!

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

Gray here I come!

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

    rating count begins from 1500 , if you perform well ,you can directly reach blue after first round, else you would be green

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

      Else you would be green ”. You forgot one else if that he might be cyan if he writes contest not very bad)

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

    Welcome to FairyForces :P

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

Sorry to say, but A is much to much text. That is not very motivating.

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

    I didn't even understand the problem. Why the english is hard

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

Nobody :

Me:

(5 mins before the contest): watching hunter_x_hunter

(contest begins) : reading problem-A...

(5 mins in contest) : still reading problem-A......

(10 mins in contest) : (yawning) still reading-A.........

(15 mins in contest) : watching hunter_x_hunter again

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

Most Div3 contests have better and harder problems. Typeforces strikes again.

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

is there someone else too or only me.

till 20 min reading problem a.

solved b in 5.

again reading a for another 10.

solved c .

again reading a.

solved d1.

now still reading a...

basically A ruined my mood .. :( .. what the question is saying. at one moment i thought of shut down and play pubg but b c d1 were easy ...

&& also share approaches for d2 and e after the contest.

Thanks.

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

    Exactly .... B should have been A , A question is supposed to be cakewalk right and I wasn't able to understand what it was saying for the first 10 mins ....

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

    oh shit i managed to solve only A after 40 min and got confused from B.

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

I think D2 worth more points. D1:750 D2:1750 would be better.

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

    Maybe there isn't too much difference if U think a lot about them:)

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

F: another problem that Wikipedia makes a difference

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

    So it means we can reduce the problem to querying the number of different directions of the directed arrows in a certain range. Didn't figure out this until the last minute of the contest.

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

Woah, how to solve E? Is it some observation on the recurrence, or simply data structures? :O

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

For E, why doesn't a segtree solution pass?

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

    Simply too costly, keep in mind that $$$n$$$ and $$$m$$$ may both reach $$$3000$$$.

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

      Do I have to drop two logs?

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

        Even one additional log into the $$$nm$$$ will cause TLE immediately. I tried.

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

          The proof of the pudding is in the eating. Thanks a lot.

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

            Best solution (based on std::multiset) with O(nm log(n + m)) asymptotic 57272696
            Just new / delete optimisation with small test generation analysis (weak test cases)

            but not at the contest time...

            UPD: This is just an example of how to reduce the execution time of a program.

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

          My solution using std::priority_queue has one $$$\log$$$ in its time complexity. Some other solutions with $$$\log$$$ also passed system test.

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

          I'm on the first page of fastest solutions with $$$O(nmlog(nm))$$$... Edit: my runtime increased by about 20% after systests so this statement is no longer true. It's still 420 ms though.

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

Can anyone share how to solve D1? I bruteforced it and got tle in tc7.

Also A took me so much time to solve like 3*(time req for B). It was really demotivating :(

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

    -First i solved examples on paper, then recognized pattern. Result=summation(f(a[i],a[i])*n

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

    My solution to D1 is:

    1. Work out how many times each digit appears in each position.
    2. Add the digits in each position.
    3. Work out the total by adding these up multiplied by suitable powers of 10

    I didn't get a solution for D2. I think the same process should work, but step 1 is more difficult.

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

How to solve D2 ?

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

    For $$$f(x, a)$$$ and $$$f(x, b)$$$, if $$$a$$$ and $$$b$$$ have the same number of digits, the effect of $$$x$$$ on the answer is always the same. The same holds for $$$f(a, x)$$$ and $$$f(b, x)$$$. In addition, if $$$a$$$ has at least the same amount of digit as $$$x$$$, the effect of $$$x$$$ on answer is always the same. We only need to store the frequency of number of digits.

    The contribution of $$$x$$$ would be like follows (take $$$x=1234567$$$):

    $$$12345670 -> 123456070 -> 1234506070 -> ... -> 10203040506070$$$ if it is $$$f(x, a)$$$.

    $$$1234567 -> 12345607 -> 123450607 -> ... -> 1020304050607$$$ if it is $$$f(a, x)$$$.

    $$$a$$$ has number of digits $$$1 -> 2 -> ... -> numberOfDigitsOfx$$$.

    To insert a zero between the digits, you can just use the *, /, % operators.

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

Problem D: So the digit combining function helped the students find the coordinates of the treasure?

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

Where am i wrong.Can someone please help? For C problem https://codeforces.com/contest/1195/submission/57227259

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

Why didn't you send a single announcement that you updated problem B statement? I didn't refresh and wasted a lot of time with it.

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

it make the chinese stay up late

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

Nice round! I solved two problem but didn't have idea of problem C. Does someone teach me how to do?

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

    -I solved with Dynamic Programming. for (i=1;i<=n;i++) { dn1[i]=max(dn1[i-1],a[i]+dn2[i-1]); dn2[i]=max(dn2[i-1],b[i]+dn1[i-1]); } cout<<max(dn1[n],dn2[n])<<endl;

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

    The main idea is DP. Let dp[i][0] be the best sum if we only take players up to position i and take the player in the top row at position i. dp[i][1] is defined similarly, except we take the player in the bottom row at position i. dp[i][2] is also similar, except we take no player in position i. We can then fill this dp table in O(N) time, as the transitions are relatively simple.

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

      simply 2 variables would have been enough i think?

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

        Yes

        x=A[0],y=B[0]
        loop(1,n){
        temp=x;
        x=max(x,b+A[i]);
        y=max(y,temp+B[i]);
        }
        
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use dp. let dp[i][j] be the max sum u can take till column i and u choose jth row {0 , 1} in current column. now transition will be either from i-1 or from i-2 because no point in skipping 2 elements.

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

      I don't get the exact logic of "There's no point in skipping 2 elements". I think I can get a feel that at any state we have two paths to go — one from taking just next element and the other is from taking next to next element but I can't prove it. I recurse for all the states with memoization but got TLE only because your logic works but I couldn't prove why?

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

        prabhat7298 there is nothing to prove in it.

        take this example :

        1 2 3 7

        5 6 8 9

        taking index — 1 based.

        suppose we are at column 4, and we choose element from row 1 that is 7. now we must choose a previous element from row 2. suppose u skip 2 elements and choose 5 from 2nd row. now to choose 7 u can go through 5 -- 2 -- 8 -- 7 . since the numbers are positive we will only add +ve numbers to our answer. if we skip two elements we can always form a ziz zag path. so it would be optimal for us to not skip 2 elements.

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

    You can use dynamic programming for that one.

    Let C(r, c) be the optimal cost to choose the team if we begin our choice from row r and have c individuals in each row. Then:

    C(1, 1) = H(1, 1) C(2, 1) = H(2, 1) C(1, c) = max(H(1, c) + C(2, c-1), C(1, c-1)) C(2, c) = max(H(2, c) + C(1, c-1), C(2, c-1))

    Once we've built our array, the solution is just max(C(1, n), C(2, n)).

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

    Thanks you guys, I will think how to do it with your tutoral. Hope me I will get accept :D

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

    You can refer to my submission here. It is an easy application of dp

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

I'm so sad if just 3 minutes I could've solved D2 ugh stupid bug lost 30 more rate

Edit : it was WA lol I'll never assume my solution is right unless I see the fukin accepted

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

After lot of searching, I found problem C at https://www.geeksforgeeks.org/maximum-sum-from-three-arrays-such-that-picking-elements-consecutively-from-same-is-not-allowed/ only to find out the code does't give correct output on pretest 2. Tried to fix it, failed.

RIP rating.

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

meme

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

Very good round!! First round to solve 4 problems. I usually solved 2 or 3

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

    I think it's better to solve few harder problems, rather then wasting time implementing easy ones. I haven't liked it -_-

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

    Congrats!

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

Is it possible to solve B mathematically? To solve this system of equations: 1. x(x + 1)/2 - y = k 2. x + y = n which gives y^2 - y(2n + 3) + n^2 + n - 2k = 0 and solve this quadratic equation for y. Then, check whether y fits [0, n]. It fails on the 11th test, what have I done wrong?

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

    Do $$$int(sqrt(...))$$$

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

    You can put $$$y = n - x$$$ which gives you $$$(x^2 + x)/2 + x - n = k$$$. It's quite simple to solve :)

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

    I did it same way. If n>=1e9 then sqrt(n) gives not an accurate answer.

    How i dealt with it:


    int mysqrt(int b){ int c = (int)sqrt(b); int r = max(0ll,c-10); int l = c+10; for (int i = r; i <= l; i++){ if (i*i == b){ return i; } } return c; }
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Standart C++'s sqrt() gives AC.

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

        Hmm, yes it does... But, anyway — sqrt isn't precise =)

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

          Ofc, but as condition says It's guaranteed, that for the given n and k the answer always exists.

          If it hadn't guaranteed, sqrt() probably would have got WA.

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

            Try to avoid using fractional types if it is possible to

            For example in this problem you can iterate over x from 0 to C and try each of them to fit your formula (here C is some constant that x will never exceed e.g. 10^5)

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

    Any other non-math solution?) my solution: 57211560

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

    Ohhh I see. My Equations were as follows :

    k = (n-x+1)*(n-x)/2 - x

    Where x was the number of actions where she ate a candy and n-x was the number of adding candy operations.

    So basically solve for x.

    I used binary search : 57215407

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    ll x = (sqrt(9 + 8*(k + n)) - 3)/2;
    ll y  =  n - x ;
    solve for x it is easy not for y, and obtain y as n - x;
    happy coding:)
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    x^2 + 3x -2(n + k) = 0

    its positive root will solve the problem. and it is a guarantee that it has only one positive root. so the answer will be unique. let its positive root is x, then answer will be (x * (x + 1)) / 2 -k.

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

can someone explain the first sample in D1 please ?!

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

    I think that you forgot f(45,45)=4455 also makes sense.

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

    f(12,12) = 1122 | f(12,33) = 1323 | f(12,45) = 1425 | f(33,12) = 3132 | f(33,33) = 3333 | f(33,45) = 3435 | f(45,12) = 4152 | f(45,33) = 4353 | f(45,45) = 4455

    Sum these up, you'll get 26730.

    Hope this explains :)

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

      oh shit !

      what got to my mind when i read this : $$$∑ni=1∑nj=1f(ai,aj)$$$ is

      12,12
      12,33
      12,45
      33,33
      33,45
      45,45

      really sad !

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

    f(a[0],a[0]) + f(a[0],a[1]) + f(a[0],a[2]) + f(a[1],a[0]) + f(a[1],a[1]) + f(a[1],a[2]) + f(a[2],a[0]) + f(a[2],a[1]) + f(a[2],a[2])

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

Couldn't solve D2 because I forgot to multiply by 2 :/ This really sucks

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

Lucky me.

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

Problem F,why the sample input different with the image.

3
2 2
1 2
2 1

but the image is:


------- | / | / | / | / |/

why??????

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

Here is an interesting approach for problems like today's E. It provides an $$$O(n)$$$ solution to the minimum element on all subarrays of length k problem

Link

Do this for every row with a sliding window (two pointers) of length b, and then with these results do it again for every column with a sliding window of length a (or vice-versa)

I tried it using a map, but it seems $$$O(n\cdot m\cdot logn)$$$ is too much this time :(

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

If I submit two correct solutions in different time, which one is scored? Latest one or first one? I miss submit D2 solution to D1...

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

Why is the TL of E so tight? Even O(n * m * log(m)) solution is not passing the time limit :(

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

    The problem E.aka TLE :D

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

    In my case, O(nmlogn) was accepted by 500ms. I used efficient segment tree. I saw your solution, it was O(nmlog(nm)) and set/map have much overheads.

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

    I had the same problem. After dozens of attempts to push O(n*m*log(2)), I decided to write something else. And finally, i wrote solution with sparse table. In my implementation queries were with fixed size, so i could answer them with O(1) time. But anyway Sparse table uses O(n*m*log(m)) precalc, but this is much faster then segment tree or other structure.

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

Wow, another ImplementationForces round, so cool (yes!)

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

    deleting the comment lines and thinking that it will be missed out from the codeforces users :D:

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

      It definitely missed the plagiarism check though.

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

        how the system did not detect it? it is kinda weird

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

    MikeMirzayanov Please look into this.

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

    Both from Hangzhou, China. Coincidence? I don't think so ...

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

    ???

    I think I don't give this guy my code.

    Anyway,I find the similar problem of this round's E

    Might he use my code by the similar problem.

    So Why [user:ljc2002]not skipped?

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

      hello . I'm ljc2002 and I want to explain why my code is very similar to yours.

      The problem E may be a combination of two subproblems(the "sliding window" ,滑动窗口)。But, I completely copied the solution to this topic into this question. However,the author of the problem I referenced participated in the competition again.So it may led to this misunderstanding.

      I’m terribly sorry about this thing. I hope to get your understanding.

      I emphasize one point,the code of ours is done by ourselves.And,there is no any communication in the examination.

      大家好,我是ljc2002,我想和大家(特别是对ChthollyTree同学)解释一下这次事件的原因。

      problem E是由两次的"滑动窗口"组合而来的,但是我使用了某篇题解的代码来解决这个问题,但是,这篇题解的作者可能也参加了这个比赛,所以就导致了这样的误会。

      我对ChthollyTree同学感到非常抱歉,并且希望得到他的谅解。

      我指出一点,两道题目的代码是由我们两个自己分别独立,完成的。不存在考场上的交流

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

        复用已有代码是符合规范的,没必要道歉。

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

        I believe that ljc2002 can solve problem by himself.

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

In round #574 (div 2), problem D1 I had submitted my solution with 10-20 seconds remaining and it was in the queue for verdict but suddenly the contest was over and I was redirected to the home page of contest. Please look into the problem.

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

editorial?

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

Idea for the problem D1?

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

    Observe that for each digit of each number, you can predict what position it would occupy in the functional output. For ex., if the numbers are 22 34 then f(22,34) = 2324 and f(34,22) = 3242. So, the ith digit in, say, x would be the 2*ith or the (2*i + 1)th digit in the functional output. So, simply iterate over the 10's expansion of each number and add to an ans variable the value that each digit in the expansion would occupy in the output.

    To complete the example above, you'd have s=(4*(10^0)+4*(10^1))+(3*(10^0)+3*(10^1)) from 34 for each number it is going to be paired with. Each number will be paired with n numbers (including itself), so, you'd have ans+=(n*s) for 34. Proceed similarly for each number in the input array.

    My submission: http://codeforces.com/contest/1195/submission/57225770

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

      What about d2. How to solve it.

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

        It's very similar. You just have to be careful about the weights in the 10's expansion that you assign to the longer number.

        For this, my approach was to maintain a frequency array having a[i] as the number of elements with length i.

        Now, for each number in your input array, traverse its 10's expansion. If you're at the ith digit then surely, all numbers with >=i digits will ensure that this ith digit will play out similarly as in D1. Only for numbers with <i digits, you'll have to figure out the 10's expansion weights.

        For ex., f(12,3456) = 341526 and f(3456,12) = 345162. Observe how for the lowermost 2 digits, this case was similar to the case for D1, ie. f(12,56) and f(56,12). You only have to be careful about the weights you assign to 3 and 4. You should be able to arrive at an equation for the weights in terms of the len(a[i]) and i. Think about it.

        My submission: http://codeforces.com/contest/1195/submission/57237562

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

          during 10's expansion in both d1 and d2, will there be an issue of carry generated?

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

            It's always taken care of on its own. For ex., when you're doing 98+76, you're essentially doing (9*10)+(8*1)+(7*10)+(6*1). Any generated carry will be taken into account in the calculations by itself.

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

Editorials?

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

can any one explain test cases in (problem D1) >> thanks ..

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

    3

    12 33 45

    you need to calculate element's sum of this

    f(12,12) f(12,33) f(12,45)

    f(33,12) f(33,33) f(33,45)

    f(45,12) f(45,33) f(45,45)

    calculated values of functions:

    1122 | 1323 | 1415
    1122 | 3333 | 3435
    4152 | 4353 | 4455
    

    you can present as

    1020+102 | 1020+303 | 1020 + 405
    3030+102 | 3030+303 | 3030 + 405
    4050+102 | 4050+303 | 4050 + 405
    

    you can see that sum of this equals to

    (1020*n + 102*n) + (3030*n + 303*n) + (4050*n + 405*n)

    where n=3

    or just:

    f(a1,a1)*n + f(a2,a2)*n + f(a3,a3)*n

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

What was the correct approach for A? Many people (including myself) got WA in test 13 :/

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

    Just store frequency of each type of drink and for any type of drink having frequency more than zero, say having frequency f, (f — f%2)/2, sets of that drink(decrease frequency by f — f%2), decrease the drink set count(originally ceil(n/2)) and after doing it for all present type of drinks, we have at max 1 drink of a particular type , so say K(not question's K) drinks are still required(Since all remaining drinks are having frequency 1) then choose to add minimum of (K, remaining sets) to the final answer, and finally that would be the answer I THINK!!!!

»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Everyone has done problem C as bottom-up approach if anyone wants top-down approach then here it is #57250417

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

Can anyone xplain the logic of problem C?

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

It's been almost 10hrs since the contest ended. Why isn't the editorial released yet ? Isn't it prepared beforehand ?

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

My submission for D1 gives a WA verdict for the test 5 1000000000 1000000000 1000000000 1000000000 1000000000. But the answer matches the expected output in my system. Any help would be appreciated. Link to my submission https://codeforces.com/contest/1195/submission/57257009

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

    Try debugging your code through 'Custom invocation' feature of Codeforces.

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

Where are the EDITORIALS?

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

can someone pls tell me where i went wrong. It is for question B,I used a function similar to binary search one and after 10 pretests I got wrong at 11th one. //

int ans(int l, int r) { if (r>=l)

{

int idx = l + (r — l) / 2; long long int o= idx*(idx+1)/2;

      if (o-(n-idx)==k)         return idx;
      else if (o-(n-idx)>k)     return ans(l,idx-1);
      else                      return ans(idx+1,r);

}

return -1;

} // the following test case gives me wrong answer. 999999994 108004280

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

    Overflow. The right side is calculated first. (int)*(int) -> overflow.

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

      thnk u and also bro I dont know how to solve this issue . could u pls tell me how to solve this??

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

        "long long idx" or "1ll*idx*(idx+1)/2"

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

          either of these things doesnt help. still getting wrong answer :(

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

              yeah, i used long long unsigned int for o which gave 6 as answer for 5 0, while the answer should have been 3. when i removed 'unsigned' it somehow gave right answer and my code got accepted. thank you.

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

How to solve E

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

    Consider the row and the column respectively. Let

    $$$r[i][j] = \min(h[i][j], h[i][j+1], \dots, h[i][j+b-1])$$$
    $$$c[i][j] = \min(r[i][j], r[i+1][j], \dots, r[i+a-1][j])$$$

    The answer is obvious.

    $$$\sum_{i=1}^{n-a+1}\sum_{j=1}^{m-b+1} c[i][j]$$$

    Now the problem is to find the minimum value of fixed-length subarrays in a sequence, and it can be solved in linear time with sliding window(or monotone queue)method.

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

Why is the meaning of question A so difficult? 0.0

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

Can anyone suggest a testcase to make this solution fail? https://codeforces.com/contest/1195/submission/57264099

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

    You can even take look at this one! I've checked your solution for all valid inputs such that $$$N \le 10^4$$$ and It was okay (I'm not sure that there exists any counterexample).

    This problem can be solved using the quadratic equation (submission).

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

      Yeah I know the solution, just wanted to find the counter example for this. Thanks anyways :)

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

    I don't think you will find one. The correct solution is:

    n + floor(3 -sqrt(9 + 8*(k+n))/2
    

    (actually for valid test cases the floor function doesn't change anything).

    This code does:

    n - floor((1 + sqrt(1+8*(k+n))/2) +1
    

    If we say x =8*(k+n) then the difference between these is:

    d(x) = floor((3 -sqrt(9+x))/2) + floor((1+sqrt(1+x))/2) -1
    = floor((1-sqrt(9+x))/2) + floor((1+sqrt(1+x))/2))
    

    For x>=0 we have 0 < sqrt(9+x) - sqrt(1+x) < 2 so d(x) is either 0 or 1.

    For valid testcases x is an even number such that 9+x is an perfect square.

    If 9+x is a perfect square and x > 0 then 1+x isn't, so d(x) will be 0.

    In other words, the code will get the correct answer for all valid testcases, even if it does it in a slightly strange way.

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

Hi,

these 2 people have exact same code for D2 all they did was just rename the variables and added spaces and random ass functions which have no job in the code. Is this allowed to do so? it can't be coincidence that their code is exact same except the variable names.

BTW they from same college too.

cuber_coder 57239152

RaunaqRoxx 57235255

Sad

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

    Cheating on codeforces is quite common. More shameful thing is that MikeMirzayanov doesn't take any serious action. I only remember one time when he responded. Otherwise he has nothing to do. But if you are red he might respond. Example when he even responded a blog asking for debugging help

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

      I guess we should not blame anyone for that, Codeforces contest frequency is so high, all the people who are providing these for free,work very hard .Not because of money,but because they love this work.if some people cheated it's shame on them.but I want to ask why are you wasting your time .I guess codeforces have plagiarism checker it might be slow.Think it as learning platform,its not some real exam.its the platform u make mistakes and learn. Time is valuable resource invest it in right direction, try to solve hard problems instead of looking into such matters, it's for your benefit.no offense.

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

        Hi thank you for your suggestion,

        I agree with your views on how busy the platform is. I just wanted to clarify that I'm not obsessed with checking if the 2 users cheat or not. I was just reading their answers for method to solve a problem and found that they were same. If you know a user who gives good concise answers to problems in contests you can share their handle please.

        Thank you.

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

Will the editorial be published for this round, vovuh?

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

please ,publish editorial fast ....

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

The editorial will be within one-two hours. I almost done with it. Sorry for delay.

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

    You are really a good author and coordinator. Thank you!

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

following is the solution for B in O(1) time complexity:-)

O(1) solution for B
expressions are :  1. (x*(x+1))/2 - y = k ( here x is the no of times she put candies)
                   2. x+y = n
                   3. let no of candies eaten  = req;
 solve 1 and 2 equations . we obtain a quadratic eqn in x , n  and k as given below -
 quadratic eqn : x^2 + 3*x -2*(n+k) = 0 
 solve this equation and take positive root .
 after finding the root(x) .. now we have to subtract this from n since we need
 how many she ate ..
 as we know  no of candies eaten(req) + no of candies put(x) = no of chances(n)
 thus req = n-x.
 this is the ans.
    for code click this link ->  https://codeforces.com/contest/1195/submission/57284355
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F

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

Can anyone help me indicate why this situation happens?

GNU C++11: https://codeforces.com/contest/1195/submission/57351255

MS C++ 2017: https://codeforces.com/contest/1195/submission/57351301

They are both my submissions (in practice) for problem E (https://codeforces.com/contest/1195/problem/E) in this contest.

They are exactly the same code yet submitted with different compilers, e.g., GNU C++11 and MS C++ 2017. However, the one submitted using GNU C++11 got wrong answer with the output 0 for the first system test while got accepted if submitted using MS C++ 2017.

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

What wrong with my submission on test case 5 D2 problem. Thanks in advance!

https://codeforces.com/contest/1195/submission/57376447

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

Hard div.2(A) problem ever:)

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

I know this is really late but test cases for F are weak; solutions which use doubles to store atan2(example: 58176014) pass system tests even though the following test case makes them output 3 instead of 5:

2
3
0 0
1000000000 999999999
0 1
3
0 0
999999999 999999998
0 1
1
1 2
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! Added your test into testset to prevent accepting such solutions in the future.