They were held for russian-speaking users only.

The rounds are identical, but there are six different problems :)

'#470' and 'VK Cup' is basically the same.
Because they'll have the same problems.
That's why it's called "#470 based on VK Cup 2018 Round 1".
And you can participate in #470 div.2.

Yes, that is true. Solving all six of them is still quite a challenge.

Yes!

Are you sure you don't want some downvotes? Maybe just one?

but i decide to attend the contest,because the contest is one of the most contest of Russian.so we can talk with the more expert students.

I think the time is quite good in your timezone?
It'll be 21:35 if I'm right...

Thanks ! :) majk

Perhaps it would be better to publish them after contest, not before.

Great Deduction.

No worries, the problems will also be in English. We'll check the registration page, thanks for reporting.

tourist's solution for Problem D falied on main tests.

announces X1 = 14 Bob picks prime 5
then x2 = 15

yeee)

Iterate over X0 and prime P that divides X0 (note that there are at most 7 such primes) Than you form X1. Than iterate over primes that are less than X1 and find X2. If X2 is same as input X2 than X0 is the answer.

I'm not sure if my approach was optimal, but here it is always. First, we can use Sieve of Eratosthenes to quickly compute all the primes strictly smaller than N (our given number). Now, we know the number X2 must have been the result of multiplying a prime. So, for each prime smaller than N that N % i == 0, we can compute a number (N — prime). This number is our lower bound for X1, because if we picked, lets say prime P, in order for the next multiple of prime P to be N we must add 1 to the previous multiple of P. Therefore, our X1 must lie between (N — prime + 1) and N. We can simply try all primes less than N and compute their next multiple bigger or equal than than (N — prime + 1) via binary search. Our answer is then the minimum of (Next_Multiple — Current_Prime + 1), using the same rule to find (N — prime + 1). If Next_Multiple is equal to Current_Prime, then take the minimum of the current answer and Current_Prime.

I hacked 3 Div2C solutions in my room by forcing TLE with the max test of the form

100000
1000000000 1000000000... 1000000000
1 1 1 1 .... 1

Naive solutions fail this case.

I thought I didn't understand the problem at first...

I beg to differ

Gotham PD — Codechef

The base idea is exactly same in the two problems

Answer is 0 right.

My solution failed all always in test 8 but it gave me 0 for that test. Is the judge solution OK ?

Input: AAAA BBAAAA 1 1 4 1 6

output: 0

Note that you can interchange between Bs and Cs. Also you can convert B to A...AB. However you can never create more As to the right of last B. Combine these facts and you'll see that you just need the count of Bs and Cs and the length of longest suffix that is all As.

B->AC->AAB->AAAC->C

C->AB->AAC->AAAB->B

when B ~ C

A->BB

B->AB

AAA->''

before B we can make A, add 'kill' AAA, so we can make any number of A

so when we take substring we interested in count of B and count of last A

and then where some easy cases (you can look in my code, after system testing)

Can you explain the solution?

Yes, and pretests are checking for random cases. If you're lucky, you will get WA immedeately, if you're unlucky you'll get it after the contest. I think pretests should either check all the cases or almost none of them like in topcoder.

Me solving D

It completely ruined my contest :/

I am sorry you feel that way. I am especially not happy that you came back to CF after such a long time and got beaten this way.

I've read the discussion about the problem D and hacks in general, and I have sympathy for the cries. I fell victim to pretests a few times as well. Most notably, on AIM Tech Round 4, where I got WA on systests because std::random_device was deterministic on MinGW. That night I though I don't have what it takes to be red and would never become one.

The problem was initially suggested as somewhere between Div1A and Div1B. During testing we realised that some of the cases are really difficult to spot, and hence it navigated all the way to Div1C (I purposefully do not call it D, as the intention was that Div1 has an extra problem at the beginning, not at the end). The idea was to put the main cases in the pretests, but leave the tricky one for systest and or hacks.

Depending on whether I would notice the tricky case in D myself or not, and was hacked or not, I might have been upset too. It was an unusual problem, but I don't consider it to be a mistake the put the problem in the set.

Sure, some people took the risk. They locked the problem that evidently had a lot of cases without having a proof that their code is correct. Later they realised that there was a case they didn't cover, either by noticing it in someone else's code, or getting hacked themselves. Risks sometimes don't pay off.

Some people were lucky to get hacked early enough. Everyone was, however, able to look at the scoreboard 20 minutes before end of contest and see that it is full of hacks. If you have twenty minutes left and are nowhere near finishing E or F, a reasonable strategy is to revisit problem D, perhaps try to come up with a more formal proof or write a brute force solution to compare with.

I view competitive programming a challenging leisure activity that gives us a balanced mix of two feelings — frustration that I cannot solve a problem, and happiness that I was able to solve one. It's okay to be upset if you do badly, it's okay to be mad at the problemsetter who caused this. You'll do better in next contest.

Remember that there is also another goal of CP for many people, and that is to prepare themselves for future employment. In the software engineering world, you also have pretests and system tests. The difference is that you sometimes get a wrong answer on systest few years after submission. And the consequences may be much more severe than a few rating points.

'Only 5 minutes left. I can't solve F. I'll just do while(CLOCKS_PER_SEC * 3.8 > clock()) and pray for AC.'

"Pretest Passed"

???

Solutions are not visible at the moment.

No i solved it without segment tree.

DIV2C can be solved easily with using Binary Search.

Lazy prop might work, but a priority queue and a variable might do the trick.

I used binary search and a Fenwick tree with interval updates and queries for element values. I didn't involve any lazy propagation, but did the horrible mistake to miss to change the type of the resulting array to be long[] (not int[]), and that's why I didn't pass the pretests, I think.

Now I'm waiting for the system test to finish and to resubmit my updated code and if it gets accepted, then I'll declare myself as a total idiot.

I solved it using Binary Search. For each day i, binary search on how many days it can melt 'fully' before it cannot melt temp[j] on the day j. We can binary search on the prefix sums of temp[j] to find this. Then, we can use a sweep-line trick to update ranges in our answer array. Update res[i]++ and res[e + 1]--, which e is the last day the current snow pile can 'fully' melt. But what about the remaining snow? We can just add this to the next day. So lets have another array add[] and update add[e + 1] += (remaining snow). Assuming sum is the current prefix sum of res[] on the i'th day, then the answer for each day is then sum * temp[i] + add[i];

Keep in mind the case where the amount of snow on day i is less than temp[j]. Then, we can just do add[i] += a[i], where a[i] is the amount of snow built on day i because the pile will never make it past the day it was built on.

AC Code: 36172821

Calculate prefix sums of T and binary search with each V -> O(N log N) solution.

we can do it using binary search + prefix sums , I don't think Lazy propagation helps here.

I wrote something like partial sums.

i use binary indexed tree + binary search ...

but just binary Search is enough

  ll add = 0;
  for(int i = 1; i <= n; ++i){
    s.insert(add + v[i]);
    add += t[i];
    ll ans = 0;
    while(!s.empty() && *s.begin() <= add){;
      ans += *s.begin() - (add - t[i]);
      s.erase(s.begin());
    }
    ans += (int)s.size() * 1ll * t[i];
    printf("%lld ", ans);
  }

Here's part of my code, I think it is pretty self-explanatory.

Thanks everybody, interesting to see so many different solutions for this.

I myself did use Lazy Propagation, which passed in 78ms, so I guess it was a good approach as well anyways.

anti tourist ? ?

I think that majk successfully arranged an "Anti-algorithm" contest. This problem had much more emphasis on hacking, case-bashing, constant/log optimizing and not falling prey to weak pretests than any real problem solving. Congrats indeed.

It's no surprise that tourist would do badly on such a contest. Moreover, strong participants have done very poorly on this contest as well. I can only hope that the next contest is back to normal.

50 points are returned.

These sentences are useless and make the whole problem long and boring.....

According to a few comments I've seen of yours, you really should control your temper, pal.

You need to learn to fail.

Wait, is that matthew99 overreacting to a Codeforces round? The guy who already posted a few times on Facebook about killing himself due to an unaccepted problem? How unexpected! Seriously, stop crying like a little girl after everything, you ain't the first or the last person to fail a contest.

next time buy a pair of plastic glasses like mine

It basically feels like you figure out a solution of a problem and you can't code it in time,it feels annoying. But nonetheless,control your temper and learn why you fail.

Honestly, I definitely understand.

Even if I don't lose rating, I regret doing this contest in the strongest terms possible. There are many contests in Canada that are known for having unnecessary and irritating complications to tasks, but this is significantly worse than any of them. I think the first paragraph of this problem describes it quite well. Although I would much rather have my keyboard stolen than deal with strangely ordered problems, meticulous time limits (on A and C) or the programming equivalent (in terms of messiness and suffering) to coordinate bashing in math, otherwise known as D.

I feel even worse for the students competing in VK cup, who had even more at stake than simply rating.

Please let this be a lesson in what not to do when setting a CF contest.

I was stuck in gray for 2 years and still have my glasses.

just kidding to make you forget the failure

No. We have an deterministic solution, but intended to let O(N²) pass, as it was difficult enough. None of our random solutions succeeded, but some were able to pass quite a few tests.

Can you please tell me what do you mean when you say the intended solution was random?

Let's define the state of the game as (x,p) where x is the current number and p is the prime we used to achieve it. The states from which we might have come here are in the range:(x-p+1,x) and some prime divisor of them. Well, it it is always better to choose the biggest prime divisor(gives you the most possible states) and knowing that, we can just precompute the largest prime div of every number from 1 to X and get a N^0.75 solution.

Let f(N) be the largest prime factor of N. Iterate from N - f(N) + 1 to N and for each composite number x, find the smallest x - f(x) + 1

It's convolution (plus some multiplicative factors), so FFT is answer.

Also, can someone share a standard implementation of binary trie? I could only think of implementing it through pointers and doubt, that is what people use in CP.

Seeing many people implementing Tries made me wonder: am I the only one directly using the built-in multiset in C++ for that problem? (provided that my late source code would get AC)

Btw here is my intended solution.

Thanks for giving me another problem which can be solved with trie.