Akikaze's blog

By Akikaze, history, 8 months ago, In English,

TREMBLE BEFORE THE MIGHTY OMEGALULGRAPE

Hello Codeforces!

We are honored to invite you to Codeforces Round #538 (Div. 2), which will take place at 10.02.2019 17:05 (Московское время). The round will be rated for all Division 2 participants (with rating less than 2100). Still, we warmly welcome Division 1 participants to join us out of competition.

You will be given 6 problems to solve in 2 hours. The round's problems were initially prepared by Duy-Bach Akikaze Le, Xuan-Tung neko_nyaa Nguyen and Xuan-Quang xuanquang1999 D. Nguyen.

There will be an interactive problem in this round. Learn more about interactive problems here.

This is our first attempt in making a Codeforces round, so suggestions are much welcome to help us improve ourselves. ;)

We also want to thanks many friends for making this round possible:

  • Dmitry _kun_ Sayutin for coordinating the round, providing a neat idea on one problem and some Russian translations.
  • Andrew GreenGrape Rayskiy for various suggestions on the problems, some other Russian translations, and most importantly, peacefully submitted himself to be quarantined from pretests. ;)
  • Michal majk Svagerka for testing the round.
  • And last but not least, Mike MikeMirzayanov Mirzayanov for the amazing Codeforces and Polygon platform, without which this round would never be possible :D

P/s: I will be at the Discord CP Community to discuss the problems after the coding phase. However, please follow the rules and don't discuss the problems during the contest by any means.

Wish everyone good luck and high rating!

UPD1: Score distribution: 500-1250-1500-2000-2000-2750

UPD2: Editorial is published.

UPD3: The contest is finished. I apologized for the "somewhat" weak pretests at here and there. Anyway, time to celebrate our winners ;)

Official participants:

  1. xlk200
  2. vasilescu_mihai
  3. Cinro_9baka
  4. africamonkey
  5. 2019_BecameMaster
  6. cdsfcesf
  7. yww_AFO
  8. hr_tian_xia_di_2
  9. JZmster
  10. chinmay0906

Div.1 + Div.2 participants:

  1. Hazyknight
  2. tfg
  3. tempura0224
  4. xlk200
  5. sava-cska
  6. mango_lassi
  7. I_love_Tanya_Romanova
  8. ec24
  9. vasilescu_mihai
  10. Cinro_9baka
 
 
 
 
  • Vote: I like it
  • +573
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Congrats on your first round!

»
8 months ago, # |
  Vote: I like it -26 Vote: I do not like it

i don’t understand any of this can someone explain

»
8 months ago, # |
  Vote: I like it +32 Vote: I do not like it

GreenGrape everywhere...

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

Good Luck to All!

»
8 months ago, # |
  Vote: I like it +83 Vote: I do not like it

GreenGrape in two consecutive rounds, you must be joking

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

writing an announcement five days before a round -> bad round

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

Kuroyukihime round? awesome!

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

    So far the round is not anime-themed...

    ... yet Lotus will not disappoint ya ;)

»
8 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Vietnamese, raise your hand!!!!!

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

Good luck for your first round! I'm feeling some math here

»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

first congrats on your first round second why interactive?

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

I dont know if I can ask this, but which is the interactive problem? C, D, E or F ???

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

Did anybody notice that there are less comments than shown in the blog.

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

    Some spams were hidden by the administrators.

»
8 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Dont worry guys Not every grape is Greengrape

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

romania!!! unite for this contest !!!

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

I hope the difficult gap between problems can be proper.More personally,I hope there will be a problem(maybe problem D) whose difficulty is between 1700 and 1900.In recent contests,the gap between C and D is always wide(such as 1500 and 2200),which is ,to be honest, unfriendly to me(rating between 1800 and 1900).In many contests,I pass the first three problems in 30 mins and cannot solve problem D in remaining time.

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

    Try problem E

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

      Personally,this contest's problem E is easier than D for me.But I focus on D and fail,so I miss a chance to become purple.

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

Interactive problem,I'm not good at it,sad... Hope it won't be too difficult.

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

Hoping to finally be blue.

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

They didn't complete surgery on GreenGrape

»
8 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Just a random fact, GreenGrape has never been GreenGrape .

»
8 months ago, # |
  Vote: I like it +52 Vote: I do not like it

Why are there more and more Div2 rounds consisting of 6 problems nowadays? I think that this leads to more implementation and to less thinking. I think it's better when there is one interesting Div2E problem than 2 pure implementation Div2E and Div2F problems.

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

i will get grandmaster this round

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

I wished that there will be 6 nice problems and make me get some new skills in this contest. Thanks to the selfless dedication of the problem provivers.

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

Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).

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

Good Luck to All!

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

What will be the pattern of the points of every problem?

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

what is pretest 10 for problem C?

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

    I think it breaks some overflow checkers, namely the ones that test if your new product is less than your old product. You can have overflow and still have the new product be greater than your old ones, and in this case I believe it is because they had some prime that was greater than 4e9 that was getting squared.

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

      "You can have overflow and still have the new product be greater than your old ones", how to handle this ?

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

Pretest 12 E?

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

    RAND_MAX is 32767, u should extend it.

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

      Oh my god...

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

      So basically random_shuffle would not shuffle properly for N ≤ 106?

      If this is the case then it is really bad problem setting because this is not something of common knowledge and many people would have encountered this error even though the had the solution.

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

        Yes, but I think we can use some tricks to make it work in N<=1e6 even though it is not actually uniform distribution.

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

        "The problem is bad if it requires some knowledge that I don't have" doesn't sound like a reasonable approach to me. The fact that random_shuffle() isn't very random by default is important thing to know, and your comment sounds like "It is bad to expect us to know that cout<<endl; is slow" or "It is bad to expect us to know that cache misses are slowing things down".

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

          It seems many people had the same issue so it isn't really common knowledge that inbuilt randomisation in C++ does not work properly for sizes greater than 32767.

          I do not mean to disrespect the problem setters, but it does seem like this specific piece of knowledge is not known to many. Otherwise I would not have said anything like that. Although I do understand that if I am coding in C++ I should know it well enough to be able to code all kinds of solutions.

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

            I still think that your reasoning makes little sense.

            The fact that a lot of contestants don't know (or don't think about) something doesn't imply anything. I would agree if that was something very compiler-specific or CF-specific, like exploiting particular compiler bug that behaves clearly against the standard of C++ and has been introduced in particular version of compiler. I also didn't manage to get this problem initially, and it took me long time to figure out my mistake — but that's my fault, and not setter's.

            Rabin-Vazirani algorithm isn't known to majority of CF users either, should we criticize any setter for deciding to use it for their problem? :)

            Moreover, setters are so nice here that they even included this test in pretests. Can you imagine the mess we'd have otherwise? :)

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

              Well I do agree to that. After all, someday someone had to make such a problem which would have highlighted this issue despite the fact that this has been posted in a blog earlier (because many people don't read blogs or simply don't happen to come across them). I guess this was inevitable.

              Again, I don't mean to say this was setters' fault. All I wanted to say was that maybe the problem could have been set in a way that this issue would not have occurred (maybe setting N ≤ 104). But then this is also true for many other situations, like the need for fast IO (though I am not the setter so I don't have a say in this :P). In no way I mean to disrespect the setters, and I truly believe all setters do a great job at bringing us new problems to solve.

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

              In what sense is including this test different from including a test for the random generator of an arbitrary language? I could see which are the first 60 numbers the program would ask for and make sure they are not coprime positions. Also using any solution (assuming it does not seed on time) I can break it. I don't think this test adds to the quality of the problem and it is specifically targeted towards one of the allowed languages. Is there a test with the first 30 numbers the random of java would generate? Would you consider such a test fair?

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

                Yes, I would consider it totally fair.

                Moreover, your analogy sounds wrong to me. You don't need to know much about generator here — the solution is going to fail no matter what seed is used in generator.

                You are complaining that the solution doesn't work because constraints are too large. That's like saying "my solution with int didn't pass only because in your problem n<=1e18".

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

What is the 12th pretest on E? I kept getting wrong answer on this one

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

what is the pretest #6 in D? ..

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

Can someone please explain how to solve D?

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

Does interval DP not work for problem D?

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

    It does, my solution is df[from][to]

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

      Interesting. I kept getting WA on pretest 6. What was your idea?

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

        If the first and the last letter of the interval do not much you either will convert the longest prefix matching the first letter or the longest suffix matching the last letter. If the two letters match you will change both the longest suffix and the longest prefix on the last move.

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

          So it seems that you're doing the DP by decreasing the size of the DP interval?

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

            Yeap

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

              I did my DP with increasing size of the DP interval (I suppose that should work?). I couldn't seem to come up with a counter case though.

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

                It should at least pass the pretests I did something similar to your solution. Did you take every possible starting position?

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

                  My program should have accounted for every possible starting position. I guess the code speaks better for itself. 49731308

                  I think my transitions may be wrong but I'm not sure how.

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

                I did it with increasing interval. you can have a look at my code- here

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

          I'm probably misunderstanding you, but I don't think what you said is true. If your array is 1 2 2 3, you can change this minimally to 2 2 2 2, which doesn't match the first or last letter.

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

            Hmm no you can not. You have to change it first to 2 2 2 3 and then to 2 2 2 2

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

              Ok, I misunderstood what you meant. I thought you meant that the prefix/suffix was going to match the exact color of the endpoints.

              In any case, I see where my understanding of the problem was flawed.

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

      What are the recursive calls? I imagine it's the classic (l+1, r) and (l, r-1), but sometimes you'll have to add 1 to your result, namely if it's not possible to get (l+1, r) to be the color of c[l] or (l, r-1) to be the color of c[r], but I couldn't find a good way to find when that's possible or not.

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

        That is the typical way I implement DP — recursion with memoization

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

What to do in E after finding Xn? I asked for 30 random values and tried to find d based on these, but it doesn't have to be correct

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

    i do the same and pass the pretests

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

      So I may have failed just because I forgot to delete the line where I was checking something...

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

        how u calculate d ? i find all gcd between all pairs, smth like :

        g = gcd(d, a[j] — a[i]) , for every i, j

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

          I did the same and could not pass pretest 12

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

          I had a list of all common divisors of differences. Final list could have more than 1 element, so d is last element in list, which is the greatest one. I made mistake here and said that d is first element of the list which is actually 1 :)

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

    Use your own rand instead of C++ rand.

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

      I had something like cout<<"xn is "<<xn<<endl; and didn't delete it. mt19937 should work for randomization btw

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

    In fact u are findng at least 30 rand number and get their common gcd, if it is 1, the d is true. Actually, it is correct at most situations.

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

    That seems to be the intended approach.

    Probability of failure is very small. Let's assume that you found dFake which is equal to k * d. This means that all your queries were lucky to hit position with same remainder modulo k, and the chance for it is roughly (1 / k)NumberOfQueries - 1.

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

Why fail segment tree solutions and pass BIT solutions in F? (Offline, solve for each prime separately) -_-

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

i think for about 40 minutes that's is sum in F instead of mult :(

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I was literally begging for pretest 5 in 'C' :(

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

    when u are finding minimum your minimum keeping variable should be large enough initially even 9e9 did not work....but after this i got struck at pretest 10 :(

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

what is pretest 7 in C :(

I just checked how much each prime for b exists

and applied this func for each prime

long long factr(long long n,long long p) { long long po=0; for(long long i=p;i<=n;i*=p)po+=n/i; return po; } and then I got the result after division first array to the second (not sure if this is important to explain first array and the second )

what's the mistake maybe just tell me the right solution and I'll know it because I have no idea

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

    Have you checked your data type? I changed from long long to unsigned long long, and passed Pretest 7.

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

      that would make a difference in the function I wrote above ?

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

        You may try remove i, and let n /= p and po += n / p instead. I passed the pretests in this way.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    long long i=p;i<=n;i*=p

    Is there anything in your code to make sure that i*=p doesn't overflow long long?

    The idea that you described sounds right.

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

E test case 12?

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

    Anti rand() testcase.

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

      I used srand(time(0))

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

        Err yes — the C standard srand() and rand() will only generate integers up to RAND_MAX = 32767. The array size is quite large, and such low-range randomization could be easily countered.

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

          I don't know what is worse anti-rand or anti java Arrays.sort tests

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

    My lazy way of solving this:

    long long RAND(){
        long long ret = 0;
        while(ret < n) ret = ret * RAND_MAX + rand();
        return ret % n;
    }
    
    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      How about using C++ random

      #include <random>
      mt19937 gen(time(NULL));
      uniform_int_distribution<int> range(1, 1000000000);
      auto RAND = bind(range, gen);
      
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel liangliang

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Tonight I learnt one thing from C, that one should never try multiply two numbers as large as 1e18... Failed several times for it. qwq

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

Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).

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

Anyone passed E without randomisation?

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

So is problem E just testing that we have read this blog Don't use rand(): a guide to random number generators in C++? Really?

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

    Problem E was only about knowing that rand and random shuffle might fail you.

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

      Wow. So we have to be prepared for THIS type of problems now too? So it's kinda STDforces?

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

        I’ve once heard that it’s a programming competition. And yes, you must know how basic stuff works in your favourite language.

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

          I don't mind. I'm just curious if this exploit-as-a-main-idea-stuff is going to be a trend.

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

            It's like exploiting hashes modulo 2^64: if you are doing it often enough, everybody knows it and it gets rather pointless as an "exploit".

            I would even say that my example is far from perfect: hashes modulo 2^64 have advantages (like faster execution), so you may still reasons to gamble "Do they have tests against it?.."; and here the fix is pretty much one-liner without significant side effects.

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

        Wow, mathforces, quickforces, hackforces, stdforces...

        You guys just never run out of ways to complain about contests.

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

          delayforces, isitratedforces, forcedforces, damnforces, unratedforces, grapeforces, overflowforces, cheatforces, longstatementforces, pupilforces, foolishforces...

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

      Add time(NULL) and random_device not being random to that list.

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

What is correct structure for F? My first thoutgh is segment tree for each prime with add on segment and sum on segment. But then I realize that segment tree can't do that from my understanding.

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

    That is entirely possible with lazy segment tree, but it uses too much memory.

    I had a segment tree storing the product of values in an interval, and a segment tree for every prime telling if the prime exists on the interval. The second type of segment trees just use vector<bool>, so they don't use too much memory.

    Answer to every query is just product of numbers in the interval * (p-1 / p) for every prime p that has at least one appearance on the interval. The division is of course modular division.

    In total this is O(q * log(n) * (log(n) + cp)), where cp is the amount of primes below 300

    This was quite annoying to fit in time limit however, since I don't know how to write a lazy interval multiplication segtree without taking modpow log(n) times. TLE'd once but some changes passed pretests, taking around 3s

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

      You can make things easier by noticing that there are 62 primes below 300, so you can store a single long long with a bitmask of primes available, and then have a single segment tree for all primes and do all updates/queries with bitwise operations.

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

      Thanks.

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

    One segment tree for product with range multiplication and the second one with bitsets for primes in range.

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

    Segment tree got TLE with this idea. But BIT passed pretests. :(

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Now everybody knows who is the author of problem A. Of course, it's GreenGrape ;)

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

    Yeah,I thought of the idea too, But I have not done that problem....sadT_T

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

What was pretest 5 in C ?

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

what is wrong with my solution on C? 49728844

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

    Try this. 9 36.The answer should be 2.

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

    I got that :( f *= f; always create a copy of f then multiply it in the loop. it should be like : f *= copy_f;

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

20 minutes per problem? I want to think in deeper way, not just to be the fast-solving machine :( Why codeforces is pushing participants(in terms of time) so hard?

»
8 months ago, # |
  Vote: I like it -17 Vote: I do not like it

C was gay af

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

what would be the ans in test case in problem C: 5 100?

»
8 months ago, # |
Rev. 3   Vote: I like it -58 Vote: I do not like it

I_hate_greengrape

»
8 months ago, # |
  Vote: I like it +177 Vote: I do not like it

Wow what the fuck is wrong with those people bashing the authors for including anti rand() tests in pretest? If they weren't kind enough to make those pretests for you then surely someone would hack you in like 5 minutes. Do you guys seriously expect the authors to publicly announce Hurr durr just saying rand() is weak you should not use that but this problem is definitely not about random?

Maybe next time try to actually appreciate the knowledge you gained in contests.

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

First time I actually enjoyed a GreenGrape contest.

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

dissapointed with the contest overall but the setters are some weebs so what to expect

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

I think intersection enjoyed this contest!

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

    Me too.

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

      how could you enjoy such a bad contest? it was so poorly made i am legitimately starting to wonder if it was a bad joke being played on us.

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

turns out rand() has max value 32768 on CF... rip master

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

For those of you who are looking for a good and clear randomization implementation 49733774 Correct me if I'm wrong.

Thank you Akikaze GreenGrape _kun_ neal

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

WA#108 E... How to know did it fall due chance 1.86185·10 - 9?)

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

    I failed that too. It should be some hacks regrading std::random_device. I saw lots of submission failing 108 are using std::random_device.

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

      That's because the output sequence of std::random_device on Codeforces is deterministic, check this.

      By the way, you are using std::random_device in wrong way, check this.

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

      Yeah, I failed on that test case too.

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

first impression is last impression. great round!

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

NO!!!! WHY????

www.bmp

wow.bmp

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

What is wrong with this code.

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

    flag might exceed the range of lld and without fortune it can be in range [0, n - 1] again.

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

    If you have a sufficiently big prime (say, greater than 5e9), flag will overflow during your while(n / flag > 0) cycle.

»
8 months ago, # |
  Vote: I like it +67 Vote: I do not like it

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

    Hacks on RANDOM-NUMBER-GENERATOR??!! That's pure evil!!

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

      Today I learned that pure evil is less than 232. The funny thing is that random_device is deterministic on codeforces.

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

Auto comment: topic has been updated by Akikaze (previous revision, new revision, compare).

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

Why does using long double instead of long long worked for passing test case 10 in Q.C ?

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

    Even long long can have overflow issues dealing with big primes, something like 1e10 or so. 1e10 * 1e10 makes number even bigger than long long limit.

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

why my Test Case 17 is failing: Problem B @Akikaze

Test: #17, time: 0 ms., memory: 140 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input

69 9 5

-7 10 7 3 8 -9 9 -6 -5 -1 6 7 -3 10 2 3 -10 3 1 -7 -9 -10 7 2 -10 -7 -5 -5 -8 -7 4 3 10 -7 -8 7 4 6 -5 -6 8 -7 6 -5 -1 -4 0 -3 1 -2 -8 -3 -4 9 8 5 5 -5 -4 10 6 -6 -2 4 -6 -6 -3 -3 0

Output

136

12 27 41 52

Answer

136

13 32 47 57

Checker Log

wrong answer the sum of beauty in contestant's partition does not match with contestant's answer: expected sum = 136, found 130

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

    you are using the least in "bigger" numbers for several times. i got wrong on this test ,too. you should use a flag not to use it more.

»
8 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Hello codeforces, I want some advice about my sysfailed code in problem E.

https://codeforces.com/contest/1114/submission/49736873 https://codeforces.com/contest/1114/submission/49736886

the only diffrenece between two codes is random function. the one with (rand()<<15)|rand() fails at test 101, but (rand()<<16)|rand() successfully passes all cases. I thought that if cpp rand() generates [0,32767] uniformly, then (rand()<<15)|rand() can generate [0,2^30] uniformly, but the result says it isn't.

Could anybody solve my curiosity? Thanks in advance.

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

    rand()<<15|rand() does generate [0,2^30] uniformly.

    I think that test 101 is an anti-test for rand(time(0)), or in other words all values of time(0) that start from somewhere around the end of the contest until a few hours after that, which is around 10800 values for 3 hours, so any code that uses srand(time(0)) and was judged during that time will fail, resubmitting should get AC.

    rand()<<16|rand() most likely works because test 101 was based on rand()<<15|rand(), and no similar test was based on rand()<<16|rand().

    All of what I said is might not be true, but I couldn't think of any other explanation.

»
8 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Apparently, my this submission got WA on test 101 in contest time and now the same solution is getting AC.

WA Submission

AC Submission (added an extra space before the last line because they weren't allowing me to submit the same code twice).

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

    AC submission doesn't have the line x ^= 16153382;. rand() is a bad random number generator in general, and using it multiple times actually makes it worse. Also, rand() on CF gives atmost 215 - 1 anyway, so the lines x &= (1 << 15) - 1 and y &= (1 << 15) - 1 don't have any meaning.

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

      May be it's not the most ideal random number generator. But that's not the point. The point is I should get consistent verdicts if I submit the same code repeatedly. And it appears that basically using srand(time(0)); is what caused me that WA, which is frustrating because many other contestants also used it and got AC.

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

What will be the output of this test case for D:
5
6 7 6 8 6

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

    It's 3. My previous wrong solution was printing 2 for this test, because it wasn't take in consedirstion that the chosen start is unchangable, so it proceed your example like following:

    7 -> 6

    8 -> 6

    But the correct process is:

    If we choose the index 2 (with number 7) as a start, then we will change it to 6, so the array will be: 6 6 6 8 6, then we connot change the index 2, so the array should become: 8 8 8 8 6, then: 6 6 6 6 6, so the answer is 3.

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

      Thanks a lot! I too misunderstood the question. :D

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

Wow, cool song

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

alright, this is enough. i have so many times expressed my concern about programming problems being wrongfully, but intentionally mixed with math. problem C was a nightmare because it had useless math. why do you keep making these? mid problem set you think “i can’t make this hard in a challenging way so i’m just going to bombard it with some random useless stuff”? this is not okay.
also, seeing from the editorial you really didn’t care about the whole contest and/or about us either.. it was a joke. i had high hopes but they all fell short.

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

Loved this contest! Decently prepared and well-balanced. GRAPE ALL THE WAY

»
8 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Trying to make some rand(time(0)) code fail? Well, I'm not the great fan of that idea, but it can be an option if problemsetter can block every possible code that he can think of. The problem is that it's definitely impossible. If I use "rand() << 16 | rand()" instead of "rand() << 15 | rand()" by mistake, it will still work. If I use "for(int i = 1; i <= 5; i++) val = (val * RAND_MAX + rand()) % (1<<30)", which is my common random number generating code, it will still work too. If you can only make that exact random generating method, then what's the whole point of making those anti-rand tests? At this point, it's totally unfair to make some of the codes fail only by the reason that he used the same random number generator with the problemsetter.

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

    Well, my initial idea was blocking srand() and its derivatives only. I have thought of time(0) stuff, but then I didn't go on with making such failed, because:

    1. There'd be too many seeds to kill all of them.
    2. Using current time from epoch has been a common method in choosing seeds for RNGs, thus causing such approach failed (for not being precise enough to be unpredictable) would be too unfair, even to me.

    However, hacks are here and there. This kind of behaviours was unavoidable, and we still had to include such hacks into systest (tests with indices  ≥ 97 were hacks), thus making things more unfair than what I wanted at first.

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

I keep getting Runtime Error on B :( What could be the problem? I checked the memory capacity, return value, and declared them in the global variables but nothing seems to work!

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int> > vec;
bool pick[2000001] = {0};
vector<int> vec2;

bool myfunc(pair<int, int> a, pair<int, int> b) {
	return (a.first >= b.first);
}

int main() {
	int n, m, k; scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		int a; scanf("%d", &a);
		vec.push_back({a, i});
	}
	sort(vec.begin(), vec.end(), myfunc);
	long long int ans = 0;
	for (int i = 1; i <= m * k; i++) {
		pick[vec[i-1].second] = true;
		ans += vec[i-1].first;
	}
	int bucket = 0;
	for (int i = 1; i <= n - 1; i++) {
		if (pick[i]) {
			bucket++;
		}
		if (bucket == m) {
			bucket = 0;
			vec2.push_back(i);
		}
	}
	printf("%lld\n", ans);
	for (int i = 1; i <= (int) vec2.size(); i++) {
		printf("%d ", vec2[i-1]);
	}
	return 0;
}
  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think you made some mistake when you print the answer, have a try on this data :

    6 1 4
    4 3 2 2 1 1
    

    your code has output 4 numbers in the second line, while the correct case should be 3. By the way, I suggest you use > instead of >= in myfunc() , it seems that c++ requires strictly lower or bigger.

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

      Thanks! Got an AC! Hope I don't make mistakes on indexing next time...haha^^;

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

First time become blue in this round, feeling good ^_^ .

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

Wonder how to prevent hack of E by random generator

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

In problem C, I m getting WA in test case 7 . But I m getting right answer in my compiler. but CF compiler is showing another output and giving me WA in test case 7 . I m using gnu g++ 14 . Can anybody have a look at my code ? https://codeforces.com/contest/1114/submission/49753432.

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

For Problem C where can i read the necessary properties of factorial to understand the logic behind the given editorial?? I cant understand how the problem was simplified to just that. Akikaze

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

    Consider the b-ary representation of n!. Let it be represented by the digits d1,d2,d3,d4,d5,d6 (I'm considering it consists of 6 digits. It's similar for any no. of digits). Suppose last 3 digits are zero. Then it's decimal representation will be num=d1*b^5+d2*b^4+d3*b^3. The rest terms are not considered because they are zero. Clearly num is divisible by b^3. Here 3 is the maximum power of b that divides n! which is also the no. of trailing zeros. Hence proving the solution. Satisfy yourself with some more examples.

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

In problem C the system says that my code is similar xith xb2403/49705111, ciwomuli/49716822, XY_cpp/49725082;That is because C is similar with the problem P3927 and I use the solution which is last modified at 2017-10-15 14:46

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

can someone tell me why my solution is wrong?

code

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

    Try to get gcd from a[x] - a[y] for all your selected x and y, not only x and max.

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

      Hey,

      Thanks for replying

      it is still broken...

      Code

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

        I think that there is a countertest on pure random_shuffle. (Might be hack?) And sorry, using Euclidean algorithm my first suggestion is useless. (gcd(a, b) = gcd(a, b + a))

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

    You using random_shuffle for shuffling. Since it using rand() it shuffling only first RAND_MAX items which is small. Use std: : shuffle(begin, end, mt19937) instead.

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

      Hi there,

      Thanks for pointing it out! Fixed. Appreciated!

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

Problem C is an interesting maths problem. The idea is to look carefully at the b-ary representation of the number n!. It is a modification of Legendre's formula. We need to find the largest power x of b such that b^x divides n!.

»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Wow 2019_BecameMaster! You seriously lived up to your name.

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

Wow the contest makers is a group of vietnamese. Does anyone vietnamese in here

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

In problem B i am getting correct output on test case 5 on my machine but on codeforces i am getting wrong output please help. My code