Vovuh's blog

By Vovuh, history, 13 months ago, translation, In English,

I am so sorry about very long gaps between the contests but I really don't have enough time to prepare the problems. So...

<copy-pasted-part>

Hello!

Codeforces Round #521 (Div. 3) will start at Nov/16/2018 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. 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 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 Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD1:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 diolG 7 173
2 lyzqs 7 228
3 pvviet001 7 241
3 LVL 7 241
5 lukameladze1 7 250

Congratulations to the best hackers:

Rank Competitor Hack Count
1 PikMike 153:-6
2 ______-__________-______ 186:-85
3 knowbody 128:-6
4 Laggay 113:-6
5 Marcosk 66:-6

1359 successful hacks and 755 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Laggay 0:01
B Laggay 0:03
C Programmist_111 0:05
D Laggay 0:12
E Programmist_111 0:12
F1 happ1 0:29
F2 Radko 0:32

UPD2: Editorial is published!

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

»
13 months ago, # |
  Vote: I like it -43 Vote: I do not like it

I am here for reading comments.But i am the fisrt commentor,so read my comment and hit the up button... Wish you all higher rating...

»
13 months ago, # |
  Vote: I like it +44 Vote: I do not like it

What happen for Div. 3 contests if we haven't Vovuh ?

Thanks Vovuh and also thanks creator of copy-paste (Larry Tesler) :))

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all of you, guys! Hope you high ratings. :)

»
13 months ago, # |
  Vote: I like it -34 Vote: I do not like it

earlier i used to think that i could solve 4-5 problems in div 3 rounds as it would be easy with div3 tag , but now i knew one thing "dhoka hai ye , ek trah ka jaal, shajis hai hamein nicha dikhane ki, haha div3 tag XXXDDDD", don't take it offensively it's just a joke, i love codeforces.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    What a nasty comment...

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

    haha, same, man

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

      Translation?

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

        Meh, languages used are part of the joke. You'll have to believe me that it's funny and highly relatable)

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 3   Vote: I like it -23 Vote: I do not like it

        So i opened the refrigerator, took a tomato, a cucumber,a greenery, wanted to make salad. It is obvious the salad should be made with mayonnaise (else who who would eat it?). I cut all and realized I forgot the mayonnaise. i opened the refrigerator again, took the mayonaise and suddenly realized that there is some lard in front of me. I have never eat the lard, but i suddenly i wanted it. While I filled the salad with the mayonnaise , cut the lard, ate it and suddenly all (*something in Ukrainian)

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      haha classic

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Pardon me this is my first rated(hopefully) Div 3 contest. Why is this rule there?

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

They will be considered in leaderboard table though?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If they solve problems fairly then yes, they're will be shown in the leaderboard. This rule is there just to exclude the people who want to be top-5 by unfair hacks.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what's the benefit of hacking someone's submission ? does it increases rating or points?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know but I'm sure that X3NNY knows (but I think that he was framed and this is just coincidence)

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I just want to lose Rating, no harm.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get reminder for this type of contest?

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

I hope this div3 A will not be harder than div2 A as always

edit:finally it's not

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

today I'll become blue. screen it

»
13 months ago, # |
  Vote: I like it -22 Vote: I do not like it

After Hacknig xD
photo-2018-11-16-19-39-42

»
13 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks, Vovuh !!

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

Can someone please tell me why my submission for F is getting TLE on test 41 ? Used deque and dp.

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

I can't believe I wasted that time on C that feels incredibly stupid XD

edit: and it's WA XD

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E binary search?

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

    No, but D is

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve D?

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

        Observation: Suppose from an array you can remove a number of value 'v' X number of times, you can also remove it X — 1 number of times,

        Basic division and function check on this monotonic function gives you AC. Didn't code this because my implementation skills are bad. But pretty sure this approach is correct.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is.

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

    I solve E with lower_bound in c++.I think it's the same as binary search.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain your approach?

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

      is your solution have two logs ? Is it works by using binary search(or lower_bound) in every possible numbers of competitions?

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes,there are two logs,one is the number of problem ,one is lower_bound

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solve D and E with binary search,but I am not sure it will not be hack

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution for problem C ?

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

    Start from left of the array and if there is a zero in between two ones, remove the right one. Let this be ansA, do the same for the reverse array and let the answer of that be ansB. Final answer is min(ansA, ansB).

    Sorry this is for B

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is the solution to problem B Not C

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

        Sorry,

        For C: Let sum of whole array be S, then in a vector store pair of <value, index> sort this in descending fashion,

        if you are removing first element of this vector, your remaining sum is S — v[0].value. remainingSum — v[1].value should equal to v[1].value.

        else your remaining sum is S — v[i].value. remainingSum — v[0].value should equal to v[0].value.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you please Illustrate more ?

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

            essentially there are a couple ways to create a good array, both can occur though.

            type1: removing the largest value, hence the second largest value will have to be the sum of the remaining digits, excluding the originally biggest number (and the second largest of course).

            type2: removing a value (that is not the largest), to make the sum of all the other values equal to the largest.

            you can check for both types, which is what i did.

            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Actually, This is a good idea

              I have wasted my time in this vector for a long time trying to remove only the greatest one

              Thanks a lot

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For B, I think ansA will always be equal to ansB, so there's no point in calculating both of them. If I'm wrong, can someone please suggest a test case where ansA  ≠  ansB?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Observation: We are checking if removing an element from the array can make the max element equal to the sum of other remaining elements. And in case we are removing the max element, we are just checking if we can make the second max element equal to the sum of other remaining elements. (Since there is no element with -ve value) So, we just have to find out the max and semi-max element and then iterate the array removing each element at a time and checking the above criteria.

    for example, a= [5,2,1,3] Max= 5, Semi Max= 3 Removing 5(Max), a=[_,2,1,3] makes Semi Max, 3= 2+1 Removing 1, a=[5,2,_,3] makes Max, 5= 2+3 These two are only bad indices in this example.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the hard version of problem F ?

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

    dp[number added][last added]

    Naive transitions work in O(n) for a total of O(n^3). If we use sliding window for each layer, we can transition each layer in O(n), for a total of O(n^2).

»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Did anyone manage to AC E with dp in O(nlog(109)log(n)), something like this?

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

    For E: Store the frequency of each topic in array and sort that array. Then let say we fix the no of topics in first contest be i, then binary search on this array to find if there exists a topic with frequency greater than i, if yes then take the leftmost topic and set it as new index (initially index is 0) and then check for 2 * i and repeat the process. If not found, just break at that index. Repeat the process for new i. Code: http://codeforces.com/contest/1077/submission/45834476

»
13 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Relief :)

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach D? what i did, first i count the frequency of every number and then i put them on a pair, but then i could not find any way that how to go further!! i could come this much :(

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too i just store frequency in hash

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think recursive find() function that continuously divides possible region for k in half might solve the problem in O(nlgn), but I ran out of the time...

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    count the frequency of every number and then put them on pair. now try to cut the array x time. if it is possible than it is possible for all number 1 to x if it is not possible it wont possible for any number x to 200000. (Thats mean you can use binary search)

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's easy to find an array that can by cut out x times. So just do a binary search for the biggest valid x.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excuse me, where is the tutorial of this contest? :-)

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

give some test case to hack

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the tutorial for this contest?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it intended in F2 that using segtree gives TLE but other data structure like sparse table gives AC?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why on problem F the condition if((k*2-1)*x<n) cout<<-1; isn't enough to detect if it's impossible to solve?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you get points for Hacking other's solution in this round?

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

C Wrong answer on test 3, but I got right answer local.... Why?

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

Mike bhaiya meri rating kyu nahi badh rhi? ye codeforces hi bekaar hai

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Plz someone explain me, why 45840553 is TL 16 and 45840575 is RE 1 ?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your cmp function does not define a "strict weak ordering", which std::sort requires. The short version of the explanation is that your predicate should behave like < and not like <=.

    Failing to meet this requirement causes undefined behavior, which basically means that the verdict may vary arbitrarily.

    P.S: there might be other problems with the source, this is just one I have noticed.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack for C? A lot of C's solutions are getting hacked.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    4
    2 7 7 5
    

    Answer:

    2
    2 3
    

    The reasons for WA are various as for all of the following outputs I found a solution that produces that output:

    0
    
    2
    2 2
    
    4
    2 3 2 3
    
    2
    2 3 2 3
    
»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It seems that I was the only one who misunderstood the statement for problem B. Can anyone tell what is it really asking for ??

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

    me too bro :(

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The question asks for the minimum lights you have to turn off for all peoples "sleep well".

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

      If only I had known that before. I thought they were asking how many different pairs of lights I needed to turn off (turning off a single pair), in order for no people to be disturbed.

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

    same, the pairwise distinct stuff confusing me, i think that for sample test 1 answer should be 1 because it only need 1 pair to make not disturbed array,

    wasted so much time understanding this problem >:(

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      All it required was to search for "101" and keep skipping by 2 so as to prevent any extra count of 101 due to overlap. Here is my submission.

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

What's the benefit of hacking someone's submission in Div 3? Does it helps in increasing rating?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it doesn't help to increase the rating.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But you can overtake some peoples and then your rating will be higher

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

        Their code will fail at main tests anyway :)

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

    Some people enjoy this :) And for cf: you don't need to test some solution if it already failed

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

I tried to hack a solution (It makes 10^12 operations worst case) but I got unsuccessful hacking however the code I tried to hack takes 128s on my machine itself (with T = 100 , it is 1000 in the test case). I want to ask if hacks are only successful if the code gives WA ?

EDIT : here is the link https://codeforces.com/contest/1077/submission/45824799, he is looping from 1 to k/2 when a != b.

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

    WoW ! Looks like CF is real fassst.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give the link of solution?

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

    Then you have a different version of the compiler. On my machine with GCC 7.2.0 it runs almost instantly.

    EDIT: Actually, you need to have -O2 as a tag for the compiler to make the solution fast, compiler version doesn't matter.

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

      Did it run instantly on a case where k ~ 10^9 and T ~ 100/10 and a!= b?

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

        Yes. Did you add -O2 as a compiler tag?

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

          Yes , I added that tag and it took about 10s(for t = 100).

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Though I still dont get that how can it not give TLE since he loops from 1 to k/2 (1e9/2) for every case with a != b.is CF insanely fast or something since I dont see this passing anywhere.

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            See my reply, and learn compiler theory.

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

            -O2(at least on my machine) notices that the program increases a number "sum" by a-b l times, so it replaces that part of the code with increasing "sum" by (a-b)*l.

            • »
              »
              »
              »
              »
              »
              »
              13 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              :O nevermind. Thanks for your help.

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You can see the optimised assembly here: https://godbolt.org/z/piYeZH

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Compiler optimizations. P.S. This is what happens when a person jumps right into the programming, bypassing the CS.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I read some code and want to hack them. But now my head are getting hacked...

»
13 months ago, # |
  Vote: I like it +25 Vote: I do not like it

»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can any one tell me why my solution for E is getting TLE on TestCase 51 I think its Nlog(n). http://codeforces.com/contest/1077/submission/45845419[Link to submission].

»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why sometimes there's 3600 participants and sometimes 5000 :/

that's not the first time this happens

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E: why is this approach is wrong?

»
13 months ago, # |
  Vote: I like it -22 Vote: I do not like it

Problems like Dick

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with std::list? I used sliding window algorithm for F2 and I used std::list to implement it but I got MLE. So I tried to cut down memory by making D[2][5000] instead of D[5000][5000] and I got accepted. But when I changed std::list to std::deque, it was accepted and even faster! In another OJ sites I usually use, std::list is faster than std::deque so I thought it would be same here. Can anybody tell me why?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    MLE code : 45823888 AC code : 45852635 Here is my code.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe list need some extra space to save pointer?

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

      I think so. According to my short experiment using both std::list and std::deque, std::list is faster than std::deque but drains tons of memory. std::deque, on the other hand, uses less memory but slightly slower. There might be something wrong, so if somebody finds anything new, please let me know.

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

        Well... std::list is a doubly-linked list, so for every element in it of type T is uses two pointers and one field of type T.

        std::deque on the other hand is basically a linked list of increasingly large vectors and uses (more or less) the same space as a vector.

        As a very rough approximation, if T has the same size as a pointer, std::list will use more or less 3 times more memory than std::deque. Nothing wrong with it, it's just the way the structures are implemented.

        P.S: Bjarne Stroustrup (the creator of C++) has a very interesting talk on why you should avoid using linked lists. They have their uses (mostly when deletion in the middle is involved), but you should avoid them whenever you can use pretty much anything else.

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

If there is any one want to hack somebody, you can try to hack HunTer's problem C solution, he didn't use long long instead int lol

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it true that SysTest of Educational/div3 round goes this long or is it only this contest? I just realised it today.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I did 42 successful hacks but didn't get increase in my rank....how it'll be beneficiary for me?

»
13 months ago, # |
  Vote: I like it -6 Vote: I do not like it

When would the rating changes reflect?

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was solving the 3rd problem of round 521 div 3. Problem Link: http://codeforces.com/contest/1077/problem/C As mentioned in question's description that a[i] <= 10^6 but test cases don't follow so. I used frequency array and got runtime error. On the other hand, using map got me AC. Please clarify if I am wrong. Diagnostics: https://imagebin.ca/v/4MtAcprEnUbw RE sol: http://codeforces.com/contest/1077/submission/45860663 AC sol: http://codeforces.com/contest/1077/submission/45862293

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

    Even though a[i] <= 10^6, sum can be greater than that, so your line 42 where you tried to access pre[(sum-a[i])/2] would make you RTE

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

I was solving the 3rd problem of round 521 div 3. Problem Link: Problem C I don't know why I'm getting wrong for test case 86. But getting right on my local machine here is the code link Solution.

ThankYou.

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Magic has been hided after the dots, last number of the input is 532704.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ThankYou

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But still getting right on my machine.

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Then it isnt that testcase, but you're wrong because m is mapping from int, m[temp/2] will be truncated to m[int(temp/2)].

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thankyou The map is taking some random key with 0 value. Just handled and got ac.

          • »
            »
            »
            »
            »
            »
            13 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But why it will take random key instead of taking only the int part(maximum bits that can hold by int type)

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, It still gives the correct output in the cf custom test section also

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

this 45822434 gives me correct answer for question D in my IDE but this is wrong answer.

can any body say why?

»
13 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Huge difference between cf-predictor & actual rating change!! What's wrong today?

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you "hack" someone by sending inputs that are meant to fail the code you get 100 points if that attempt was successful, likewise the person that was "hacked" will loose their points for the question, as their attempt will be considered a failure. I got hacked and dropped a rank because of it i feel.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any of my solutions wasn't hacked here...

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

    I think it's because the predictor is considering non-trusted participants on the calculus

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov in predictor, my increment was +98 but i was increased by +77 in change rate why ??

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

    Same for mine too...it was showing +61 but actual increase is +39

»
13 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In this round CF predictor shows my rating would be +103 but actual rating increased by +73 :( :( can anyone please tell me the reason why it happens ???

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

Vovuh I get WA on problem C with solution 45813685 , but get AC with 45865201. The map might taking some random key with 0 value as I declared map<int,int> and the data can be long long. But why it will take random key instead of taking only the int part(maximum bits that can hold by int type)??? I have checked in the Codeforces custom test section with that test case. It gives same answer as jury's

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because when all the values of array are 1e6, value of s will 2*1e5*1e6 which exceeds int datatype. so when you are performing the check at if(mp[(s-a[i])/2]>0) , s — a[i] has already exceeded int's limit. That is why it wraps up again to lower values and gives incorrect result.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      It gives the correct answer in CF's custom test section for the same input -_-

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      But still it shoudn't give WA for that test case. Cause, when overflow occurs it should some value till limit of int instead of taking random key

      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is not taking random key. It is wrapping up to the lower values again when exceeds it's limit.

        • »
          »
          »
          »
          »
          13 months ago, # ^ |
          Rev. 2   Vote: I like it -6 Vote: I do not like it

          Then it should be Accepted as it runs well for test case 86 in CF's custom test also :/

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same with my solution 45813690 why this fail, and when change map to ll get AC?

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

can any one tell me why my solution for E is getting TLE on testcase 54? complexity O(n log^2) http://codeforces.com/contest/1077/submission/45868358

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i am getting wrong answer for the problem C foe the test case 86 , its output should be 0 but it is showing something else in my case, but i have seen other codes and their submissions, for them the output for the test case 86 is 0.

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

Where can I find the editorial/tutorial for this contest?

»
13 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Can somebody explain O(n^2) solution for F? I've seen solutions with sliding windows using deque but I don't quite understand logic behind it.

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't see the tutorial.Can you give me ?

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

My solution to D without binary search passed — https://codeforces.com/contest/1077/submission/45884322 Are the hacks not included in the final test cases when the problem goes into practice section?

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

    Hmm, it is really weird. I will add the test on which your solution will got TLE. It is very strange that nobody do it during the hacks phase. (And even more strange that I don't do it before the round start. Sorry about that.)

    UPD: Woops, this solution got TLE now.

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

      Weird :p Does this mean that this solution would have gotten Accepted in the main contest?

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

        Yes, it was accepted in the main contest, unfortunately. I have nothing to hide. Sorry :(

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

HI in the last two contests thst i've taken a problem that i solved correctly got hacked.does anyone know why?45824931

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think div 3 and div 2 contests are same in quality except problem A

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats wrong with my logic for A here:

t = int(input())
for cas in range(t):
	a, b, k = map(int, input().split(" "))
	if k%2==0:
		print(int(k*(a-b)/2))
	else:
		print(int((k+1)*a/2 - (k-1)*b/2))
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You have to use integer division (//) instead of float division(/)