fcspartakm's blog

By fcspartakm, history, 7 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #451 (Div. 2). It'll be held on Saturday, December 16 at 14:35 MSK and as usual Div. 1 participants can join out of competition. Note that round starts in the unusual time!

The round is rated.

This round is held on the tasks of the municipal stage All-Russian Olympiad of Informatics 2017/2018 year in city Saratov. They were prepared by Olympiad center of programmers of Saratov SU. A convincing request to the participants of the municipal stage in Saratov to do not participate in this contest.

Great thanks to Grigory Reznikov (vintage_Vlad_Makeev) and Nikolay Kalinin (KAN) for helping me preparing the contest, to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and to Alexey Ripinen (Perforator) and Roman Glazov (Roms) for writing solutions.

You will be given six problems and two hours to solve them. The scoring distribution 500-750-1500-1750-2000-2500. Good luck everyone!

UPD Editorial

UPD2 Congratulations to the winners!

  1. Namys

  2. MSeashell

  3. zhouyidong

  4. ITMO.MansNotHot9

  5. meoconn

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

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

A friendly round for Chinese! :)

But, I registered for it and it doesn't show that I'm out of competition. Why?

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

I really think that CF had a difficult time, but at least last 3 contest had a decent queue and nice problems. I think CF is going in a right direction, mentioning the number of contests.

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

Last week, I saw that c.f. Round 451 would be held at 18:35 MSK. Why it comes to 14:35?

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

MikeMirzayanov , there is a clash between tomorrow's atcoder match and this , can something be done? , I dont want to miss either one of these! fcspartakm

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

    Unfortunately, we can not move the round because of the onsite high-school olympiad and Russian AI Cup Final Round. Usually we avoid such clashes but this time we can't choose start time.

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it
»
7 years ago, # |
Rev. 3   Vote: I like it -58 Vote: I do not like it

Nothing is mentioned related to rating.

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

Is it -rated?

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

MEOWWWWWWWWWW~

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

May as well be a nice warm-up before ECL Final :)

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

Will it be Sunday tomorrow in Moscow or it is just typo ?

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

GOOD LUCK !!!

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

Is this contest rated? lol

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

Not cool it overlaps with arc tomorrow. Why so early?

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

Just curious, is that a rated contest?

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

CAn yUU please, SiR, stop deleting my "is it rated?" comments/censor me ? We live in democracy which means I can freely act like a retard , not in communism where i would be put in some gulag.

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

    No

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

    You have the freedom to post senseless comments, and everyone else has the freedom to vote it down into oblivion. This results in you being hidden for negative feedback.

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

please make sure the time limit is enough

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

This is my frist contests after cet-4 , best wish for my cet-4 , besides i want to rise my points!

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

Hope for short statements <3

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

When you open Codeforces for no reason and you see a contest is about to begin in 30 mins :P. I always get an email for contests saying "Attention! Unusual start time" but this time when the timing was really unusual I didn't get any email. Not cool Codeforces :(. Anyways, it's nice to see so many upcoming contests lined up before New Year.

"The scoring distribution will be announced later." When?!

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

Scoring distribution please?

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

Nice time start point for me:)

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

The round was the best for me

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

Very nice difficulty distribution of problems.

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

Liked the fact that there were no long queues. Keep it up.

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

is D some directed graph problem

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

    I think that greedy will work fine here. Remove the last alarm clock while there is at least k alarm clocks in segment.

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

      Did you use binary search in your solution?

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

        No binary search is needed. Since times are <= 10^6, you can create a vector of bools from [1, 10^6] and iterate over windows of size m to simplify implementation.

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

    D was DP+ segtree After sorting.. when u see that u are at a time ti such that there are >=k alarms within time ti-m+1, just turn of the ith alarm. maintain the sum using segtree

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

      If you use a sliding window, you don't need a segtree.

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

      I've solved D with FFT and made some optimizations to pass the TL.

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

    Greedy on time and sliding window may help you.

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

    I think problem D is two pointers + data structures

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

How to solve F?

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

    If the length of c is n, the maximum length of a and b is n or n - 1.

    With each possible length of c, we only need to check for 2 cases.

    To calculate a, b, c in each case, we can use Hash. The hash value of a + b is the sum of hash value of a and the hash value of b.

    And remember to check if there is some 0 at the beginning of a, b, c when the length of a, b, c is greater than 1.

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

      Can you please explain, how are you using hashing? I am not aware about the concept of hashing. Also, how can you say the hash value of (a + b) is the sum of the hash value of a and the hash value of b?

      Thanks.

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

How to solve problem D?

I thought of segment tree solution but was unable to get it accepted. :(

Edit -

My basic idea was to assign 1 (in the array) to the minutes when alarm clock rings and in each iteration, find the sum from i to i + m minutes, say it p.

If it is less than k, then no problem. Otherwise update the array from range L to i + m and make each element in it 0. It can be done by lazy propagation and about finding that value L (from where we have to update the range) , it can be done by simple binary search.

Can anyone tell me, what I was missing or was I wrong with my logic?

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

    I solved it using BIT tree. Just maintain at each index how many clocks are there and while checking for any time i just see the number of clocks present between i and i+m time interval and if it is greater than or equal to k just update index i+m with negative value equal to abs(val[i+m]-(k-1)).

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

    I think it's somewhat greedy but not sure about that!

    What i did was that first make an array of alarm point(as there are only 1e6 alarms and all distinct!) and then take a window of size m and if it contains more than k then i start removing from last on alarm(as removing this makes sense and help to optimize our answer for the next step). Finally slide the window and calculate the number of alarms thus removed.

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

Hints for D? I was thinking binary search but am not sure and couldn't get it to pass

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

    A sliding window algorithm. And remember the greedy strategy, its always the best to turn off the last alarm clock.

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

    sliding window

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

    I was also thinking about it for a while, but I don't know how can we check in O(n) that we can choose alarm clocks so that they don't intersect too much.

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

How did people manage to solve D in 5 minutes? =)
Is it some kind of a standart problem?

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

    A sliding window algorithm did it for me. Hope it passes the systests.

    UPD: It did. XD

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

      I know what sliding window is, but I don't know how to solve this problem.

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

        use greedy technique for that. Delete last alarm clock.

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

          Why is it correct to delete the last one?

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

            Because if another alarm clock intersects with the previous ones, it's better to remove an alarm ending at an earlier time instance compared to one ending later.

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

            Cause, that will help the most. The first alarm clock will be the first one to leave the span of m minutes. So, there may be a case that there exists exactly k-2 alarms in the range starting from last alarm clock.

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

            Cause that clock will be part of more up coming window.

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

This round is true Div.2 round: when most of the problems are solvable for Div.2 participants.

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

Why change the statement and not send a annoucement???? consequence -> consecutive Consequence ??? How can i know this...

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

Hey, this submission(33299805) says runtime error...while checking with Diagnosis in custom test, its says,

p71.cpp:57:24: runtime error: member access within misaligned address 0xbebebebe for type 'trieNode', which requires 4 byte alignment
0xbebebebe: note: pointer points here
<memory cannot be prin...
Runtime error: exit code is 1

I don't understand.. Why this happened? it's ruined my mood & I have left contest.. Now, there will be a disaster in my rating. :(

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

Lol, can someone(MAYBE CF ADMINISTRATION) explain me why I can`t hack one submition twice?

I hacked once and got an "Invalid input" because of the EOL in the end. After I corrected my test CF says "Submit already challenged". LOL, REALLY??? So then I must know if the EOL is needed there before hacking????

Due to this issue I didn't get 200 points on hacks.

THX, CF.

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

    So then I must know if the EOL is needed there before hacking????
    Yes.

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

      So why it is not mentioned on the hacking page, hah?

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

What is testcase 7 in F ???

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

    Did you check for 0s at the beginning of a, b, c if their lengths are greater than 1?

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

EDITED

In Problem-E, my first submission got WA in pretest 9. But, then I relocated my long long ans = 0 variable at the top of main function and got pretest passed after submitting. Why did that happen? I was looking for the bug for such a long time, maybe like 30 minutes. Then I just gave up and then did the above thing on a whim and got accepted. but why?

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

    declaring long long ans in main might have garbage value. oustide main is 0

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

    maybe you did ans += something; before there is any value on ans, the value of ans before declared, inside main is random, CMIIW

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

    You also changed your comparator function.

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

      The change in comparator function looks insignificant to me. Either way, the sorting will be the same

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

Is greedy work for problem E?

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

It is rated?

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

    Near perfect conduction of an announced rated round. Why even bother asking?

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

I am getting Wrong answer on pretest 8 for 2nd problem (B) My submission

Can someone please help? I used the Extended Euclid algorithm to solve it.

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

    There is another "NO" case.
    Suppose "X" is non-negative and "Y" is negative.
    You obviously want to make "Y" non-negative by subtracting numbers from "X", right?

    Here, there is a possibility of making "X" negative even though you manage to make "Y" non-negative.

    In short, "X" and "Y" cannot be both non-negative in this case.

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

      I solve that case looking for minimal non-negative "Y" in O(1) and thus checking non-negativity of "X"

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

Speed up this system testing, I can't wait to see how many problems will fail from the 6 : |

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

    Speed up this rating updates, I can't wait to get my new COLOR xD

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

Very Good Contest! Great thanks to the author!

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

I got some issues hacking. From the second hack, it always navigates to the hack summary page without the hack popup where I can enter my hack case.

So I am not able to hack others in the same browser. I have to switch to a different browser or use a different computer. Did it happen to others?

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

My solution (33309422) for problem C gets wrong answer on pretest 1. Whats wrong here ?

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

    You have to print how mnay lines of output you have

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

      Thanks. I feel so terrible for such a silly mistake...

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

        It happens to all of us at some point; if you ever see a problem with a VERY early pretest (like 1, 2, or 3), you can use the fact that CF will judge the example test cases as the first pretests (at least in my experience they always have). So if you fail test 1, you can diff check with the sample output and find out that you have a formatting error.

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

      Yep, I too didn't do that in my first attempt! Got a WA. :/

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

can someone please look into my code why it is giving RE on sample test(3).

code : https://ideone.com/8dFo4E

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

    One doesn't simply code trie when the string lengths are  ≤ 10.

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

      yeah but i have wasted a lot of time in it! please help.

      btw i didn't think that trie is making problem it's only when we have a string of length 1. if i remove all those then it runs fine. And when there are string of length 1 then builder is not working correctly. please help!

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

UPD: I have changed my MIND.. if you want to downvote me then you are welcome :)

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

    Wow, how did you find that?

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

      May be I was lucky :D

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

        Damn, you must be really lucky and skilled to find those 2 submissions!

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

    Lol. They're the same submissions. Think for a moment before slinging mud on others.

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

    lol. Didn't even bother to change submission id

    Edit: codeforces saves all revisions you know :P

    Edit2: looks sufficiently different to me

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

    submission link is updated.

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

IS O(sqrt(ai)*n) sufficient to pass the tests in problem E ??

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

    sqrt(ai) ~= 3.16*10**4 (max)

    n = 2*10^5 (max)

    no of steps ~= 6.3*10**9

    extremely low chance of passing, unless the constant factor is really low

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

      Because I've seen many solutions pass the tests even though they used O(sqrt(ai)*n) solutions !!..

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

I think the diagnosis process makes the system test so slow. But I am pretty sure that many of the contestants do not or less care the diagnosis result. So this is just my small suggestion, what about running the diagnosis only when the contestant wants? For instance, by clicking run diagnosis button on submitted code. This may reduce the server load a lot, making system test faster, and contestants can know their ratings earlier, which most of the contestants care about. Can I share your opinion?

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

    Are you sure the diagnosis is even running? I could not see diagnostics after WA (on pretests and when submitting now)

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

      33314427

      Maybe WA does not run the diagnosis.

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

        originally the blog said, it would run for WA and RTE, but seems so

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

My first Div.3 contest!

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

Good contest, comprehensible statements, short systest pending time.

Many thanks, although I lost my perfect chance to solve the last problem for the first time, just because I forgot checking the leading zeroes :<

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

the E task should be D or even C

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

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

Can anyone plz point out my mistake in E, I wrote a pretty easy solution- http://mirror.codeforces.com/contest/898/submission/33306957

Thanks

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

My solution for D gives runtime error on testcase 3 but runs fine on my system http://mirror.codeforces.com/contest/898/submission/33302108 Help please!!!

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

For problem C I think my output for the first test case is correct ,can anyone tell me why my first test case output is wrong.

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

I really don't think this round is good. The rates of algorithms used in the contest are not in equilibrium. 3 problems(ABC) don't need any skill or algorithms, and C is just grand-grand-great simulation. And 2 problems(DE)are just greedy, which doesn't need advanced algorithms. Even DP and graph theory don't exist in problems. And the quality of the problems aren't high as well, here "quality" means the well-situated difficulty for Div. 2. (Because I can only AC around 2 problems before, but this time I can do 4 if I have a little more time)

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

    I'm beginner and I'm glad to see such problems like A or B. No one in the entire world started walk right after birth. Those problems actually makes me think that I can solve more then just 1 or 2 problems in the next contest. And yeah, it keeps me motivated, and don't give up from CP. If the contest was too easy for you, move to div1 and try to beat tourist:)

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

      Actually I don't think the round is too easy for me. As what I said, I can do 4 if I have enough time. I am still far from AK(solving all). But I just think it's much easier than most of the div2 contest before:) Maybe the round still has an advantage that it gives us encouragement. Maybe what I said in the last discussion is not fit, so I pay apologize about it. But if all of the div2 contests on codeforces are "encouraging rounds", what will it be like?

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

Can someone discuss their F solution ?

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

Good work! Very interesting tasks.

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

%zu printf specifier is not recognized... this cost me an accept in C :(

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

For Question B, if we do brute force according to editorial, we will get TLE on test 49 for Python...

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

    Did you try PyPy?

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

      oh yes now it passes!! Thanks so much!! So next time I want to submit Python code I should use PyPy as it runs much faster?

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

        Yes. But there is some difference in Python and PyPy.So read the docs.

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

Hey guys, I didn't do well yesterday because I was stuck on Problem C for a long time. I used std::set to store the telephone number, and I iterated the set to check if they were suffix to each other, and I delete the elements while iterating and I got runtime error. Can anyone please tell me how the set works while erasing the elements. Thanks a lot.

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

For Problem F,I use unsigned long long without modulo (let the hash overflow naturally) and Rabin-Karp Algorithm to check whether the answer is ok,the verdict shows TLE on test 77.However,if I add a modulo which is only 23333 (only about 2e4) and use the same way to check,it got accepted in only 78ms.So can I assume that you intend all the hashing algorithm without modulo to fail?I don't think it's good for a hashing problem,especially when I use Rabin-Karp to check and it still can't pass.:D

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

    I think, during the contest someone passed pretests with overflow hash and someone just hacked this solution, as a result a counter-test for overflow hash was added in the final test set.