By majk, 3 years ago,

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

Announcement of VK Cup 2018 - Round 1

• +251

 » 3 years ago, # |   0 Wow, one more streak of rated contests? Nice!
 » 3 years ago, # |   +40 " Wish you many submissions, high hacks and successful rating."I am assuming there will be lot of hacks
 » 3 years ago, # |   0 Looking forward to the round)
 » 3 years ago, # | ← Rev. 2 →   +10 Can the test in English?
 » 3 years ago, # |   0 How do I know if I got to this stage or not?
 » 3 years ago, # |   0 How do I know if I am eligible for VK cup ?
 » 3 years ago, # |   +21 When and where were the two qualification rounds held for VK Cup Round1 ??
•  » » 3 years ago, # ^ |   +23 They were held for russian-speaking users only.
•  » » » 3 years ago, # ^ |   +17 But why orbitingflea and zhangzy can register? They're both Chinese.
•  » » » » 3 years ago, # ^ |   +15 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!):)
•  » » » » 3 years ago, # ^ |   +13 They passed qualification. I think they translated russian statements during it
 » 3 years ago, # | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +29 The rounds are identical, but there are six different problems :)
 » 3 years ago, # |   +130 The main heroes of this round will be Alice and Bob. Beware that Eve might attempt to foil their plans.
 » 3 years ago, # |   +3 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" ?
•  » » 3 years ago, # ^ |   +28 '#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.
 » 3 years ago, # | ← Rev. 3 →   -8 Div. 1 will have six "identical" problems :O
•  » » 3 years ago, # ^ |   +10 Yes, that is true. Solving all six of them is still quite a challenge.
•  » » » 3 years ago, # ^ |   +15 Cool!! Let's hope the problem statements will be identically short for both the Divisions :P
 » 3 years ago, # |   -45 (please read the 'for teams' part before downvoting!)is it rated for teams?
•  » » 3 years ago, # ^ |   +109 Yes! Are you sure you don't want some downvotes? Maybe just one?
•  » » » 3 years ago, # ^ |   +95 No thanks!i have a lot of them :(
•  » » » » 3 years ago, # ^ |   -64 Are the downvotes rated?
•  » » » » » 3 years ago, # ^ |   +2 I think you are in a good position now to see for yourself. :P
•  » » » » » » 3 years ago, # ^ |   0 Haha, yes. But I was just pulling OP’s leg — I guess kids are too bored with that joke.
 » 3 years ago, # |   +8 What a sad time for Chinese :(23:35 :(
•  » » 3 years ago, # ^ |   0 Warm condolences .. .. but i think it will be a great soiree with codeforces:)
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 This is a good time of the contest for Russia. But unfortunately not for everyone.
•  » » 3 years ago, # ^ |   0 I think the time is quite good in your timezone? It'll be 21:35 if I'm right...
 » 3 years ago, # | ← Rev. 2 →   +2 I hope this contest will make me green !UPD: I am green now :)
•  » » 3 years ago, # ^ |   +7 Thanks ! :) majk
 » 3 years ago, # |   -35 editorials ?
•  » » 3 years ago, # ^ |   +199 Perhaps it would be better to publish them after contest, not before.
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   +46 Great Deduction.
 » 3 years ago, # |   +11 Will the problems statements be in English? The registration page is showing me T&C in Russian
•  » » 3 years ago, # ^ |   +6 No worries, the problems will also be in English. We'll check the registration page, thanks for reporting.
 » 3 years ago, # | ← Rev. 2 →   0 [deleted]
 » 3 years ago, # |   +11 Will we see tourist tonight? Exciting!
 » 3 years ago, # |   +6 I hope this contest will make me green once again...!!!!
 » 3 years ago, # |   +5  "Wish you many submissions, high hacks and successful rating." I wish you successful submissions, high hacks and many rating, too. :)
 » 3 years ago, # | ← Rev. 4 →   -13 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
 » 3 years ago, # |   0 If i understand correctly, usually Div#2 prob-C is prob-A in Div#1. In this round 5 problems are common between Div#1 and Div#2, so Div#2 Prob-A will be Div#1 prob-A. Is this right ?
 » 3 years ago, # |   +12 B > C
 » 3 years ago, # |   +16 tourist is in the house!
•  » » 3 years ago, # ^ |   +3 tourist's solution for Problem D falied on main tests.
 » 3 years ago, # |   +31 CF-Predictor broke or something?
 » 3 years ago, # |   0 948BIn 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?
•  » » 3 years ago, # ^ |   +7 announces X1 = 14 Bob picks prime 5 then x2 = 15
 » 3 years ago, # |   0 it was a terrible decision to keep thinking about problem B.. I should have tried problem C :(
 » 3 years ago, # |   +18 Lol Div2B harder than Div2C/D
•  » » 3 years ago, # ^ |   0 yeee)
 » 3 years ago, # |   0 Really nice problems this round, looking forward to see the tutorial.
 » 3 years ago, # |   0 How to solve div2-B ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ |   +1 Why would you assume the the first prime divides X0?
•  » » » » 3 years ago, # ^ |   +2 I don't
•  » » » » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 I came up with exact solution after 10 mins the contest ended :(
 » 3 years ago, # |   0 Can anyone share hack for C ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +19 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.
 » 3 years ago, # |   +47 Original C, never coulda come up with such task.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I thought I didn't understand the problem at first...
•  » » 3 years ago, # ^ | ← Rev. 2 →   -20 I beg to differGotham PD — CodechefThe base idea is exactly same in the two problems
•  » » » 3 years ago, # ^ |   +33
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   -15
 » 3 years ago, # | ← Rev. 4 →   0 TIL (x-y)%z != x-y%z.
 » 3 years ago, # | ← Rev. 3 →   +16 Hate the availability of the CF last minutes. We suppose that 80% solutions on problem D are wrong. Test by Petruchcho: A ABBABBA 1 1 1 1 7 
•  » » 3 years ago, # ^ |   +2 Answer is 0 right.
•  » » » 3 years ago, # ^ |   0 Yes.
•  » » » 3 years ago, # ^ |   0 Yeah
•  » » 3 years ago, # ^ |   0 My solution failed all always in test 8 but it gave me 0 for that test. Is the judge solution OK ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 .
 » 3 years ago, # |   +5 Hack test for D?
•  » » 3 years ago, # ^ |   +10 Input: AAAA BBAAAA 1 1 4 1 6output: 0
 » 3 years ago, # |   0 How to solve Div-1 D Picking Strings? I've no clue how to approach this...
•  » » 3 years ago, # ^ |   +5 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.
•  » » 3 years ago, # ^ |   +8 B->AC->AAB->AAAC->CC->AB->AAC->AAAB->Bwhen B ~ CA->BBB->ABAAA->''before B we can make A, add 'kill' AAA, so we can make any number of Aso when we take substring we interested in count of B and count of last Aand then where some easy cases (you can look in my code, after system testing)
•  » » » 3 years ago, # ^ |   0 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?
 » 3 years ago, # |   +14 Bob isn't smart. Don't be like Bob.
 » 3 years ago, # |   +224 I hate problem D. Stupid casework.
•  » » 3 years ago, # ^ |   0 Can you explain the solution?
•  » » » 3 years ago, # ^ |   +5 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.
•  » » » 3 years ago, # ^ |   +13 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
•  » » » » 3 years ago, # ^ |   +5 difference of length of longest suffix should be divisible by 3.
•  » » » » » 3 years ago, # ^ |   +10 Yeah sorry.But only when |B|+|C| is same.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +21 CF would be better off without pretests if they're just random. I can write random tests myself, thankyouverymuch.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +126 Me solving D
•  » » » 3 years ago, # ^ |   +54 Still turned out to be wrong though
•  » » 3 years ago, # ^ |   +3 It completely ruined my contest :/
•  » » » 3 years ago, # ^ |   +18 Yeah, this sentiment should be common.
•  » » 3 years ago, # ^ |   +3 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.
•  » » » 3 years ago, # ^ |   +19 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 DAnother 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 systestsUnfortunately, 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.
•  » » » 3 years ago, # ^ |   0 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 :)
•  » » » » 3 years ago, # ^ |   +3 No offense taken. I'm glad for the discussion!Wish you luck in next contests!
•  » » » 3 years ago, # ^ | ← Rev. 4 →   +36 Everyone was, however, able to look at the scoreboard 20 minutes before end of contest and see that it is full of hacks. 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?
•  » » » » 3 years ago, # ^ |   +2 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 that uncommon) and I will do my best to avoid that situation next time. they should agree that the contest is imbalanced as hell as don't try to solve the last two tasks 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.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ |   +10 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. 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 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(N2)). 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 blind submissions. The difference is that you sometimes get a wrong answer on systest few years after submission. 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.
 » 3 years ago, # | ← Rev. 2 →   +60 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.
•  » » 3 years ago, # ^ |   +65 '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"???
•  » » » 3 years ago, # ^ |   +37 "WA/TLE on test 96"
 » 3 years ago, # |   +3 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..
•  » » 3 years ago, # ^ |   0 Solutions are not visible at the moment.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Here's the solutionAlso, another implementation with O(Nlog^2N) Complexity (ordered set) hereEdit: Solutions visible now
•  » » » » 3 years ago, # ^ |   +3 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.
•  » » » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 DIV 2C was Lazy Propagation, right?
•  » » 3 years ago, # ^ |   +1 No i solved it without segment tree.
•  » » 3 years ago, # ^ |   +8 DIV2C can be solved easily with using Binary Search.
•  » » » 3 years ago, # ^ |   0 How!!!!!!!!Please give some hints...
•  » » 3 years ago, # ^ |   +2 Lazy prop might work, but a priority queue and a variable might do the trick.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 cjtoribio, Can you please explain your solution?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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?
•  » » » » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +3 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.
•  » » 3 years ago, # ^ | ← Rev. 6 →   +6 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
•  » » 3 years ago, # ^ |   +7 Calculate prefix sums of T and binary search with each V -> O(N log N) solution.
•  » » 3 years ago, # ^ |   +3 we can do it using binary search + prefix sums , I don't think Lazy propagation helps here.
•  » » 3 years ago, # ^ |   0 I wrote something like partial sums.
•  » » 3 years ago, # ^ |   0 i use binary indexed tree + binary search ...but just binary Search is enough
•  » » 3 years ago, # ^ |   +4  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.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 codeforces.com/contest/948/submission/36171753 what's wrong in this? I hv already checked it on several test cases but still don't know why is it wrong??
 » 3 years ago, # |   0 Why i can't open another's solution?
 » 3 years ago, # |   +3 Any clue on what was the 4th pretest in div2/C ?
 » 3 years ago, # |   +72 Congrats majk for arranging one of the "Anti-tourist" (maybe) contests after so many days!!!
•  » » 3 years ago, # ^ |   0 anti tourist ? ?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 he is 30th
•  » » » » 3 years ago, # ^ |   0 ok..
•  » » 3 years ago, # ^ |   +22 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.
 » 3 years ago, # |   0 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...
 » 3 years ago, # |   +32 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.
•  » » 3 years ago, # ^ |   +79 50 points are returned.
 » 3 years ago, # |   +77 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." (!-_-)
•  » » 3 years ago, # ^ |   +19 These sentences are useless and make the whole problem long and boring.....
 » 3 years ago, # |   +17 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).
•  » » 3 years ago, # ^ |   +134 According to a few comments I've seen of yours, you really should control your temper, pal.
•  » » 3 years ago, # ^ |   +61 You need to learn to fail.
•  » » 3 years ago, # ^ |   +179 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -35 He didn't smash your glasses， so don't judge him arbitrarily.
•  » » » » 3 years ago, # ^ |   +71 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.
•  » » » 3 years ago, # ^ |   +21 He didn't smash your glasses， so don't judge him arbitrarily.
•  » » » » 3 years ago, # ^ |   +31 Boy, that was creative.
•  » » 3 years ago, # ^ |   +24 next time buy a pair of plastic glasses like mine
•  » » » 3 years ago, # ^ |   0 i got plastic glasses thinking they were harder to break but it didn't help, instead of the glass breaking the frame broke. LOL
•  » » 3 years ago, # ^ |   +3 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.
•  » » 3 years ago, # ^ |   +18 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.
•  » » 3 years ago, # ^ |   +6 I was stuck in gray for 2 years and still have my glasses.just kidding to make you forget the failure
 » 3 years ago, # |   +7 Is intended solution for F is random? I hope no...
•  » » 3 years ago, # ^ |   +22 No. We have an deterministic solution, but intended to let O(N2) pass, as it was difficult enough. None of our random solutions succeeded, but some were able to pass quite a few tests.
•  » » » 3 years ago, # ^ |   0 Was there some counterexample in pretest for random solutions for F? I think lots of pretest-passed solutions are quite straightforward random solutions.
•  » » » » 3 years ago, # ^ |   +3 A tree with one node whose degree is n - 2 and a chain. The expected step is O(n2).And this problem can be solved combined with several random solutions.
•  » » 3 years ago, # ^ |   0 Can you please tell me what do you mean when you say the intended solution was random?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I meant "Does intended solution use randomized algorithm?". Forgive my hastiness and English :P
 » 3 years ago, # |   +5 Easier way to do A beside DP + Prime Sieve + Segment Tree? Nearly 100 lines of codes and 30 minutes to code this one.
•  » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 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
 » 3 years ago, # |   0 How 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?
•  » » 3 years ago, # ^ |   +10 It's convolution (plus some multiplicative factors), so FFT is answer.
 » 3 years ago, # | ← Rev. 2 →   +3 For div2D — Perfect SecurityIs the solution through binary trie?. Where you store bits of P in reverse order and for each element of A select the one with minimum XOR in . Couldn't implement it in time.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 struct Trie { Trie() { next[0] = next[1] = nullptr; } Trie* next[2]; //Usefull info }; Trie* root = new Trie(); 
•  » » » 3 years ago, # ^ |   +1 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 ;)
•  » » » » 3 years ago, # ^ |   +5 It's correct solution, but it's not greedy. You just wrote definition of lexicographically smallest message.
•  » » » » » 3 years ago, # ^ |   +19 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.
•  » » » » » » 3 years ago, # ^ |   +1 It is greedy indeed.
•  » » » » » 3 years ago, # ^ |   0 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. :)
 » 3 years ago, # |   -40 codeforces today was like a shit :\ sorry But very slow : hope will be better in coming days ; please have democracy and do not ban me LOVE YOU <3
•  » » 3 years ago, # ^ |   -11 it is Time for change (some old servers) ;
 » 3 years ago, # |   +3 Wonder how many people copied their Trie from 706D - Vasiliy's Multiset for the D1 C in this contest :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ |   +3 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
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 3 years ago, # ^ |   0 Me :P
•  » » 3 years ago, # ^ |   0 Thanks for giving me another problem which can be solved with trie.
 » 3 years ago, # |   +11 Tourist's solution fails D. o_o
•  » » 3 years ago, # ^ | ← Rev. 2 →   -14 .
•  » » » 3 years ago, # ^ |   +2 Wait for his next contest dude.
•  » » » » 3 years ago, # ^ |   +2 But he losing position 1 in ratings is kind of record..
 » 3 years ago, # | ← Rev. 2 →   +51 RIP ppppppppppppppp, you trolled yourself.
•  » » 3 years ago, # ^ |   +5 Did he get banned? Have never seen that before, CF is usually accommodating of trolls :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Only got comments deleted. (I didn't pay attention to the exact number of p-s.)
•  » » » » 3 years ago, # ^ |   0 15 I guess
•  » » » » 3 years ago, # ^ |   +5 AFAIK, when account gets banned its all comments gets deleted automatically.
 » 3 years ago, # |   0 36157531 and 36156681 similar code
 » 3 years ago, # |   +51 D WA99 <3
•  » » 3 years ago, # ^ | ← Rev. 9 →   +18 Try this one: AAAAAA BBA 1 1 6 1 3 Answer is yes.
 » 3 years ago, # |   +76 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.
•  » » 3 years ago, # ^ |   0 What's the point of having different websites if they're going to have similar contest format?
•  » » » 3 years ago, # ^ |   +54 They have different problem styles.
•  » » » » 3 years ago, # ^ |   0 In retrospect, I think the hack system needs a revamp. But I don't mind the pretest system.
•  » » 3 years ago, # ^ |   0 you are not the only one..
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +26 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?
•  » » » » 3 years ago, # ^ |   +11 Judge queue would be insanely long without pretests
•  » » » » » 3 years ago, # ^ |   +16 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?
•  » » » » 3 years ago, # ^ |   +15 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.
•  » » » 3 years ago, # ^ |   0 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!
•  » » » » 3 years ago, # ^ |   -8 Trudeau Logic Evaluation is not as evil as COCI with systest, don't be disingenuous
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 >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 contestand best of all.....>Making test data after the contest and forcing everyone to wait for 2 days before systests.
•  » » » » » » 3 years ago, # ^ |   0 At least we have pretests :). COCI has sample as pretests.
•  » » » » 3 years ago, # ^ |   -20 Trudeau Logic? What is it about, straight white men get -1000 points privilege penalty? If you defeat other contestants, they win?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 hmm
•  » » » 3 years ago, # ^ |   +5 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 Somehow I managed to AC only problem B div2 today
 » 3 years ago, # |   0 Defeat Accepted.
•  » » 3 years ago, # ^ |   +5 Ok
 » 3 years ago, # |   +6 hmm, for DIV2 difficult level D < C < B !!!
 » 3 years ago, # |   +2 Success rate on F: 0 out of 26, mostly failed on test 96.Ebin :DDD
 » 3 years ago, # |   0 402nd place... Brutal...
 » 3 years ago, # |   0 In Div1D, why are there so many tests that only consist of As?36162982
 » 3 years ago, # |   0 I could not solve B and it cost me my first ever (maybe also last) chance to become CM.
•  » » 3 years ago, # ^ |   +9 Dude, see my graph. You will be like me lmao xD
•  » » » 3 years ago, # ^ |   0 I lost my cool in the end. It's fucking depressing.
•  » » » » 3 years ago, # ^ |   0 Did you throw your mouse or something?
•  » » » » » 3 years ago, # ^ |   +5 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.
•  » » » 3 years ago, # ^ |   +3 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.
 » 3 years ago, # |   0 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
 » 3 years ago, # |   +1 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.
•  » » 3 years ago, # ^ |   0 Only WA 1 does not give you penalty. No matter, how many there are pretests.
•  » » » 3 years ago, # ^ |   -11 This is something new!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Didn't see this was already answered. :)
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ |   0 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
•  » » » » » 3 years ago, # ^ |   +8 Additionally If you have wrong Input/Output format, you fail to pretest 1.
 » 3 years ago, # |   0 Why does my div2 C 36170685 code fail on test 9?
 » 3 years ago, # |   +7 Today something will happen that has never happened I believe in the history of codeforces.I am just waiting for the next round now. :)
•  » » 3 years ago, # ^ |   +25 Everyone has his/her bad days. I share the same with him. But a man like him, I know will conquer the next one. :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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. :)
•  » » » 3 years ago, # ^ |   0 Everyone has his/her bad contests. FTFY
•  » » » 3 years ago, # ^ |   0 i share the same with him ?? what it means here
•  » » 3 years ago, # ^ |   0 He would probably slip down from #1 (after a long time).
•  » » 3 years ago, # ^ |   +3 It actually has happened before. But honestly speaking we should stop this sensationalising tendency of ours.
 » 3 years ago, # |   -19 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?
•  » » 3 years ago, # ^ |   +19 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.
 » 3 years ago, # | ← Rev. 3 →   0 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/36177886Only problem seems i am checking an empty string...but it doesn't have 'SW' match any way
•  » » 3 years ago, # ^ | ← Rev. 2 →   +14 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 yes an empty string.... not =='S'...doesn't empty string means ..we get 0....anything is other than 'S'..shouldn't print no..
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 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??
•  » » » » » » 3 years ago, # ^ |   0 The memory inside strings isn't global.
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 what i did was at all . print D and check if there is any S adjacent to W if yes print no else print matrix but it gave wa on test 20 why ? @majk i dont think there is any boundary condition which is making my soln. wrong . any flaw in my soln > ? http://codeforces.com/contest/948/submission/36157645
•  » » 3 years ago, # ^ |   0 can u please explain this majk...... & MikeMirzayanov ?
 » 3 years ago, # |   +6 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.
•  » » 3 years ago, # ^ |   0 Row 0 is a empty string and column c+1 is also empty
•  » » » 3 years ago, # ^ |   +1 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 ??
•  » » » » 3 years ago, # ^ |   +8 "global space is initialized with 0".I don't think it is necessarily true for STL.
•  » » » » 3 years ago, # ^ |   0 same problem ..vai
•  » » 3 years ago, # ^ |   +11 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.
•  » » 3 years ago, # ^ |   0 It's simple UB.You read string s and concat with '0'. So length of s[i] is C + 1. But you trying to access item s[C + 1] which is out of range. This is certain UB.
•  » » » 3 years ago, # ^ |   0 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 ?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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 throw out_of_range exception.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 use 2D array of char instead of using 1D array of string
 » 3 years ago, # |   +22 Really enjoyed the problems today. :)
 » 3 years ago, # |   -24 I am waiting for the new song by Petr, "The Fall of Tourist"
•  » » 3 years ago, # ^ |   0 for the first time since i join CF.our lord and our savior Tourist get rekt
•  » » 3 years ago, # ^ | ← Rev. 3 →   +36 tourist is just went for tourism , He will back soon :)I wait for The Return of Tourist
 » 3 years ago, # |   0 401st place? Really? When I was 403rd it wasn't so hard:D
 » 3 years ago, # |   0 Can anyone please tell me why my soln. gives wa on pt 20http://codeforces.com/contest/948/submission/36157645
•  » » 3 years ago, # ^ |   0 When you check adjacent tiles, you are sometimes accessing out of bounds array elements. This is causing undefined behavior.
•  » » » 3 years ago, # ^ |   0 Thanks !! finally corrected it ! actually i was thinking of the same but since the pretests passed initially i didn't care .. but ...
 » 3 years ago, # |   +92
•  » » 3 years ago, # ^ |   +29 That's a pity. Hope tourist will come back again! :)
•  » » 3 years ago, # ^ |   +103 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.
•  » » » 3 years ago, # ^ |   +13 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.
 » 3 years ago, # | ← Rev. 2 →   +9 When I noticed tourist is not the leader!!
 » 3 years ago, # |   -10 Hi, I got "WA 8" on div.2 D.Here is my submission.Who can help me find the bug?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
 » 3 years ago, # |   +16 A competitor in Grade 8(djqtxdy) became Grandmaster after beating tourist in last night's round!
•  » » 3 years ago, # ^ |   +13 congrats!!!!!!!!!!!
 » 3 years ago, # |   -30 It's amazing to see the fall of tourist.
•  » » 3 years ago, # ^ |   +8 hope for him.
 » 3 years ago, # |   +53
 » 3 years ago, # |   0 948A — Protect SheepThe code that i submitted during contest got WA on case 49.But the same code got AC when i submitted it after contest.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 But now the same code is getting AC. Why?
•  » » » » 3 years ago, # ^ |   +3 if(a[i][j-1]=='S' || ... 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 :)
 » 3 years ago, # |   0 Problem D was beautiful, respect to majk for it
 » 3 years ago, # |   +3 it feels so good
•  » » 3 years ago, # ^ |   -8 No one cares :-"
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   +8 why my code is giving WA.http://codeforces.com/contest/948/submission/36241274
•  » » 3 years ago, # ^ |   +8 Ya Got Accepted no need of help
 » 3 years ago, # |   +3 Only tourist can lose 290 points and still have 300+ points above Legendary Grandmaster line.