By SirShokoladina, history, 4 years ago,

• +62

 » 4 years ago, # |   0 I asked someone to explain my div1B solution to me in this commentAnd you actually did that, thanks :D.
 » 4 years ago, # |   +6 SirShokoladina please fix div2E. There is parsing error.
 » 4 years ago, # |   +17 A lot of things to learn...
 » 4 years ago, # |   +3 C shows up as "unable to parse markup" for me.
•  » » 4 years ago, # ^ |   +12 thanks for noticing! it should work now
 » 4 years ago, # |   +5 Can you please provide code to the solutions, especially Div 2D/1B... really hard to understand the solution for me. Thanks a lotAlso, Div 2E/1C problem is missing it's solution
•  » » 4 years ago, # ^ | ← Rev. 3 →   +6 Here is my code for second solution for div1B:https://pastebin.com/FpfJXVH0Here is the first solution for div1C:https://pastebin.com/2KemU4bNHere is div1E, but here z = 0 means that there were people on stations and z = 1 means there were no people.https://pastebin.com/5ZdKuRkM
 » 4 years ago, # | ← Rev. 2 →   +3 I don't understand div2 C part where it says that answer can be no more than n-x. Can somebody explain me little bit better?
•  » » 4 years ago, # ^ |   0 I think there is some inaccuracy. Consider cycle and every element in it: break it on intervals between elements equal to concerned element (include first boundary, exclude second). When element is single there is one such interval. Obviously that on every interval there is exists at least one bad replacement. So in every cycle at least k bad replacements, where k is max number equal elements in cycle. So if there is x equal elements in array then in every partition on cycles there is at least x bad replacements.
•  » » » 4 years ago, # ^ |   0 how is it obvious that there is one bad replacement on each interval, why cant all elements be good replacements for some particular interval of some cycle ?
•  » » » » 4 years ago, # ^ |   0 Because we start and end on same value. Try to move ahead with this thought.
•  » » » » » 4 years ago, # ^ |   0 Okay, that's pretty clear now, thanks !!
 » 4 years ago, # |   +41 Great Contest! With mind blowing problems. SirShokoladina Sir, you should conduct contests more often.
 » 4 years ago, # |   0 LOL I did some kind of precalc on div1B. 40296044. My solution has complexity . But I can't implement it without map which contains vectors so it is very slow. Then i noticed that it can be precalculated and instead of 43 * log with bad constant it gives clear 43.
 » 4 years ago, # |   0 I think for the second solution to C, you mean to say that X and Y are the minimal possible values satisfying that condition (but the solution works).
•  » » 4 years ago, # ^ |   0 Yes, fixed it.
 » 4 years ago, # |   +2 Overall, I thought the logistics of the contest could have been managed better. Some of the problem statements could have been worded better, there were a lot of clarification announcements, etc.That being said, I thought the problem quality was good, especially Div 1 C. If Div 1 BC were shifted down 1 problem (can't speak towards D or E), and another Div 1 B made, I think the problem scaling would have been perfect.
 » 4 years ago, # | ← Rev. 2 →   +15 Can't understand the second solution for Div1.B. The solution says:"In such way every satisfying this criteria parallelepiped (not considering the orientation) with three different side lengths was counted 6 times."Let's consider the large parallelepiped to be 4x6x10, the small parallelepiped 2x3x5 will only be counted once. Why the solution says that it is counted 6 times?(Actually, can't understand the first solution either... What does "mask" mean in the solution?)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 we count it 6 times — as 2x3x5, as 2x5x3, as 3x2x5, as 3x5x2, as 5x2x3 and as 5x3x2mask of length 3 in a subset of set {1, 2, 3} written as a 3-digit binary number. so 0 = 000 = {}, 1 = 001 = {1}, 2 = 010 = {2}, 3 = 011 = {1, 2}, 4 = 100 = {3}, 5 = 101 = {1, 3}, 6 = 110 = {2, 3}, 7 = 111 = {1, 2, 3},
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 But the direction of the large parallelepiped is fixed, and 3 is not a divisor of 4, so why is 3x2x5 counted?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Because we use the IEP on rotations (permutations), so both 2x3x5 and 2x5x3 are rotated in all directions and if at least one orientation satisfies then it is counted once, otherwise it is not counted.
 » 4 years ago, # |   0 so my understanding of div2D was correct but problem statement and number of submissions prevented me,huh,sad
 » 4 years ago, # |   0 can anyone help fix my mistake for div2 B?Submission Link
•  » » 4 years ago, # ^ |   0 x > curh and y <= curh it will not update curh, in fact, curh = y.
•  » » » 4 years ago, # ^ |   0 got it, thank you
»
4 years ago, # |
-21

# ?detaR tI sI

 » 4 years ago, # |   +21 Why did my code of div1C which used "exit(0);" get "Idleness Limit Exceeded" in pretest 12?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +94 you noob
•  » » » 4 years ago, # ^ |   -8 kappa
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Nice doubt, don't forget to tell once you get the reason.
•  » » 4 years ago, # ^ |   +8 maybe you use "exit(0)" before you actually guess the correct numbers?
•  » » 4 years ago, # ^ |   +16 Oh I found a precision error in my code. But when I changed "exit" into "return" it got accepted.
•  » » » 4 years ago, # ^ |   0 can you show me your code?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 exit：http://codeforces.com/contest/1007/submission/40288030return：http://codeforces.com/contest/1007/submission/40303376
•  » » » » » 4 years ago, # ^ |   0 seems like the codes are really equivalent... I don't know, maybe you have ub.
 » 4 years ago, # |   0 Can Someone Please tell me a more intuitive way to understand the solution of div2 C (div1 A) or different easier approach if possible???
•  » » 4 years ago, # ^ |   +1 The problem can be done by using two pointers. Lets sort the given array and initialize count and both pointer to 0. say pointers be i and j. starting from index 0, take next biggest element(by changing j) and when you find that, increase i, j and count. Here we are calculating the possible number of pairs in which smaller can be replaced by bigger number. Here is snipped for what I did: sort(a,a+n); ll cnt = 0; ll p1=0,p2=0; while(p1
•  » » » 4 years ago, # ^ |   0 got your point, Thanks for explaining. :)
 » 4 years ago, # |   +3 Can someone please elaborate on the Div1B Second solution? (The Inclusion exclusion one) ...?!It is not very clear to me how the "ans2" part is calculated by the author's solution...If you had a different combinatorial solution please share that as well ..
•  » » 4 years ago, # ^ |   +8 ans2 supposes that the first two lengths of the parallelepiped coincide. That means that this length should divide two chosen dimensions of the big parallelepiped. thus we use g[x[0] | x[1]]
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Look at my other comment lower, maybe it will help.
•  » » » 4 years ago, # ^ |   0 thankyou , the whole approach is still exotic to me as I have never seen something like this before, but get your solution..
 » 4 years ago, # |   0 It seems that SirShokoladina forgot to link the editorial to the problems in Div2 (contest 1008). In any of the five problems we can't see the link of editorial.
•  » » 4 years ago, # ^ |   0 I don't know how to link them. I guess Codeforces this automatically.
•  » » » 4 years ago, # ^ |   0 I'm sorry... I don't know that before.
•  » » » 4 years ago, # ^ |   0 You can do that by clicking clip image at the top of the blog
 » 4 years ago, # | ← Rev. 3 →   +14 Can anyone explain div2d in understandable way?
•  » » 4 years ago, # ^ |   +5 I can elaborate on the second solution. First, google what inclusion-exclusion principle is. I'll explain its meaning. Assume you have a bunch of sets and want to know the size of their union. If for every set of this sets (for example "1st 2nd and 4th set" or "3rd and 5th set") you know the size of their intersection then you can count the size of their union.We have six orientations. Each of them gives us a set of parallelepipeds that we can pave the big one with. One of such sets is "1st side divides the 2nd side of the big, 2nd side divides the 1st side of the big and 3rd side divides the 3rd" side of the big", let's mark it 213. Now how can we find the size of intersection of several such sets? If we had two permutations 132 and 231 then a parallelepiped is inside the intersection of their sets if it satisfies both orientations. So its 1st side must divide both 1st and 2nd sides of the big, 2nd divides the 3rd side and 3rd divides also both 1st and 2nd. Then there are #d(gcd(A, B)) * #d(C) * #d(gcd(A, B)) such parallelepipeds (where #d is number of divisors). So we know the size of every intersection, thus we know the size of the union, which is the number of parallelepipeds that we can orientate somehow so it can pave the big. But now 2x3x5 and 3x2x5 are both counted. That's why we need to count something more, read the tutorial and I will continue if you don't understand.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 I understand to your part. Can you elaborate more? I mean, I know the inc-exc principle (union of a,b,c is a+b+c-ab-bc-ca+abc etc.) but I dont understand the editorial having read it 5 times already xDMaybe its just simple language but yours seem much more clear. Cant understand a single word from both solutions :P im bad at math lol Also, what do u mean about 2x3x5 and 3x2x5 being counted multiple times sir
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 So for one query we perform following algorithm: use exc-inc principle for all 6 permutations (1,2,3) and count intersections of each subset of sets so we can obtain the union of this permutations which is our answear am i right? Second question is what does exactly p(m) from the end of the editorial mean, i dont get it ;(
•  » » » » 4 years ago, # ^ |   +4 You were right in the beginning, but that is not exactly our answer. This is the answer, but when 1x2x3 is counted 6 times (as 1x2x3, 1x3x2, 2x1x3, 2x3x1, 3x1x2 and 3x2x1), 1x1x2 is counted three times (1x1x2, 1x2x1 and 2x1x1) and 1x1x1 is counted once.So the second number we count will be the same, but considering only parallelepipeds XxXxY, so two first sides coincide. Assume we fixed a set of sets and found which sides each side of the small parallelepiped must divide. In my example it was (A, B), (C), (A, B). Now as we know that first two sides are equal, we must unite the first two sets, so it will become: (A, B, C), (A, B, C), (A, B). So the number of such parallelepipeds will be #(gcd(A, B, C)) * #(gcd(A, B, C)) * #(gcd(A, B)).In the second number 1x2x3 was not counted (as 1 != 2), 1x1x2 was counted once (1x2x1 and 2x1x1 are not counted as 1 != 2) and 1x1x1 was counted also once.We multiply the second number by three and add it to the first. Now 1x2x3 is counted 6 times, 1x1x2 is counted 6 times and 1x1x1 is counted 4 times. Now we add #d(gcd(A, B, C)) * 2 and everything is counted 6 times. Then divide by 6 and get the answer.
•  » » » » » 4 years ago, # ^ |   0 So we do count the second number exactly the same as the first one but on each intersection we consider first two sides to be equal? We use inc-exc principle once again right?
•  » » » » » » 4 years ago, # ^ |   +3 Right.
•  » » » » » » » 4 years ago, # ^ |   0 And what did p(m) meant on the end od the tutorial on this task? (In time comlexity).
•  » » » » » » » » 4 years ago, # ^ |   +3 https://en.m.wikipedia.org/wiki/Partition_(number_theory) in case of m=3, p(m)=3: 1+1+1 (three unequal lengths), 2+1 (two equal lengths and one more), 3 (the equal lengths)
•  » » » » » » » » » 4 years ago, # ^ |   0 Last question.In counting second number we can assume that first and second are the same because of symmetry, right?
•  » » » » » » » » » 4 years ago, # ^ |   0 yes
•  » » » » » » » » » 4 years ago, # ^ |   +16 Thanks for help both of you guys. I appreciate it.
 » 4 years ago, # |   0 For div2C does cycle decomposition work if the permutation contains repeated elements? I mean for the proof it is assumed that there is a cycle decomposition?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Permutation can't contain equal elements
 » 4 years ago, # | ← Rev. 2 →   -8 Hi, can anyone please help me with my div2C submission, it is getting error on test case 8 #include using namespace std; int main(){ int n; cin>>n; std::vector v(n); for(int i=0; i>v[i]; sort(v.begin(),v.end()); int k=0; for(k; kv[0]) break; std::vector num(v.begin()+k,v.end()); int count=0; for (int i = 0; i < num.size(); ++i) { if(num[i]>v[i]) count++; //cout<