By Kuyan, 7 days ago, translation, In English,

Hi all!

I'm happy to invite everyone to a combined for Div.1 and Div.2 Mail.Ru Cup 2018 Round 2, that is starting at this time: Nov/10/2018 17:35 (Moscow time). The problems were prepared by Kuyan and Jacob. Thanks to _kun_ and 300iq for coordination and help in preparation.

Also huge thanks to majk, lewin, gritukan, demon1999 for testing, and also to MikeMirzayanov for Codeforces and Polygon platforms.

This round is the second round in the new championship called Mail.Ru Cup, you can learn more about it following the link. The round will be rated for everybody!

The championship feature the following prizes:

  • First place — Apple MacBook Air
  • Second and third place — Apple iPad
  • Fourth, fifth, sixth places — Samsung Gear S3
  • Traditionally, the top 100 championship participants will get cool T-shirts!

In each round, top 100 participants get prize points according to the table. The championship's result of a participant is the sum of the two largest results he gets on the three rounds.

There will be 7 problems for two and a half hours. The scoring will be available later.

I hope you will like the problems and wish you a rating increase!

UPD1: Scoring distribution:

500 1000 1500 2250 2750 3500 4000

The round is over, congratulations to the winners!

  1. aid
  2. LHiC
  3. V--o_o--V
  4. mnbvmar
  5. tourist

The current results of Mail.Ru Cup (summing up the two rounds) are published.

The analysis is also published.

Announcement of Mail.Ru Cup 2018 Round 2
 
 
 
 
  • Vote: I like it  
  • +175
  • Vote: I do not like it  

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

Is there any AI Cup this year?

»
6 days ago, # |
  Vote: I like it -116 Vote: I do not like it

Memes and more memes . . .

»
6 days ago, # |
  Vote: I like it +20 Vote: I do not like it

NOIP2018(National Olympiad in Informatics in Provinces) is being held in China now.So we will miss a great contest.What a pity!

»
6 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Cleshes with Asia champions league-final

»
6 days ago, # |
  Vote: I like it -21 Vote: I do not like it

Cleshes with the double-11. :) (: :) (:

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

Very few users registered for this round :\

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

why would my second hacking attempt gets counted if its the same input to the same person ?

I just pressed backward in the browser and accedintally it got sent again :(

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you would get "wrong answer on hack 1" if you submit code that doesn't pass the same test.

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

      nah I'm the one hacking B) but my hacking attempt got sent twice accedintally

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

How to solve C,D,E?

Cool problems btw

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

    E. Binary search for answer, and use dp[i=we can only take values i...n][j=there is at least j values <= mid] = minimal number of segments.

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

any idea what pretest 5 of C might be?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In got WA on 5 by only considering cases where the interval of lucky days of Bob is to the right of the interval of lucky days of Alice (in the optimal case). Not sure if this will help you...

    (After considering cases where the interval is to the left I got WA on pretest 8 :( )

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

      In case of such a scenario, I swapped Alice and Bob's info and performed my calculation in the same way. So, I think I handled that.

»
6 days ago, # |
  Vote: I like it -15 Vote: I do not like it

If I had 10 more seconds I think I would have solved D! ouch

Also, how do you solve C?

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

    If I had an undefined number of seconds I would have solved F... I'm getting WA for some unknown reason.

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

    never mind, i wouldn't have solved it with 10 extra seconds either

    probably 10 more minutes

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

    My solution for C.

    I'll try explain as best as I can. Pretend array a is fixed. You can offset b by increments of gcd(ta, tb) relative to a (since the arrays are periodic). Start with the offset such that la - offset ≤ lb and la - offset is as close to lb as possible. Now push a rightwards increment by increment and check and store how many lucky days are shared each time. As soon as the number of shared lucky days stops increasing, break and print the maximum number of shared lucky days. Maybe this could be done with ternary search too, but my linear search was well under the time limit.

»
6 days ago, # |
  Vote: I like it +21 Vote: I do not like it

In D pretest 8 is something like

2
abab
ba
aaab
ba

Unfortunately, I've came up with this too late.

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

    fuck :)

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

      Fuck indeed

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain your C

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

          Assume la < lb (swap a and b otherwise) and shift everything so that la = 0. Now observe that the beginning of both periods are aligned at first, but then start to differ. This difference is always a multiple of , let this be g. So the difference between the the start of period a (which is also the start of the good days for a) and the start of good days of b is always of the form lb + k·g.

          The intersection will be maximized by either making this value the smallest  ≥ 0 (good days of b just ahead of that of a) or the largest  ≤ 0 (the opposite).

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

    Very nice. There was one more tricky idea that D was that you may need to extend the string with common prefixes and suffixes.

    Example Testcase: 2
    yaa
    xaayaa
    ybb
    xaaybb

    Here the answer is not "aa", but "yaa".

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain the logic as to how to extend the string with common prefixes and suffixes?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, I forgot to exclude variables which don't change while calculating the expansion of the string. Brilliant.

    I really hope that wasn't my only mistake...

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

    For my solution, I think it is something like:

    2
    abb
    av
    abd
    av
    

    Because, my solution will see the first 'b' and convert it to 'd' instead of second 'b', then print NO.

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

Will the following solution for F work?

Let A be an array of size n. Ai = xor of path from root to ith node. Now answer is just the kth smallest pairwise xor in A.

To do this do a binary search for value of xor. Say x is your current value. Find number of pairwise xors less than equal to x (this should be easy to do with trie). And so on...

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

    Of course, It will lead to TLE or MLE. I didn't think carefully, so spent last one hour for it :)

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

    It seems no chances to pass TL with such solution

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

Test 13 in problem D???

»
6 days ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve C?

»
6 days ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve problem c? Is there any kind of geometry involved?

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Test 7 in C?

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

Can someone help me find a corner case for my submission in B?

http://codeforces.com/contest/1055/submission/45537375

https://ideone.com/BlSehh

»
6 days ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

I have passed pretests on C with this :)

long long ans = 0;
for (int step = 0; step < 1e8; step++)
{
	ans = max(ans, segments_intersection_size(l[0], r[0], l[1], r[1]));

	if (l[0] < l[1])
	{
		l[0] += t[0];
		r[0] += t[0];
	}
	else if (l[1] < l[0])
	{
		l[1] += t[1];
		r[1] += t[1];
	}
	else
		break;
}
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell the logic?

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

      We go through good segments for Alice and Bob, one by one and check the size of the intersection of segments [l0;r0] and [l1;r1]. We iterate 108 times and store the largest intersection.

      This is pretty dumb algorithm, but since I wasn't able to come up with a hack case, I've decided to code it.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does it work for?

    1 1 6
    1 1 999999996
    
    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      I also have a bit of preprocessing:

      if (l[0] == l[1] || gcd(t[0], t[1]) == 1)
      {
      	cout << min(r[0] - l[0], r[1] - l[1]);
      	return 0;
      }
      
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I passed C with similar approach but mine gives TLE for more than 4*10^7 steps whiles yours works for 10^8. But i am sure it will fail systests.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had this idea too, but moving the intervals with binary search for K.
    But I can't prove it is correct or incorrect so I didn't code it.
    I think your solution will fail on input where one starts with '-' of huge length and another one has small interval (t).

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think your solution will fail on input where one starts with '-' of huge length and another one has small interval (t).

      Could you, please, share an example to test the code? I wasn't able to break it ;(

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe for this test case
        0 1 2
        2*10^8+1 2*10^8+2 3

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I get an answer of 2 because of my preprocessing

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

            1 2 4
            200000000 200000001 4

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

            Maybe this
            0 0 2
            10^9-2 10^9-2 10^9
            l[0] will reach its max value of 2*10^8 which is < l[1] and hence your answer would be 0 but answer is 1

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

              Shit, I should have used 5·108 as the number of steps ;)

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

                That would have lead to TLE... XO

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

                  No, that should be below 1s. The processor speed is 3.4GHz, i.e 3.4 billion of operations per second =)

                  Look here: https://ideone.com/HVDFuc It runs in 0.88 seconds.

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

                  You can use while(clock()*1.0/CLOCKS_PER_SEC<0.95)... to do as many iterations as possible.

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

                  That would be too smart for me =)

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

                  I have a doubt

                  Shouldn't we use

                  clock_t t=clock();
                  while( 1.0*(clock()-t) /CLOCKS_PER_SEC <0.95) ..
                  
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  Maybe, but I thought that at the beginning of the program clock()=0.

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

                  Ah, yes. It says that "clock() returns the number of clock ticks since starting of the program" so t will be equal to 0.

                  I thought they run multiple test cases on same program in a loop (without exiting) so I used a variable.

                  Thanks

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        this? 0 1 3 903981041 903981051 903981141

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I get 0 as an answer. Is it correct?

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't know the answer, my idea is make your solution get TLE.
            How many steps did it take?

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

            ans will be 2

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes, my code gives 2, once I increase the upper limit from 108 to 5 * 108 ;)

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

    Hmm, that was not a lucky day for me 45531559 ;)

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

What are the edge cases for problem D. I was getting WA on pretest 8.

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

    This is not an edge case -> the whole idea is wrong.

»
6 days ago, # |
  Vote: I like it +64 Vote: I do not like it

hey, this is cruel to set such tight constraints in F! Why couldn't you at least allow memory pass? :(

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

Who can explain why low number of votes?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it is because it is clashing with some other contest, or a traditional festival?

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

how to solve problem B

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Initially find the number of segments in O(N). Then per query just check if after incrementing a[p] by D, it affects the segments or not, it can affect in either of the following ways: 1. It can merge to an existing segment(sidewise elements >l), hence no change in the count. 2. It can be a new segment(consisting of itself only), in that case, its sidewise elements have to be <=l 3. It can join two segments into one(when sidewise element>l), in that case, count reduces by 1.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same thing but my code did not work

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You continuously failed on test case-3. Please check if you did check for a[p]>l after adding d to it.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes I did

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you please share the link to your code.

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

              int main() { std::ios::sync_with_stdio(false); ll n,q,l; cin >> n >> q >> l;

              ll arr[n+2];
              for(int i =0;i<n;i++) cin >> arr[i];    
              ll co = 0;
              for(int i =0;i<n;i++)
              {
                  if(arr[i]>l) fl[i] = true;
              }
              for(int i =0;i<n;)
              {
                  int j=i+1;
                  bool f = false;
                  if(fl[i]==true)
                  {
                     f = true;
                     for(j=i+1;j<n;j++)
                     {
                       if(fl[j]==false) break;
                       else f = true;
                     }
                  }
                  if(f)co++;
                  i = j;
              }   
              

              // cout << co << endl; while(q--) { ll a; cin >> a;

                  if(a==1)
                  {
                     ll p,d;
                     cin>>p >> d;
                     arr[p-1] += d;
                     if(p-1!=0&&p-1!=n-1&&fl[p-2]&&fl[p] && arr[p-1]>l&&!fl[p-1]) {co--;fl[p-1] = true;}
                     else if(p-1!=0&&p-1!=n-1)
                     {
                       if(!fl[p-2] && !fl[p]&&!fl[p-1]) {fl[p-1] = true;co++;}
                     }
                     else if(p-1==0)
                     {
                       if(!fl[p]&&!fl[p-1]) {co++;fl[p-1] = true;}
                     }
                     else if(p-1==n-1)
                     {
                       if(!fl[p-2]&&!fl[p-1]) {co++;fl[p-1] = true;}
                     }
              
                  }
                  else
                  {
                     cout << co << endl;
                  }
              }
              
              
              return 0;
              

              }

              • »
                »
                »
                »
                »
                »
                »
                »
                6 days ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                As far as I can see the checking of a[p]>l has not been given in the last two else if.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I checked it in the first if else only

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Whenever you are increasing the count of sequences, you need to check for a[p].

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ok thanks got my mistake

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

    You can also solve using segment tree like this.

    It will be useful if you want to query for any intervals.

»
6 days ago, # |
  Vote: I like it +35 Vote: I do not like it

Used a char array to store the lcp calculated by Z-algorithm on D.
How come I can't find this bug using more than 1 hour during the contest, but spot this instantly after contest......

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

    More important question is how come you couldn't find that Z-algorithm is not needed in D...

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

      Wow how to solve D? Also, more importantly, how to solve D in less than 200 lines?

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

        https://code.re/dvu

        In each pair wi ≠ w'i pick the whole substring we should fix (from first to last dismatching letters). If these strings are not same for all such pairs, output NO. Else try to widen this string out by appending maximum possible amount of letters to the left and to the right. At the end check if everything is ok.

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 5   Vote: I like it +26 Vote: I do not like it

        For each i, find the smallest interval 0 ≤ l ≤ r < |wi| in which wi and w'i differ (i.e. they are the same outside [l, r]). This interval should have the same length every word (if it exists), and it should contain the same letters for every word. This gives you your initial s and t Now you would be done, except that there are nasty cases like this:

        2
        xayxax
        yaxxax
        xayxbx
        yaxxbx
        

        Answer:

        YES
        xax
        xbx
        

        But we can print any valid solution, so we just greedily extend s in both directions while this is possible (i.e. we don't go over the border of a word or consume different letters in different words). Finally just test if the s and t you found actually work by executing the search and replace on each wi and comparing the result to w'i.

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

        My solution:

        • for each name that needs replacing, find the substring between the first and last character that's different in the original and new string
        • s has to replace this substring and leave everything else intact, so the original substrings have to be the same for all names and the replaced substrings must also be the same
        • s is this original substring with some characters added at the beginning and at the end, t is the same for the replaced substring
        • it's optimal to add as many characters at the beginning as possible and as many at the end as possible
        • now we can't extend s and t anymore, so these have to be our answer — the only thing left is to check if what they produce is correct, using KMP
  • »
    »
    6 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I looped to n instead of the size of the current string at one point in D. Same thing about noticing immediately after the contest :(

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

      Same here, although such code didn't pass my local tests, so found it fast enough.

»
6 days ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

was my comment invisible or what :P

I don't understand the logic of counting the same hacking attempt when someone send it accedintally .. why it's not like when someone send the same WA solution twice they don't count the second one

  • »
    »
    6 days ago, # ^ |
    Rev. 4   Vote: I like it -6 Vote: I do not like it

    edit: ok take that 50 points :) eventhough I insist it doesn't make sense to count 2 similar consecutive hacking attempts on the same solution

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Problem F all the downvoters

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Some identical hacks depend on the time the code is hacked, so it does matter.

»
6 days ago, # |
  Vote: I like it +97 Vote: I do not like it

Thanks for the contest! I liked the problem ideas but thought limits on problems D and F were unnecessarily strict.

D is a very nice conceptual problem, but limits require linear-time string matching (and fast-enough input to read 18 million chars in 1 second). IMO, linear-time matching does not add any depth -- a limit of N ≤ 300, wi ≤ 300 would have all the same conceptual value without requiring book code.

F is similar. Requiring linear-time bucket sort or trie traversal makes the problem much harder but not much more interesting. N <  = 105 would allow map / sort / unordered_map solutions to pass without changing the core of the problem. Also, the complexities are hard to distinguish: I've heard of some log-time solutions that snuck under TL as well as some constant-time solutions that went over.

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

    I agree 100%.

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

      Well, one more thing I would appreciate is a guarantee that the answer doesn't change in G if we change some radii by epsilon.

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

        The only geometry that is needed is Minkowski sum and checking that distance from point to polygon is less than d, it's not harder to write it in integers than in doubles.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          There is more than one possible approach.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        On ACM-style contest this is what we would probably do. But considering that this is a contest where hacks are allowed, we would need to implement such a check in the validator, which would make the validator significantly more complex.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually thought about a randomize string matching solution after trying to hack the test case (and fail) :D

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    IMO, linear-time matching does not add any depth

    I saw some depth there. For example, linear-time string matching using hashes or KMP? Hashes are faster and maybe simpler since we're only checking the first occurrence. And do we really need it, isn't there a stupider algorithm we could use? After all, the problem is quite specific and, more importantly, the lengths of strings are small. How long does it take to write KMP, what are the chances of making bugs compared to other ideas, is it worth risking anti-hash tests, is it worth risking TLE with an optimised bruteforce... all factors to consider. I decided for KMP because it's actually very simple and turned out to be a good choice.

    Plus there may be some more straightforward solutions (or parts of solutions). Consider just that the number of forbidden substrings is O(N|w|2).

    D was a very evil problem in that there are so many ways to approach it.

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

      As far as I know, strstr works in linear time in GCC and implemented as two-way algorithm.

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

        ...and is going to be extremely fast because we're matching cache lines of ~1000 4-byte blocks or ~500 8-byte blocks (depending on architecture).

»
6 days ago, # |
  Vote: I like it +12 Vote: I do not like it

What's the solution for problem C ?

»
6 days ago, # |
  Vote: I like it +25 Vote: I do not like it

debugforces

»
6 days ago, # |
  Vote: I like it +29 Vote: I do not like it

Earning a macbook air with 30 seconds. Glorious !

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

Apparently pretests in C were very weak. My code even fails to something really simple like

1 2 4
0 0 6

because I shifted by ta instead of the gcd after taking mod gcd :/

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

    Added your test to upsolving

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he only meant pretests.

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

        Mm, I misread it indeed.

        Anyway it is nothing bad actually.

»
6 days ago, # |
Rev. 3   Vote: I like it -37 Vote: I do not like it

when you expect last minute submission on G by tourist but its aid instead

»
6 days ago, # |
Rev. 12   Vote: I like it +41 Vote: I do not like it

Why isn't the contest open for practice? EDIT: it is now.

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

How to solve F? Kind of seems impossible to a noob like me

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

    Lol, that was exactly the intention of the probem setters. A noob shouldn't be able to solve a problem F.

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

      You're not answering the question. He isn't saying he should be able to solve it, just stating he wasn't, and asking how to solve it.

»
6 days ago, # |
  Vote: I like it +19 Vote: I do not like it

I dont give a sh*t if people down vote this but ive seen 2 round of this contest and both of them sucked.

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

About message

I threw the code 2 times. The first test failed. The second code is the modified first.

»
6 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Interesting, for E problem S3 * log(N) is passing easily — 45540761 :)

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

    I rejudged your solution. Sorry, tests in problem E were very weak.

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

Thanks,I benefited from this contest knowledge and Increase the rating

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

Here is a more intuitive and simple explanation for solution to Problem C which i found after struggling for a day,

Pre-requisite : Understand what we have to do

First of all, if one can make an Alice's interval and a Bob's interval coincide (in the sense that both begin in the same number) then the answer is just min(rb - lb + 1, ra - la + 1) (the length of the shortest interval).

However, this may not be possible. Sometimes it isn't possible for them to perfectly overlap ever(think about it, if you don't get it, continue reading anyway).

We intend to choose lucky intervals(one of alice, one of bob) so as to minimise the difference of the start points of the intervals of alice and bob. Now convince yourself that this will give maximum intersection.

Now the easier part, the solution :)

Consider the start points of two general intervals (one of alice, one of bob).

For alice, start point of general lucky interval is : la + k1 * ta

For bob, it is : lb + k2 * tb

Difference of start points, diff = lb- la +  (k2 * tb) -  (k1 * ta)

Now, I want you to focus on last two terms of the above expression, they are : (k2 * tb) -  (k1 * ta) where k1, k2 are general integers. That's a linear combination of t1 and t2 which always happens to be a multiple of gcd(ta, tb). In fact any multiple of gcd(t1, t2) can always be written as a linear combination of t1, t2(see Bezout's lemma for both these facts).

So we can say that the difference is of the form :

diff = lb- la + k * gcd(ta, tb), where k is yet another integer.

We intend to minimise the absolute value of diff; so we solve the equation, diff = 0(minimise diff) for k. (Note that it may be not be possible for integer value of k, i'm coming on it)

We get after rearranging,

k = -(lb- la) / gcd(ta, tb) (Don't do integer division here).

Of course, since diff = 0 isn't always possible because the start points of alice and bob may never overlap. So this k we have here must be calculated as a float value (use long double), its floor and ceiling are two integer candidates one of which will make the diff value minimum.

So with ceil(k) and floor(k), we obtain two different diff values. For both of these diff values, we calculate the intersection length of intervals [la;ra] and [la + diff; la + diff + (rb — lb)] and print the maximum intersection length for two diff values. (If you don't get this last part, think about it, it's easy, you can ask if you don't get it)

You can refer to my solution here. 45568612

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

    k*gcd(t1,t2)=k2*tb-k1*ta
    how do you know that the value
    k you got meet that k1,k2>=0

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

      What you just wrote is a Diophantine equation (In case you don't know, read it a bit), These equations have many solutions. Which means for any k, we have many k1, k2 which satisfy the Diophantine equation. K1, k2 come out in form of expressions which depend on integer parameters (After following a standard procedure of solving linear Diophantine equations).I think by manipulating those integer parameters, you would definitely find a solution with non negative k1, k2.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me what is test 2 of #B. I'm very curious about it.....