Problem A.
In this task all you had to do was to make sure that the sum of all Σxi is 0, the sum of all Σyi is 0 and that the sum of all Σzi - 0 .
We have not written that condition evidently in order that participants will have a chance to break a solution.
Problem B.
In this problem, in fact, you should find a winner at every section. For each section, you must do a full search of all competitors to find a competitor with a minimum section time, which ran that section. Asymptotic of the solution is O(nm).
Problem C.
In this task, you had to update the collection of artifacts, which belong to Kostya’s friends, after each purchase . You had to set a matrix c[i][j] - number of the j-th basic artifact that is required in order to collect the i-th component artifact. Further, one can make a matrix of composite artifacts, where a[i][j] is number of the j-th basic artifact of the i-th friend and a similar matrix b of composite artifacts, and check whether i-th friend has any a composite artifact of O (MN) after each i-th friend’s purchase. Check whether one component of the artifact assembles for O (N): while checking whether the i-th friend is able to collect the j-th artifact you have to check, if there is such u, that c[j [u]> a[i][u], if so, the j-th artefact will not be collected, if not, then you have to increase the b[i][j] and update the values in a[i]).
So.the asymptotics of the processing of all purchases will be O (NQM). Then, we need to make a list of artifacts for each person, keeping their quantity(a total of O (KN + KM), and sort it (a total of O (QlogQ)).
Problem D.
This game is over, because except for a finite number (2) of reflections about the line y = x,the coordinates are changed to non-negative integer (and at least one coordinate is changed to a positive number).
Algorithm for solving this problem is DFS / BFS (states) where the state is a pair of coordinates, and two logical variables, which denote if the 1 (2) player had reflected a point about the line y = x.
Total number of states is obtained by S <= 4D^2 (pairs of coordinates) * 4 (Boolean variables).
Processing of one state takes O (N) actions (do not forget to try to reflect the point about the line y = x, if the player had not made it earlier in the game). Thereby, we have the overall asymptotic O (ND^2), which works on C + + in less than 200ms.
Problem E
To solve this problem you have to do a "move" subsegment and know :
1. The set B of numbers, meeting once, with the function of extracting the maximum for O (logN)
2.The set of numbers appearing on this subsegments with keeping the number of times,that this number is found on this subsegments, with function of verifying how many times the number in this subsegments for O (logN).
While moving a segment from (a[i] .. a[i + k - 1]) for 1 item left (a[I + 1] .. a[I + k]) you have to:
1) Check whether a[i] with a[I + k]. If yes, then there is no need to modify the set, otherwise proceed to item 2 and 3.
2) Check how many times we have a[i] in the set A: if 2, then add a[i] to B, if 1, then remove it from A and B. Do not forget to reduce the corresponding number of occurrences of a[i] in the current segment 1.
3) Check, how many times we have a[I + k] in the set A: if 0, then add a[i] in the B and A, if 1, then remove it from B. Do not forget to increase the corresponding number of occurrences of a[i] the current interval to 1.
After that, if the set is not empty, we should take peak from it.
So the asymptotics of this process will be O(NlogN).
As such data structures set / map(for those who use C + +) and the Cartesian tree are suitable.
Here is my approach:
Process first K numbers at once. Store frequencies of each number in hash table and maintain a set which contain values which occurred only once. then process rest of the numbers while taking input. reduce frequency of i-K th number, modify the set according to frequency.
Suppose input is:
6 3
1
1
2
6
6
First i will process first 3 numbers. so the set will be {2} and map will be freq[1]=2,freq[2]=1.
When i get 4th number 6,i will reduce freq of 1st number. freq[1] will become 1 from 2. as it has become 1,the set will be {1,2,6}(as i got 6 for the first time).
Then i get 5th number 6,i will reduce freq of 2nd number. freq[1] is now 0. as it went 0 from 1, i need to remove it from set too. so the set becomes{2}(i will remove 6 too as i got it 2 times now).
Every time print the largest number from set. If the set is empty print "nothing". i've used c++ stl <set>.
When I changed "double" to "int" in task E, I've got AC (with double - WA). But I can't find any words in problem statement about representation of numbers in answer. Also I can't find nothing in problem statement to determine if numbers are integers or not...
ATTENTION! THIS CONTEST SHOULD BE UNRATED!
Maybe now you will read my message carefully :) I think that Corny is right. His solution works just after replacing "double" to "int".
Really? Ok, try to output floating-point numbers with 1e-10 precision.
I think result would be the same :)
b 1
c 2
So your solution is wrong. After buyin first 'a' artifact player has oportunity to build artifact 'c' but in your solution he didn't take advantage of it, he waited for the second 'a' to compose 'b'
It is just a mathematics Question Just apply For loop and at the end the if, else statement...
In problem A testcase 50 is wrong anyone can help??
Hi, I'm a beginner. I am wondering if there's an error in the test cases.
For problem A, I get a wrong answer on test 81 even though I passed all other test cases. My solution involves putting all x_i, y_i and z_i values in one array and just iterating over the array elements to sum, then seeing if sum is zero or not. I can't understand why I got this one test case wrong when all other 80 test cases where right.
Here is test case 81: (my output for it is YES, because the sum is 0) 3 0 2 -2 1 -1 3 -3 0 0
You're understanding the problem wrong. You are supposed to make the sum of the x coordinates equal to 0, the sum of the y coordinates equal to 0, and the sum of the z coordinates equal to 0.
For example, in TC 81, the sum of the x, y, and z coordinates, respectively, is -2, 1, and 1. Together, they sum to zero, but it isn't in equilibrium.
I just changed my code to have three input arrays for each vector component. It's working now. Thanks!
There is no need to take input array you can just iterate and add them in 3 different variable and then check these variable . This comment was just to help beginner:)
Problem A
I did first sum of all coordinates(xi,yi,zi) and checked if it is 0 or not, but it failed on test case 81 . Then I did following changes in the code then it failed on test case 1 .
Any help on this problem !
include <bits/stdc++.h>
using namespace std;
int main() {
}
https://codeforces.com/contest/69/submission/52241213
For this accepted solution why do we have if all(friends[ai][basic]==cnt for basic, cnt in combo.items()): surely it should be if all(friends[ai][basic]>=cnt for basic, cnt in combo.items()):
did the composite artifacts have to made exactly and only once?
In Question D, why do so many of solutions add +200 (or +250) in the DFS? What are they trying to achieve with this?