By DBradac, history, 17 months ago, ,

Join us this Saturday on the 7th round of this year's COCI!

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

•
• +53
•

 » 17 months ago, # |   0 I just tried to register but I'm getting "You're not allowed to log in from this location." Is it not an open contest?
•  » » 17 months ago, # ^ |   +10 Change the contest from HNOI to COCI.
 » 17 months ago, # |   0 Reminder: less than 2 hours left.
•  » » 17 months ago, # ^ |   0 Now it's 1 hour.
 » 17 months ago, # |   +9 I wonder what happened to the author of the second task. Why the footnote is so sarcastically?
 » 17 months ago, # |   0 Firstly, I scared input of 50 :D
•  » » 17 months ago, # ^ |   +21 Poor input of 50.
 » 17 months ago, # |   +32 The problem statement of second task is so long it's disgraceful.
 » 17 months ago, # |   +1 How to solve B (80) problem ?
•  » » 17 months ago, # ^ |   +4 Look at divisors of 2N.
•  » » 17 months ago, # ^ |   +3 Hint: sum of l,l+1,...,r-1,r is equal to (l+r)/2.0*(r-l+1) try iterating over every possible value of (r-l+1)
•  » » 17 months ago, # ^ | ← Rev. 4 →   +7 You can solve in Easy understandable code intt n; cin >> n; intt a = 1; while (a * (a + 1) / 2 < n) { if ((n - a * (a + 1) / 2) % (a + 1) == 0) cout << (n - a * (a + 1) / 2) / (a + 1) << " " << (n - a * (a + 1) / 2) / (a + 1) + a << endl; a++; } You will understand from that :sum of 2 adj. numbers: m + (m + 1) = 2m + 1sum of 3 adj. numbers: m + (m + 1) + (m + 2) = 3m + 3sum of 4 adj. numbers: m + (m + 1) + (m + 2) + (m + 3) = 4m + 6 .. etc..
 » 17 months ago, # |   0 How to solve C? I used bitmasks for 40pts.
•  » » 17 months ago, # ^ |   +14 This might be overkill.Let's denote the amount of a-s, b-s and c-s Slavko has for some some suffix of Mirko's string as sa, sb, sc. Also denote the amount of a-s, b-s and c-s in the suffix as ma, mb, mc. Then that suffix is solvable with the given letters iff the maximum flow of the following graph is sa + sb + sc:Now we can iterate over Mirko's string and choose the lexicographically smallest character so that the remaining string is still solvable with the remaining letters.
•  » » » 17 months ago, # ^ |   0 huh, at least I'm not the only one who did that :D
•  » » 17 months ago, # ^ |   0 Task Igra: implement an O(n) function to answer "is it possible to arrange a valid string if we have (a1, b1, c1) free characters against (a2, b2, c2) already placed characters (notice that a1 + b1 + c1 = a2 + b2 + c2). To do it you can iterate over what part of a1 goes to b2, and then all the rest if fixed and can be checked with some ifs.Now you can iterate over each character of answer string and try to place a, then b, then c and check if it is correct. It is O(n2), obviously. By the way, the function is some kind of maxflow, so it can even be solved in nearly constant time, making O(n) operations total.
•  » » » 17 months ago, # ^ |   0 I tried to fill a2 with b1 and c1 by first giving all the b1 and then c1...another possibility is by giving all c1 and then b1. I generated 8 such possible ways.Is it wrong? :/
•  » » 17 months ago, # ^ | ← Rev. 3 →   0 You can just pick the letter greedily, checking if choosing such letter and you can still have a valid string afterwards.e.g. if you choose 'a' at pos i, you need to make sure no. of 'b' in Slavko[i + 1 .. n] <= (a — 1) + c, no. of 'c' in Slavko[i + 1..n] <= (a — 1) + b. you can do this O(1). where a, b, c are the number of letter that Mirko still have.So overall time complexity is O(N).
•  » » » 17 months ago, # ^ |   0 Did you get full score for that approach? Because I did the same and got only 30 points (it is possible that my code has a bug).
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +3 Yes I got full score with it. qjnUOH
•  » » » » » 17 months ago, # ^ |   0 Thank you
•  » » » » 17 months ago, # ^ |   +3 I got 30 too, my error was that I was allowing negative frequencies.
•  » » » » » 16 months ago, # ^ |   0 Exactly the same bug.
 » 17 months ago, # |   +30 How to solve 140pts?
 » 17 months ago, # | ← Rev. 2 →   +3 I wonder why the limits for third task are so small. Isn't there an O(n * alpha^2) solution? UPD: seems like my solution is wrong
•  » » 17 months ago, # ^ |   +3 I submitted an O(n^2) solution, but I think that it could be changed slightly to an O(n) one. How did you get an alpha^2 factor?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 First alpha for iterating over every character, second alpha for checking if this character can be inserted (if it doesn't make some of the remaining characters unusable)
•  » » » » 17 months ago, # ^ |   +13 Oh, I thought that by alpha you meant the inverse Ackermann function
 » 17 months ago, # |   0 how to solve F?I can solve it only for 64 points with a weird Gauss Elimination but I have no idea how to do it for max.
•  » » 17 months ago, # ^ |   +10 I didn't solve it (made pretty bad mistake), but I think this is the intended solution.The only thing left would be to find σ, which can be done using Knuth-Morris-Pratt.So this solution runs in O(M) time.
•  » » » 17 months ago, # ^ |   0 Got it. Thanks.
 » 17 months ago, # |   +3 Is it just me or COCI's are becoming harder and harder?
•  » » 17 months ago, # ^ |   0 You can look at the scores of people in past contest to compare. Write back if you find something interesting.
•  » » » 17 months ago, # ^ |   0 Oh! I see it. One contest is easy the next is difficult :P
•  » » 17 months ago, # ^ |   +1 I think this contest was harder than usual.
•  » » 17 months ago, # ^ |   0 In 5th round I got 434 points, 6th round was 350 points and now I didn't even solve three problems in this round :(
•  » » 17 months ago, # ^ |   +4 Or maybe the previous rounds this season were easier than usual? At least this is how I feel about it.
 » 17 months ago, # |   +5 What's an expected value?
•  » » 17 months ago, # ^ |   0 Sum of every possible result divided by the number of these results. If a result can be obtained in two different ways it should be counted twice. I haven't read the problem asking for expected value. I'm giving the general meaning
•  » » » 17 months ago, # ^ |   +5 Thanks
•  » » » 17 months ago, # ^ |   +18 That is correct only if all results have equal probability. The general definition of expected value is : Let's say that there are n results of something with values a[1],a[2],..a[n-1],a[n] and the probability of the ith result to appear is p[i], then: The expected value=sigma p[i]*a[i]
 » 17 months ago, # |   +5 Fourth problem (120) may fail because of recursion?
 » 17 months ago, # |   0 How long does it normally take for COCI results to be final? It's my first time competing in a round.
•  » » 17 months ago, # ^ |   +3 Like an hour. But initially the results only appear at the evaluator page, it takes a while before they appear at hsin.hr/coci
•  » » 17 months ago, # ^ |   +6 you can see them now
 » 17 months ago, # |   -8 IAmNomad was the first place in 6th round but he scored 130 in this contest. Isn't it weird?
 » 17 months ago, # | ← Rev. 3 →   0 I got a solution for problem D that got TLE on 2 last testcases. How can I improve it?First, treat the scale as a binary tree (left child = left beam, right child = right beam, weight = leaf node). There will be maximumly 3n nodes in this tree.Call dpu the smallest sum (in binary form) for a balanced subtree in vertex u. Then:We got a O(n2) solution now. How can we make this faster?Since dpu is now a string, multiply by 2 also mean add character '0' to the end of the string. So, with careful implementation using pointer, "assigning" value for all dp states will take totally O(n). What about time needed to compare the strings from two children? It's in the worst case (The tree look like an segment tree with value of all leafs equal each other). So we got a solution.My code
•  » » 17 months ago, # ^ |   0 My solution was saving the values and the exponential of two considered that the answer is one of the node * power of 2. This give a linear solution. The last two were hard so I luckily got 12th by solving first 4 problems lol.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 Sorry if this is stupid, but how to prove correctness of the DP for an internal(scale) node? I mean if we have scale with children having weights a and b(a ≤ b) we'd have to add b - a weight to the left child, but how do you know that it can be done while maintaining the current balance within that subtree? Wouldn't it be required for b - a to be divisible by 2height where height =  height of the node from the bottom?
 » 17 months ago, # |   0 My solution for D got just 54pts. I think my approach is correct — For all the weights, I found the wt such for maximum value — w[i]/pow(2,level[i]). Answer is concatenation of binary representation of wt and level of wt times '0'.also I took care of the fact that level can go upto 10^6.My CodeWhere am I wrong?
•  » » 17 months ago, # ^ |   +8 Probably handling 106 strings of length 106 is too much. It is better to represent the numbers in the form of a·2b where a is some odd integer.
•  » » » 17 months ago, # ^ |   0 I didn't made strings of length 10^6. Check my code. I got just 54 pts.
•  » » » 16 months ago, # ^ |   0 Could you post a link to your solution? Thank you in advance. :)
 » 17 months ago, # | ← Rev. 3 →   0 Am I the only one, who thought, that in the 4th problem you are only allowed to add weights to the existing weights (in other words, to the leaves of the tree)? Got only 54 points during the contest because of that and full score in the analysis mode when I decided to leave this assumption alone (and I believe, that my first assumption is way more intuitive).
•  » » 17 months ago, # ^ |   0 I assumed that and got 120. You were wrong elsewhere.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 What does your solution produce for the following test case?22 -5-2 -2According to my AC solution, the answer is 1010, and according to my failed slution, the answer is 1100
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 And one more thing: if we assume, that we can only add the weights to the leaves of the tree, the total weight should be divisible by 2treeDepth, which, I believe, is not true for the fifth test in the testset
•  » » » » 17 months ago, # ^ |   0 This is not true. See the first clarification on the message board — you may add any real number to the leaves. In your example, we can add 0.5 to both of the "2" leaves.
•  » » » » » 17 months ago, # ^ |   +3 Oh, I've missed that clarification. Now it all makes sense: the problem, where you are allowed to put the weights to non-leaf vertices and the problem where you are allowed to add any real number to the leaves are equivalent. Thanks!
 » 17 months ago, # |   +18 How to solve the 5th problem?
•  » » 16 months ago, # ^ |   +5 Sketch of the solution (I am an author of the problem):Take any 3 noncolinear points and bring them all to the [5, +inf] x [5, +inf] quadrant of the plane. It can be seen that such series of moves exists if you observe the tiling of the plane by parallelogram generated from those 3 points. Now, you can just use BFS to find shortest series of moves to bring those 3 points to that part of the plane. Since coordinates are small you can check all possibilities and see that in worst case this takes around 1200 moves.Last, you can see that after you have points A, B in quadrant [5, +inf] x [5, +inf] you can move any other point C to first quadrant with just one move.
 » 17 months ago, # |   0 Form problem D, it seems like I had to use linear diophantine and solve it using extended euclidean algo but I have no idea was it is an just gave up :(