The round 1 of VK Cup 2018 will take place on March 10 at 18:35 MSK (check your timezone). The contest "VK Cup 2018 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, along with teams that qualify in the Wild Card Round 1 a week later. As usual, there will be two parallel rounds for those ineligible to participate in VK Cup, one for each division.

I'd like to thank KAN for steering my crazy ideas into a coherent unit, the coordination and also for suggesting one of the problems, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 and misof for testing the problems, MikeMirzayanov for building Codeforces and Polygon and VK for organising the contest.

All three rounds last **2 hours**, and all are **rated**. The VK Cup and Div. 1 will have **six** identical problems while the Div. 2 contest will consist of **five** problems. The scoring distribution will be announced before the contest.

The main heroes of this round will be Alice and Bob. Beware that Eve might attempt to foil their plans.

This is my first round on Codeforces and hopefully not the last. Wish you many submissions, high hacks and successful rating.

UPDATE: The scoring in Div.1 and VK Cup round 1 is 500-1000-1500-1750-2250-3000. For Div.2, it is 500-1000-1500-2000-2250.

UPDATE2: The round is finished. I hope you enjoyed it. Tune in a bit later for editorial.

UPDATE3: Congratulations to winners!

Div.1

Div.2

VK Cup

UPDATE4: Editorial

" Wish you many submissions, high hacks and successful rating."

I am assuming there will be lot of hacks

Looking forward to the round)

Can the test in English?

When and where were the two qualification rounds held for VK Cup Round1 ??

They were held for russian-speaking users only.

But why orbitingflea and zhangzy can register? They're both Chinese.

I know a lot of guys that they're not russian but they registered the contest...

with just using a little bug(changing the page's language!):)

They passed qualification. I think they translated russian statements during it

The translation of "...Раунды VK Cup и первого дивизиона будут иметь шесть задач, одинаковые в обоих раундах." is somewhat awkward. A better one is: "...The VK Cup and Div. 1 contests share the same six problems while the Div. 2 contest consists of five problems.

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

Hi, im confused with the round announcement, can anybody please answer below 2 questions,

1) Why there are 2 contests (#470, VK Cup) held at the same time ?

2) What does it mean "#470 based on VK Cup 2018 Round 1" ?

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

Div. 1 will have six "identical" problems :OYes, that is true. Solving all six of them is still quite a challenge.

Cool!! Let's hope the problem statements will be identically short for both the Divisions :P

(please read the 'for teams' part before downvoting!)

is it rated for teams?

Yes!

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

No thanks!

i have a lot of them :(

Are the downvotes rated?

I think you are in a good position now to see for yourself. :P

Haha, yes. But I was just pulling OP’s leg — I guess kids are too bored with that joke.

What a sad time for Chinese :(

23:35 :(

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.

This is a good time of the contest for Russia. But unfortunately not for everyone.

I think the time is quite good in your timezone?

It'll be 21:35 if I'm right...

I hope this contest will make me

green!UPD: I am

greennow :)Thanks ! :) majk

editorials ?

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

Div-1 will be six problems,but div-2 five problems. I think after five it will be more complex problem that is unsolvable for div-2.

Great Deduction.

Will the problems statements be in English? The registration page is showing me T&C in Russian

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

[deleted]

Will we see

touristtonight? Exciting!I hope this contest will make me green once again...!!!!

`"Wish you many submissions, high hacks and successful rating."`

I wish you successful submissions, high hacks and many rating, too. :)

Excuse me, will the contest of Div.1 & 2 be Russian, too? (I know VK Cup Round 1 is only for Russians but what about the parallel Contests?)

UPD: My fault, Answered before: here

B>Ctourist is in the house!

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

CF-Predictor broke or something?

948B

In the second case, let X0 = 8. Alice picks prime 7 and announces X1 = 14 Bob picks prime 5 and announces X2 = 20.

Is the test case wrong?

announces X1 = 14 Bob picks prime 5

then x2 = 15

it was a terrible decision to keep thinking about problem B.. I should have tried problem C :(

Lol Div2B harder than Div2C/D

yeee)

Really nice problems this round, looking forward to see the tutorial.

How to solve div2-B ?

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.

Why would you assume the the first prime divides X0?

I don't

You say iterate over X0 and prime P that divides X0. Why does P has to divide X0? According to the problem statement any P less than X0 is a valid option.

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 came up with exact solution after 10 mins the contest ended :(

Can anyone share hack for C ?

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

Naive solutions fail this case.

Original C, never coulda come up with such task.

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

You seem to be right, my bad.

TIL (x-y)%z != x-y%z.

Hate the availability of the CF last minutes. We suppose that 80% solutions on problem D are wrong. Test by Petruchcho:

Answer is 0 right.

Yes.

Yeah

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

.

Hack test for D?

Input: AAAA BBAAAA 1 1 4 1 6

output: 0

How to solve Div-1 D Picking Strings? I've no clue how to approach this...

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)

Thanks. I did realize A->BB, B->AB and AAA->'', but did not know how to proceed after that. Is it just some case by case analysis like A can generate even Bs and B can generate odd Bs?

Bob isn't smart. Don't be like Bob.

I hate problem D. Stupid casework.

Can you explain the solution?

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.

firstly you can convert B to C and viceversa. Now (|B|+|C|)%2 is invaraint and also it cannot decrease.If |B|+|C| is same in both,then longest suffix consisting only of A in both should be same length.

If |B|+|C| is not same.then two cases.

1.if more A's in first string suffix then it is possible.

2.If same A's then there should be non B or C in 1st string for it to be possible

difference of length of longest suffix should be divisible by 3.

Yeah sorry.But only when |B|+|C| is same.

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.

CF would be better off without pretests if they're just random. I can write random tests myself, thankyouverymuch.

Me solving D

Still turned out to be wrong though

It completely ruined my contest :/

Yeah, this sentiment should be common.

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.

`but leave the tricky one for systest and or hacks.`

What for? I hate hacks because it depends on your room. For example, some rooms doesn't have any wrong solutions of the problem B, but in some another rooms there are teams who have made 4-6 hacks on it. It's like extra problem for them. I also think that making weak pretests are very bad idea for div1+div2 contests because people from div2 often submit naive solutions and it will make a lot of hacks and disbalance in scorboard.

`If you have twenty minutes left and are nowhere near finishing E or F, a reasonable strategy is to revisit problem D`

Another problems also have weak pretests. I saw how a lot of people passed pretest of problem F and it was very quickly. So I thought it's real to solve it faster than 15 minutes. But it was not true because these solutions were wrong. I tried to solve it and my solution of problem D was hacked 30 seconds before the end of contest.

I think hacks are the best way for tasks when autor's test can't cover all cases for all solutions(for example tasks with hash), but hacks should not be in every problem.

`on AIM Tech Round 4, where I got WA on systests`

Unfortunately, a lot of rounds on codeforces have weak pretests and a lot of hacks recently. But I think it's not a reason to make weak pretests again and again.

Anyway, I think problems were intresting and with good pretests this round would be very good. Thank you for the round and I hope next your round will have less hacks.

Hi majk, I completely understand that. I did not mean offence to you. I made that comment out of frustration. Thank you for hosting a contest :)

No offense taken. I'm glad for the discussion!

Wish you luck in next contests!

It's especially convenient to click on some participant having 6 successful hacks to see which problems he hacked and look at an infinitely loading page with their list. Codeforces hacking system is 20th century artifact. To be honest, I'd send more money to codeforces crowdfunding campaign being guaranteed that hacking system will be rewritten using some modern technologies.

On the subject: making so much random in the last solvable (ha-ha) task is definitely the best way to ruin the contest. You are saying people can stress test their solutions with a bruteforce — OK, so they should agree that the contest is imbalanced as hell as don't try to solve the last two tasks, which were supposed to arrange participants at the top?

With your first paragraph you're barking up the wrong tree here. To be honest, I've not seen any complaints about the Flash interface. Note that I'm not implying that they don't exist nor am I saying that it is ideal. I'm positive that it's not productive to complain about it on a random post three layers deep in discussion of a random round that intentionally used both of the ways of gaining points to decide the ranking. I have not noticed you saying the above in a more appropriate discussion. Perhaps you would gain more support over there and things could actually happen. I know that I would join the bid.

Regarding your second paragraph — I already know that some of the tasks were more difficult that they should have been (even though having a task with 3 or fewer correct submissions is not

thatuncommon) and I will do my best to avoid that situation next time.No, I am saying I hoped they would adjust their strategy to the circumstances and assess how to act to maximise their score. If on task E you got nowhere 20 minutes prior to the end of contest, it may be a good idea to do something else. Perhaps hack other people.

Answered on PM. On Flash — it's been told many times, nothing happened and nothing is going to.

About the strategy — I've done exactly what you are saying. But it turned out I'm so stupid that couldn't fix my solution till the end of the contest even having the bruteforce and 20 minutes. I've spent another half an hour after the contest to make it work.

The main problem with D is that most cases are not difficult to spot. It seems like the solution is: reduce it to BC-s followed by A-s, the number of B/C-s monotonically increases by 2-s in operation 1, the number of A-s monotonically decreases by 3-s in operation 4, then check how these operations can affect the other number. This translates to a lot of conditions, but the rules they check can be described very clearly, it doesn't look like case bashing at all if you think and then code, as I did.

Then there's the special case I missed: a string containing the right number of A-s at the end and no B/C-s, changed to something containing B/C-s.

Note that I started with D and solved it fairly quickly; failing the first problem I tried cost me quite a lot in score. That E/F were practically unsolvable and I didn't expect there would be many hacks (see above: I didn't see D as casework) didn't help.

I had a formal proof shortly after the contest started. The problem is you can miss something no matter how many times you go through the same thought process because, well, it's the same thought process. I had something of a bruteforce (bruter force,

O(N^{2})). Writing a test generator, fully bruteforce solution, stresstesting, finding this bug by picking random cases and fixing it takes a lot of time, probably more than 20 minutes. I sure didn't manage it that fast.Some problems have a small element of randomness. Some problems are nasty and have a huge element of randomness, either because you need to think weird to find a solution or because there's something that's very easy to miss. Some problems are geometry. There isn't always a way to do better other than farming luck in advance...

Anyway, the choice of pretests for F is much worse. If a bogo-algorithm works (bogosort: randomly permute while not sorted) on the first 95 tests, then you should make test 96 one of the pretests or use no pretests. This way, you don't have people making

blindsubmissions.If you can conceal your failure for years, that's pretty damn successful. That's not comparable to systests, but to someone running stresstests for fun and noticing an obscure bug nobody thought about a week after a contest.

Or you can be sufficiently powerful, in which case you get a taxpayer-funded bailout. But I digress.

I find my real world experience isn't nearly as harsh as people say. Not in the sense that failure is terminal. "Your submission to a vendor test didn't do well? Here are some statistics, compared to your previous submissions; we're accepting submissions again in a month." "A wild bug has appeared! We should fix it ASAP and get back to what we were doing." The various catches in (not only programming) competitions are unique in that regard. Competitions are harsh compared to ["real world" activity here] and so few people do them precisely because of that harshness.

Lol, what a moron I am. In F "while(1) try random permutation" almost works. If I'm not mistaken except for cases where one tree has high degree vertex only. So I fixed case when first tree has it. But didn't notice I need to consider case when second one has it xD.

EDIT: Ok, there is third case when two trees have high degree vertices xD. It seems it is pretty hard. So I was not close, no regret.

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

???

"WA/TLE on test 96"

Can anyone please help me understanding where this solution for problem div2 D — Perfect Security exceeds Time Limit?

I have implemented trie operations add, remove recursively, inserting indices (so as to remove issue of duplicate values, as java don't have multiset) in trie nodes, and finding index of min value in iterative manner. Complexity of this solution according to me is O(N*logN).

The only reason of TLE i can guess this time is that i used Java. (Have sometimes faced TL issue in past too :( while using Java).

Can anyone please help in pointing out ??

Thanks a lot..

Solutions are not visible at the moment.

Here's the solution

Also, another implementation with O(Nlog^2N) Complexity (ordered set) here

Edit: Solutions visible now

You do not actually need the set in a trie node to store the indices, just storing the count is enough. That should speed it up a bit.

Apart from that I don't see anything else to be improved... of course as you said it may be because of Java itself.

I guess i should leave codeforces until i learn cpp, because today i spent over an hour to code this solution, only to get 2 TLEs, Let alone rating loss (Only gained yesterday).

Anyways, Thanks a lot.

DIV 2C was Lazy Propagation, right?

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.

cjtoribio, Can you please explain your solution?

WHen you have a set of numbers and you only want to do two operations subtract to ALL, add one element. There is a technique i don't if it has a name but you just use an auxiliary number X and it will be your "floor". When you want to subtract A to all elements just add A to your floor. when you want to add an element B to the set add A+B since B is the value above the floor. For example you have set

{}, X = 0

you add 3 to the set (3 + 0)

{ 3 }, X = 0

then you subtract 1 to all the numbers

{ 3 }, X = 1

then you add number 4 (4 + X = 5)

{ 3, 5 }, X = 1

then remove 2 to all

{ 3, 5 }, X = 3 (this array is virtually {0, 2}, which can be seen as A[i]-X)

so if you want to remove all the numebers that are 0 or less just remove all numbers below the floor. all the remaining numbers are above the floor and you managed to subtract correctly from them. The ones that were removed you only subtract partially since they came under the floor.

cjtoribio, Thanks for taking time in explaining me...

P.S: Your solution is beautifully coded. :)

Update1: Is there benefit of using priority queue over multiset?Honestly multiset does the job quite nicely, but c++ priority_queue is slightly faster, as it uses Fibonaccy Heap, which i have seen is better in practice, and also the code is simpler with pqueue. But i would say use whichever you feel confortable with.

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 dayj. 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]--, whicheis 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

iis less than temp[j]. Then, we can just do add[i] += a[i], where a[i] is the amount of snow built on dayibecause 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

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.

Why i can't open another's solution?

Any clue on what was the 4th pretest in div2/C ?

Congrats majk for arranging one of the "Anti-tourist" (maybe) contests after so many days!!!

anti tourist ? ?

he is 30th

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.

I'm feeling kind of bad right now...

2 WAs in C due to typing the wrong variables, and cannot submit D (which I believe will pass the system test) in time because of the same type of mistakes...

Like today is not my day...

When I submit for problem B, I clicked the submit button twice, and there are 2 successful submissions.(36156723, 36156724) Because of the resubmission penalty, I got -50 penalty. I thought that there could be no submissions with exactly same code. Can I get my 50 points back? Please fix it.

50 points are returned.

Problem D (Div 2):"Alice is smart. Be like Alice.""Alice is smart. Really, be like Alice.""Bob is not smart. Don't be like Bob.""Did we mention that Bob isn't smart?""Since he is not so smart, he asks for your help."And while reading the problem, I am like "Okay, I got it. Please stop." (!-_-)

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

I smashed my glasses in a rage after not being able to pass the samples of E after working on it for an hour(possible due to some small issues in my solution)

Codeforces didn't cost me an arm but it cost me my glasses(although it was 100% my fault).

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.

He didn't smash your glasses， so don't judge him arbitrarily.

Did somebody under the nickname of "2018 find girlfriend" just tell me to SHUT UP AND EAT MY SHIT? This ain't no Minecraft server, cool boy, you can show your creativity without the use of swaggy words like those.

He didn't smash your glasses， so don't judge him arbitrarily.

Boy, that was creative.

next time buy a pair of plastic glasses like mine

i got plastic glasses thinking they were harder to break but it didn't help, instead of the glass breaking the frame broke. LOL

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 failureIs intended solution for F is random? I hope no...

No. We have an deterministic solution, but intended to let

O(N^{2}) pass, as it was difficult enough. None of our random solutions succeeded, but some were able to pass quite a few tests.Was there some counterexample in pretest for random solutions for F? I think lots of pretest-passed solutions are quite straightforward random solutions.

A tree with one node whose degree is

n- 2 and a chain. The expected step isO(n^{2}).And this problem can be solved combined with several random solutions.

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

I meant "Does intended solution use randomized algorithm?". Forgive my hastiness and English :P

Easier way to do A beside DP + Prime Sieve + Segment Tree? Nearly 100 lines of codes and 30 minutes to code this one.

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 ofN. Iterate fromN-f(N) + 1 toNand for each composite numberx, find the smallestx-f(x) + 1How to solve E? I think, diagonalization is the key, because it is binomial coefficients, and power of diagonalization is easy to calculate. But multiplicating matrix on vector is done in O(N^2), how to optimize it?

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

For div2D — Perfect Security

Is the solution through binary trie?. Where you store bits of

Pin reverse order and for each element ofAselect the one with minimum XOR in .Couldn't implement it in time.

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.

I use pointers a lot of times, but you might also use a global vector and store the index of the child or -1 if no child in that letter.

There was a greedy solution for this problem.

See, we wanna find lexicographically smallest message, ryt.

Formally, you should permute P in such a way that A1^P1 is smallest, A2^P2 is smallest while keeping A1^P1 at its minimum.

You can prove by induction that the Pi should be selected in such a way that Ai^Pi is minimum. Now, we need a DS which support following operations.

insert(x) — to insert a value. delete(x) — to remove this value. min(x) — find a value present such that x^val is minimum.

Now, we will first insert all Pi into this DS, and for every Ai for i from 0 to N-1, ans[i] = min(x), remove ans[i] from this DS.

Also, forgot to mention: This DS is famously known as Trie ;)

It's correct solution, but it's not greedy. You just wrote definition of lexicographically smallest message.

Why not greedy??

while moving from start to end, We greedily choose an element which minimize xor for current position, update answer for current position and remove it from set.

Correct me if I'm wrong.

It is greedy indeed.

Yes, I just wrote the definition of lexicographically smallest message

in a manner that it directly points to optimal strategy and correct solution of problem.:)Wonder how many people copied their Trie from 706D - Vasiliy's Multiset for the D1 C in this contest :)

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.

Yeah you can do it in Nlog^2N with only a multiset with really short code. My AC solution is here: http://codeforces.com/contest/947/submission/36161526

Wow, so I'm not the only one. Feeling a bit confident now, as well as a little bit regretful — if only I didn't make some silly mistakes I could submit mine.

Thanks! :D

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

Tourist's solution fails D. o_o

.

Wait for his next contest dude.

But he losing position 1 in ratings is kind of record..

RIP ppppppppppppppp, you trolled yourself.

Did he get banned? Have never seen that before, CF is usually accommodating of trolls :)

Only got comments deleted. (I didn't pay attention to the exact number of p-s.)

15 I guess

AFAIK, when account gets banned its all comments gets deleted automatically.

D WA99 <3

Try this one:

Answer is yes.

Am I the only one sick of pretests and hacks? They just make the standings unbalanced. I really admire CSA and Atcoder for dropping them.

What's the point of having different websites if they're going to have similar contest format?

They have different problem styles.

In retrospect, I think the hack system needs a revamp. But I don't mind the pretest system.

you are not the only one..

Pretests are good, hacks are not good.

The hacking system is broken beyond belief. It is supposed to be meant for some user to go through and find some obscure bug in some other fellow's code, but it doesn't give nearly enough points (only 100!??!?!). So in most rounds, nobody ever hacks, because the time is better spent elsewhere.

Then the rounds that actually have hacks are just a load of +4, +8, +11 everywhere because the pretests were insanely weak and someone didn't set the

`INF`

high enough or something. Then it's just luck of the people in your room, not skill-based at all.Hacks inflate the score. About pretests, some casework problems for example would be fitter more for a math contest than for a competitive programming one, but in a math contest you would get at least 6/7 points if you miss a case, here the whole problem...

I don't see the point in them, for what? To add unpredictability? You can just close the standings 30 minutes until the end for example. Compared to other subjects you have to code your solution here and nobody even care if your solution is correct but the code is buggy, isn't it a disadvantage already?

Judge queue would be insanely long without pretests

It's not a big deal, we can just put the basic fail cases in the beginning, do you often see submissions with WA99 for example?

The biggest reason why I like pretests is because it teaches me to consider every case without being told, "oh, it passed everything". Obviously you would have to consider every case anyway with a direct accepted verdict, but the stakes are higher with pretests, which is a good thing for me.

It depends what you consider to be programming. One of the things I admire the most about full feedback programming is that simple mistakes usually don't cost you much.

Please don't tell me you believe that someone who doesn't understand the problem at all deserves the same amount of points as someone who used int instead of long long or made an array of 100000 instead of 200000.

P.S. There are some contests called Trudeau Logic Evaluation on DMOJ that you will enjoy. There are many math, geometry and implementation problems for you to do and only one pretest, which is the sample. Have fun!

Trudeau Logic Evaluation is not as evil as COCI with systest, don't be disingenuous

>Only relative error.

>needs unsigned long long >MLE on systests

>Get TLE on systests if you use cin instead of scanf

>200000 instead of 200001

>Mod 10^9+9 instead of 10^9+7, pretests don't require you to mod

>Bounds changed from N=300000 to N=5000 after the contest

and best of all.....

>Making test data after the contest and forcing everyone to wait for 2 days before systests.

At least we have pretests :). COCI has sample as pretests.

Trudeau Logic? What is it about, straight white men get -1000 points privilege penalty? If you defeat other contestants, they win?

hmm

Generally, I agree with you, but the main reason why I don't like hacks is that it gives a particular advantage for people who were hacked: they have an opportunity to improve their solution, pass system tests and earn at least some points for the problem. Meanwhile, there can be others with exactly same solution who were not so lucky to be hacked, their solution will fail not giving them any points at all.

Since a long time, I have the opinion that the pretest system is un necessarily extremely harsh at times.

There are situations where I have declared wrong array size, and lost as much as 1600 + points in multiple contests for it.

Sometimes, this is not good.

Somehow I managed to AC only problem B div2 today

Defeat Accepted.

Ok

hmm, for DIV2 difficult level D < C < B !!!

Success rate on F: 0 out of 26, mostly failed on test 96.

Ebin :DDD

402nd place... Brutal...

In Div1D, why are there so many tests that only consist of As?

36162982

I could not solve B and it cost me my first ever (maybe also last) chance to become CM.

Dude, see my graph. You will be like me lmao xD

I lost my cool in the end. It's fucking depressing.

Did you throw your mouse or something?

I use my laptop and it has no mouse. But maybe I would have. I have a test today (it is 2 am here almost and my exam is at 11 am) and i sacrificed everything for today. but it just didn't happen. I will be 10 short in the end.

You might need to slightly reevaluate your priorities. We are in surprisingly similar situations (I solved B in pretests, and if it passed sys tests, I would have become CM, but it didn't and now I am almost exactly the same rating as you, and I have an exam on Monday, so while it isn't Friday, it's similar), but after my performance on this contest, my first thought wasn't disappointment, it was just "My consistency with solving Div2C/D during contest has been increasing a lot; I'll become CM on the next contest".

Perhaps you have something going on in your life that you can't compete on CF anymore, but if that's the case, the fact that you are not CM is almost completely irrelevant to anything. If you don't have any such thing, then compete again. If you're good enough to get within 10 points of CM, you're surely good enough to do well on a contest again.

But I would seriously rethink your motivations for doing competitive programming if you are making noticeable sacrifices in other areas of your life. Ask yourself if your end goal for competitive programming will really be more helpful than, say, focusing on your grades, and try to be completely honest with yourself. You may find that doing competitive programming

isworth sacrificing grades, but you also might find that the opposite is true.Just some friendly advice from someone in a similar situation.

Thanks for your kind and honest opinion. I often say these to other people. But reality is a little different. I do enjoy competitive programming but i know that there will be a time soon in the future when i have to quit and focus on my livelihood. But I wanted to become CM as soon as possible for a different reason (not related to programming). The fact is sometimes you can change a system when you go a higher position. I want to do something like that for my situation.

how i get pretests path then got TLE on test 5 which was in pretests there are some people who get time limit on test 5 then got it accepted it was not fair sir

Is it just me or are others also getting a penalty for getting WA on sample tc? I'm pretty sure this is not supposed to happen.

I have lost 100 points on my C due to WA on pretest 2 which was sample 2. Can someone please look into this as this is affecting ratings of everyone.

Observation: WA on pretest 1 doesn't add a penalty.

Only WA 1 does not give you penalty. No matter, how many there are pretests.

This is something new!!

Didn't see this was already answered. :)

Why did they keep it for pretest 1 only? Does not make sense to me. Shouldn't it work for all samples because that was their original intention.

I guess the reasoning behind keeping it for pretest 1 is that it automatically takes care of compilation errors and doesn't penalize one for them. Also people who use file input/output locally get a run-time error on pretest 1 itself and are not penalized

Additionally If you have wrong Input/Output format, you fail to pretest 1.

Why does my div2 C 36170685 code fail on test 9?

Today something will happen that has never happened I believe in the history of codeforces.

I am just waiting for the next round now. :)

Everyone has his/her bad days. I share the same with him. But a man like him, I know will conquer the next one. :)

Yes, I know that and this is the reason why I wrote that I am waiting for the next round now.

Tourist will be at the top again soon. :)

FTFY

He would probably slip down from #1 (after a long time).

It actually has happened before. But honestly speaking we should stop this sensationalising tendency of ours.

I have just noticed queryquerynk's submissions. He submitted D just 2 mins after his B, and passed at the first time. His D is not easy to code so fast like that, and also had different coding style from B. Seem like he did this round with a friend? Was that a kind of cheating?

Problem D is quite similar to Vasily's multiset in cf. you just need to change some of the conditions and you are ready to go.

why got WA on div2 A... Logic seems ok to me...if there is adjacent S to W I printed NO http://codeforces.com/contest/948/submission/36177886

Only problem seems i am checking an empty string...but it doesn't have 'SW' match any way

You are checking a[i + 1][j], but i + 1 can be > n. Another example is a[i — 1][j], that can be an empty string.

yes an empty string.... not =='S'...doesn't empty string means ..we get 0....anything is other than 'S'..shouldn't print no..

You are trying to get the part of the array, that havent been initalized. It can be anything, like 'a', 'Z', '\0'. It is not guaranteed that it will be 0. In the normal situation, it would result RE, but sometimes STL work weird :D

well..i bet it's either my f''ing luck...or codeforces is initializing them with 'S' cause i don't think global variable gets initiazied with 'S'.. what do u think??

The memory inside strings isn't global.

can u please explain this majk...... & MikeMirzayanov ?

I would like to report a very strange behavior that I faced today. My solution 36155783 for 948A - Protect Sheep passed pretests and had verdict "Wrong answer on test 13" in final system tests. Later, I was surprised to find that the wrong answer has been caused because of absence of boundary checks, link to my AC code 36177781. My question is global space is supposed to be initialized with 0, and I manually filled the first row with "0"s. Then how is it possible that a 'S' is there in the out-of-boundary space to cause the wrong answer or am I mistaking something or is it a compiler bug ? Thanks in advance.

Row 0 is a empty string and column c+1 is also empty

Yes, but how can there be a possible 'SW' match? There must not be any 'S' present over there in the out of boundary space, since global space is initialized with 0 ??

"global space is initialized with 0".I don't think it is necessarily true for STL.

same problem ..vai

I would politely like to mention majk and MikeMirzayanov here. I would be really grateful if you kindly come forward to explain this behavior to me. Thanks in advance.

It's simple UB.

You read string

sand concat with '0'. So length ofs[i] isC+ 1. But you trying to access item s[C + 1] which is out of range. This is certain UB.Well, definitely it is. But I think you missed the other fact that I mentioned. In global space, everything is supposed to be initialized with 0. In fact, I have used this fact to solve many problems till today. So, my question is how may there arise an occurrence of existence of an 'S' in the out of bound space then ?

In global space everything is 0 — correct. So s[0] is empty string. So when you access s[0][i] you've got UB again.

UB means that there really no way to predict behavior. If you've got this you potentionaly can get change other variable in other space, you can get elephant in your room (Can't remember who said this). I once get exception in other cpp file just cause UB.

If you want determined behaviour use

at() function. It's supposed to throwout_of_rangeexception.use 2D array of char instead of using 1D array of string

Really enjoyed the problems today. :)

I am waiting for the new song by Petr, "The Fall of Tourist"

for the first time since i join CF.

our lord and our savior Tourist get rekt

tourist is just went for

tourism, He will back soon :)I wait for

The Return of Tourist401st place? Really? When I was 403rd it wasn't so hard:D

Can anyone please tell me why my soln. gives wa on pt 20

http://codeforces.com/contest/948/submission/36157645

When you check adjacent tiles, you are sometimes accessing out of bounds array elements. This is causing undefined behavior.

That's a pity. Hope tourist will come back again! :)

I always believe that old rating formula was much better than new rating formula. Before this round everyone agree that he is the best in CF — but he falls to the 4th place just because he fails a single round? In one round everything can happen. It puts too much weight on the newest round.

I like the volatile formula. Imagine being gone for two months, then doing well on a contest, only to find you gained 15 rating...

Nobody really assigns that much weight to ratings anyway. Everyone still agrees tourist is the best in cf.

When I noticed tourist is not the leader!!

Hi, I got "WA 8" on div.2 D.

Here is my submission.

Who can help me find the bug?

OMG, I know why!

When using the multiset, the "erase" function does not act like the set.

Example:

multiset b;

b := {3,3,3,5,6,6,7} // just a example, do not mind the grammar..

b.erase(3);

And then : b := {5,6,6,7}

erase a number in the multiset will actually erase all of them.

It's my first time to use multiset. Maybe I still have some problems. But finally I learned something useful.

A competitor in Grade 8(djqtxdy) became Grandmaster after beating tourist in last night's round!

congrats!!!!!!!!!!!

It's amazing to see the fall of tourist.

hope for him.

948A — Protect Sheep

The code that i submitted during contest got WA on case 49.But the same code got AC when i submitted it after contest.

AC http://codeforces.com/contest/948/submission/36177413 WA http://codeforces.com/contest/948/submission/36157981

Maybe because you defined the array "a" in the main function.

Arrays defined in functions may not be initialized.

Try memset(a,0,sizeof a); Or you can define arrays out of main function (they'll be initialized by 0).

But now the same code is getting AC. Why?

When j = 1 you compare 'S' and not initialized value. Not initialized value is usualy a random value. So the result of this compare is random too. When you are lucky your random solution gets AC :)

Problem D was beautiful, respect to majk for it

it feels so good

No one cares :-"

Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710

Update: I seem to have fixed it by removing "remove node" function and lowering the node count while traversing the trie. Still not sure why the original function didn't work, though.

why my code is giving WA.

http://codeforces.com/contest/948/submission/36241274

Ya Got Accepted no need of help

Only tourist can lose 290 points and still have 300+ points above Legendary Grandmaster line.