Mail.Ru Cup 2018 Round 2

6 years ago, # |

← Rev. 2 →

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 :(

→ Reply

riadwaw

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

+19

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

→ Reply

brdy

6 years ago, # |

How to solve C,D,E?

Cool problems btw

→ Reply

Len

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

contest_dhuye_pani_khai

6 years ago, # |

any idea what pretest 5 of C might be?

→ Reply

FelixMP

6 years ago, # ^ |

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 :( )

→ Reply

contest_dhuye_pani_khai

6 years ago, # ^ |

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.

→ Reply

farmersrice

6 years ago, # |

-15

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

Also, how do you solve C?

→ Reply

6 years ago, # ^ |

-22

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

→ Reply

farmersrice

6 years ago, # ^ |

← Rev. 2 →

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

probably 10 more minutes

→ Reply

aryaman

6 years ago, # ^ |

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(t_a, t_b) relative to a (since the arrays are periodic). Start with the offset such that l_a - offset ≤ l_b and l_a - offset is as close to l_b 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.

→ Reply

Vshining

6 years ago, # |

+21

In D pretest 8 is something like

2
abab
ba
aaab
ba

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

→ Reply

NMouad21

6 years ago, # ^ |

fuck :)

→ Reply

meooow

6 years ago, # ^ |

-11

Fuck indeed

→ Reply

I-Owe-You-So-Much

6 years ago, # ^ |

Can you please explain your C

→ Reply

meooow

6 years ago, # ^ |

← Rev. 2 →

Assume l_a < l_b (swap a and b otherwise) and shift everything so that l_a = 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 $\text{[math]}$ , 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 l_b + 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).

→ Reply

I-Owe-You-So-Much

6 years ago, # ^ |

Yes, got it. Thank you!!

→ Reply

proofbycontradiction

6 years ago, # ^ |

← Rev. 2 →

+15

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".

→ Reply

IceKnight1093

6 years ago, # ^ |

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...

→ Reply

aboAdnan

6 years ago, # ^ |

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.

→ Reply

0101-1001

6 years ago, # |

← Rev. 2 →

Will the following solution for F work?

Let A be an array of size n. A_i = xor of path from root to i^th node. Now answer is just the k^th 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...

→ Reply

chemthan

6 years ago, # ^ |

← Rev. 5 →

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

→ Reply

MrDindows

6 years ago, # ^ |

← Rev. 2 →

It seems no chances to pass TL with such solution

→ Reply

0101-1001

6 years ago, # ^ |

Then how to solve it? :p

→ Reply

C137

6 years ago, # |

Test 13 in problem D???

→ Reply

6 years ago, # |

How to solve C?

→ Reply

mishi_gun

6 years ago, # |

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

→ Reply

TheRedLegend

6 years ago, # |

Test 7 in C?

→ Reply

6 years ago, # |

← Rev. 3 →

+20

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;
}

→ Reply

6 years ago, # ^ |

Can you please tell the logic?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

We go through good segments for Alice and Bob, one by one and check the size of the intersection of segments [l₀;r₀] and [l₁;r₁]. We iterate 10⁸ 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.

→ Reply

6 years ago, # ^ |

Why 10^8?

→ Reply

6 years ago, # ^ |

It is the largest number of operations which passes the time limit of 1 second.

→ Reply

TheRedLegend

6 years ago, # ^ |

Does it work for?

1 1 6
1 1 999999996

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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;
}

→ Reply

21August

6 years ago, # ^ |

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.

→ Reply

Serh.kry

6 years ago, # ^ |

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).

→ Reply

6 years ago, # ^ |

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 ;(

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

I get an answer of 2 because of my preprocessing

→ Reply

poojanpatel101

6 years ago, # ^ |

← Rev. 2 →

1 2 4
200000000 200000001 4

→ Reply

6 years ago, # ^ |

What's the right answer?

→ Reply

poojanpatel101

6 years ago, # ^ |

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

That would have lead to TLE... XO

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

VladProg

6 years ago, # ^ |

+12

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

→ Reply

6 years ago, # ^ |

+14

That would be too smart for me =)

→ Reply

rtanmay

6 years ago, # ^ |

I have a doubt

Shouldn't we use

clock_t t=clock();
while( 1.0*(clock()-t) /CLOCKS_PER_SEC <0.95) ..

→ Reply

VladProg

6 years ago, # ^ |

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

→ Reply

rtanmay

6 years ago, # ^ |

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

→ Reply

Serh.kry

6 years ago, # ^ |

this? 0 1 3 903981041 903981051 903981141

→ Reply

6 years ago, # ^ |

I get 0 as an answer. Is it correct?

→ Reply

Serh.kry

6 years ago, # ^ |

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

→ Reply

poojanpatel101

6 years ago, # ^ |

← Rev. 2 →

ans will be 2

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

+21

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

→ Reply

utsav_deep

6 years ago, # |

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

→ Reply

P___

6 years ago, # ^ |

+11

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

→ Reply

6 years ago, # |

+64

hey, this is cruel to set such tight constraints in F! Why couldn't you at least allow $\text{[math]}$ memory pass? :(

→ Reply

rsFalse

6 years ago, # |

-8

Who can explain why low number of votes?

→ Reply

proofbycontradiction

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

how to solve problem B

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

I did the same thing but my code did not work

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

yes I did

→ Reply

6 years ago, # ^ |

Can you please share the link to your code.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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;

}

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

I checked it in the first if else only

→ Reply

6 years ago, # ^ |

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

→ Reply

code_hard123

6 years ago, # ^ |

← Rev. 3 →

You can also solve using segment tree like this.

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

→ Reply

hohomu

6 years ago, # |

+35

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......

→ Reply

6 years ago, # ^ |

-28

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

→ Reply

gamegame

6 years ago, # ^ |

+21

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

→ Reply

6 years ago, # ^ |

-20

https://code.re/dvu

In each pair w_i ≠ 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.

→ Reply

6 years ago, # ^ |

+42

size_t lol = s[i].find(A); — isn't this O(len²), so the whole thing is O(n·len²)?

→ Reply

gen

6 years ago, # ^ |

-32

Isn't it linear? http://www.cplusplus.com/reference/string/string/find/

→ Reply

6 years ago, # ^ |

I checked that exact website before posting my comment ;p

"Unspecified, but generally up to linear in length()-pos times the length of the sequence to match (worst case)."

→ Reply

gen

6 years ago, # ^ |

Oooh, I didn't read it carefully. Thanks!

→ Reply

https://github.com/gcc-mirror/gcc/blob/3f6823abf8d0ce23804dfbfe32c6250824501ef6/libstdc%2B%2B-v3/include/bits/basic_string.tcc#L1189

6 years ago, # ^ |

It's not guaranteed. But it's also unspecified and I heard that it works very fast in G++ and... Yes, I got AC with it! 45522523

→ Reply

TimonKnigge

6 years ago, # ^ |

Looks like they just visit all occurences of s[0] and then match greedily:

→ Reply

6 years ago, # ^ |

Hmm. So, weak tests or does it work fast on CF? Or maybe the constant factor is very small?

→ Reply

Jacob

6 years ago, # ^ |

-23

Just naive search actually doesn't pass. We also found out that string::find gets accepted, but couldn't easily find any test that fails it. Perhaps this is due to memcmp being pretty well optimized.

→ Reply

cdkrot

6 years ago, # ^ |

We tested it. I think just the constant factor being extremely low

→ Reply

TimonKnigge

6 years ago, # ^ |

← Rev. 5 →

+26

For each i, find the smallest interval 0 ≤ l ≤ r < |w_i| in which w_i 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 w_i and comparing the result to w'_i.

→ Reply

6 years ago, # ^ |

+21

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

→ Reply

mango_lassi

6 years ago, # ^ |

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 :(

→ Reply

Gassa

6 years ago, # ^ |

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

→ Reply

6 years ago, # |

← Rev. 2 →

-15

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

→ Reply

6 years ago, # ^ |

← Rev. 4 →

-6

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

→ Reply

6 years ago, # ^ |

Problem F all the downvoters

→ Reply

brdy

6 years ago, # ^ |

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

→ Reply

scott_wu

6 years ago, # |

+97

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, w_i ≤ 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 < = 10⁵ 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.

→ Reply

6 years ago, # ^ |

+36

I agree 100%.

→ Reply

6 years ago, # ^ |

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.

→ Reply

aid

6 years ago, # ^ |

+23

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.

→ Reply

6 years ago, # ^ |

There is more than one possible approach.

→ Reply

Jacob

6 years ago, # ^ |

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.

→ Reply

ContestDestroyer

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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|²).

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

...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).

→ Reply

_greymatter

6 years ago, # |

+12

What's the solution for problem C ?

→ Reply

rotavirus

6 years ago, # |

+25

debugforces

→ Reply

Lord_Zebellak

6 years ago, # |

+29

Earning a macbook air with 30 seconds. Glorious !

→ Reply

mango_lassi

6 years ago, # |

← Rev. 2 →

+11

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 t_a instead of the gcd after taking mod gcd :/

→ Reply

cdkrot

6 years ago, # ^ |

+16

Added your test to upsolving

→ Reply

zoomswk

6 years ago, # ^ |

I think he only meant pretests.

→ Reply

cdkrot

6 years ago, # ^ |

+21

Mm, I misread it indeed.

Anyway it is nothing bad actually.

→ Reply

nikolapesic2802

6 years ago, # |

← Rev. 12 →

+41

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

→ Reply

SevenDeadlySins

6 years ago, # |

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

→ Reply

Jakube

6 years ago, # ^ |

-12

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

→ Reply