Vovuh's blog

By Vovuh, history, 6 weeks 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 senek_k. 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 _kun_ 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

»
6 weeks 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

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

»
6 weeks 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?

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

    It will be fixed.

    • »
      »
      »
      5 weeks 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??

»
6 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

I hope to become cyan again.

»
6 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Will vovuh surpass pikmike

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

I hope to become white after this contest.

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

I hope to become blue finally. :D

»
5 weeks 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 :)

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Clashes with topcoder SRM 763!

»
5 weeks 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.

»
5 weeks 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

  • »
    »
    5 weeks 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 ....

  • »
    »
    5 weeks 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.
»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I'm sorry that I can take place.

  • »
    »
    5 weeks 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

»
5 weeks 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?

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is SIS contest?

»
5 weeks 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 ?

»
5 weeks 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?

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What will scoring distribution be like?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the meaning of problem D's scoring?

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

    I think 1000 pts for easier version and 1500 pts for the harder version (of a similar problem) maybe.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess there will be two subproblems, similar to the problem D in Round 572 D1 and D2.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if they are hard problems, why is scoring <= C?

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

        As I reviewed the recent contests, D1 is usually easier than C, and D1+D2 is a great deal of 2500 points.

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This round clashes with Codeforces Round #574.

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

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

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

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

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

    Challenge accepted :)

»
5 weeks 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 ?

»
5 weeks 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

  • »
    »
    5 weeks 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.

»
5 weeks 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 ???

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

    Easy div1 :)

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GOOd luc to all ! .. xd hope rating get

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No Hackforces or Queueforces please!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Gray here I come!

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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)

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

    Welcome to FairyForces :P

»
5 weeks 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.

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

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

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

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

»
5 weeks 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.

  • »
    »
    5 weeks 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 ....

  • »
    »
    5 weeks 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.

»
5 weeks 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.

  • »
    »
    5 weeks 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:)

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

F: another problem that Wikipedia makes a difference

  • »
    »
    5 weeks 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.

»
5 weeks 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

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

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

  • »
    »
    5 weeks 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$$$.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do I have to drop two logs?

      • »
        »
        »
        »
        5 weeks 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.

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

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

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

»
5 weeks 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 :(

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D2 ?

  • »
    »
    5 weeks 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.

»
5 weeks 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?

»
5 weeks 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

»
5 weeks 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.

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

it make the chinese stay up late

»
5 weeks 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?

  • »
    »
    5 weeks 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;

  • »
    »
    5 weeks 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.

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

      simply 2 variables would have been enough i think?

      • »
        »
        »
        »
        5 weeks 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]);
        }
        
  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks 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.

  • »
    »
    5 weeks 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)).

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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

»
5 weeks 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

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +113 Vote: I do not like it

meme

»
5 weeks 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

  • »
    »
    5 weeks 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 -_-

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congrats!

»
5 weeks 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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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 :)

  • »
    »
    5 weeks 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; }
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks 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.

          • »
            »
            »
            »
            »
            »
            5 weeks 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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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:)
  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the first sample in D1 please ?!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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 :)

    • »
      »
      »
      5 weeks 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 !

  • »
    »
    5 weeks 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])

»
5 weeks 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

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

Lucky me.

»
5 weeks 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??????

»
5 weeks 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 :(

»
5 weeks 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...

»
5 weeks 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 :(

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

    The problem E.aka TLE :D

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 weeks 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:

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It definitely missed the plagiarism check though.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

    MikeMirzayanov Please look into this.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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?

    • »
      »
      »
      5 weeks 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同学感到非常抱歉,并且希望得到他的谅解。

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

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

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

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

        I believe that ljc2002 can solve problem by himself.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial?

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

Idea for the problem D1?

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about d2. How to solve it.

      • »
        »
        »
        »
        5 weeks 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

        • »
          »
          »
          »
          »
          5 weeks 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?

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Editorials?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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

»
5 weeks 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 :/

  • »
    »
    5 weeks 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!!!!

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone xplain the logic of problem C?

»
5 weeks 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 ?

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Where are the EDITORIALS?

»
5 weeks 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

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

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

    • »
      »
      »
      5 weeks 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??

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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.

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

How to solve E

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Why is the meaning of question A so difficult? 0.0

»
5 weeks 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

  • »
    »
    5 weeks 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).

    • »
      »
      »
      5 weeks 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 :)

  • »
    »
    5 weeks 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.

»
5 weeks 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.

ujjawalpabreja1 57239152

raunaqroxx 57235255

Sad

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

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

Will the editorial be published for this round, Vovuh?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

please ,publish editorial fast ....

»
5 weeks 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.

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

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

»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F

»
5 weeks 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.

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Hard div.2(A) problem ever:)

»
3 weeks 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
  • »
    »
    3 weeks 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.