### Vasya.V's blog

By Vasya.V, 12 years ago, translation,
1) Because of small constraints, just iterate n from 1 to Tn and check
for (int n = 1; n <= Tn; n++)
{
if (n * (n + 1) / 2 == Tn)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";


2) Let's consider a graph, where the letters A, B, C are the vertexes and if  x < y, then the edge y -  > x exists. After that let's perform topological sort. If a cycle was found during this operation, put "Impossible" and exit. Otherwise put the answer.

Another approach is acceptable because of small constaints (by Connector in russian comments).
Just iterate over all of 3! permutaioins of the letters and check if they are sorted. If no such permutation, put "Impossible"

3) Let's iterate over all of  6! = 720 permutations. For every permutation let's try to put the first 3 words horizontally, the others - vertically:
1. hor[0], ver[0] - left-up
2. hor[2], ver[2] - right-down
3. hor[1]: (len(ver[0]) - 1, 0)
4. ver[1]: (0, len(hor[0]) - 1)
Now let's define N = len(ver[1]), M = len(hor[1]).
A Conditions for the solution existence
1. len(hor[0]) + len(hor[2]) == M + 1 // edges of "eight"
2. len(ver[0]) + len(ver[2]) == N + 1  // edges of "eight"
3. len(hor[0]) >= 3 && len(hor[2]) >= 3 && len(ver[0]) >= 3 && len(ver[2]) >= 3 // "eight" is nondegenerate
4. The letters at start/end of appropriate strings are match
5. The letters on the intersection of hor[1], ver[1] are match
Now we have the right field of the size N x M, and update the answer
Note In C++ if you use vector<vector<char> > or vector<string> as the field type, then you can simply use operator "<" for updating.

4) Let's consider not the most efficient, but AC algorithm, with  the complexity O(mCn5log(Cn5)).
Let's consider the 1 answer of the system: <number, v>. The amount of the variants of the password is Cnv - not very large number in constaints of the problem, you can simply generate this variants. Declare this set of variants as current. Now, for the every answer let's generate a set of possible passwords, and let's declare the intersection of this set and current set as current. After m iterations we'll have some set. Then we'll erase elements from this set, which were in the answers of the system, and the answer of the problem will be the size of this set.

5) Let's consider an algorightm with complexity O((n + m)log(n + m)).
Exclude from considiration every wall can't be achieved by canon:  x > v2 / g
Because of α < =π / 4:
1. Function Xmax(α) is monotonous
2. Function Y(α, x), when x is fixed, is monotonous
Such observation allows to assign to each wall a section of the attack angle [α1, α2]. If this canon shoots with angle within this section, it hits the wall. These angles can be obtained by solving equation (it will be biquadratic), but because of monotonous we can use binary search.
Sort walls by x. Now the initial problem has reduced to the problem: for every shoot it is need to obtain minimal index of the wall, when shoot angle is between attack angles for this wall. This problem can be solved by Segment Tree for Minimum with possibility to update on an interval. At first, fill tree with KInf. Next, for every wall let's perform update(α1, α2, index). Then let's iterate over requests. If getMin(α) == KInf, then missle do not hit any wall and hit the land, otherwise it hit the wall with index getMin(α).

• +16

 12 years ago, # |   0 can u explain the 3rd one more?it is so ambiguous to me!!
 » 10 years ago, # |   -6 oh,I hate Segment Tree ,I hate TLE...
 » 4 years ago, # |   0 there is more efficient solution for div 2-D ?
 » 4 years ago, # |   0 Problem B can be solved using hashing, see submission
 » 3 years ago, # | ← Rev. 2 →   0 I did some pretty hardcore implementation in Div2B "so called proper brute force" can't be more brute have a look 60172369
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 We can see this problem as a directed graph, so we have to ensure that the following condition should be veryified to have an answer: 1. Every node in the graph should have not one degree at the same time. 2. There are no bidirectional edges. With the first condition we ensure that there isn't a cycle, with the second we don't have a contradiction. My sub: 60185706
 » 23 months ago, # |   0 For Problem B, After solving , I saw many solutions and some used graphs and some do loops and stuff. I wrote it using IF else haha. see it here. https://codeforces.com/contest/47/submission/86936970
 » 22 months ago, # |   0 B: Without permutation or graphs Rearrange the equations such that all inequalities face LHS i.e, x > y If the number of unique characters in LHS and RHS != 2, the solution does not exist. The character with frequency 2 on LHS is maximum and one with frequency 2 on RHS is minimum. Code
 » 22 months ago, # |   0 Why am I getting wrong answer for test no.38 of problem C ? Isn't "B..A..." lexicographically smaller than "B..B..." ? Link to my submission : https://codeforces.com/contest/47/submission/91233613
•  » » 22 months ago, # ^ |   0 Never mind,found the error.Was printing invalid answer in a corner case
 » 14 months ago, # |   0 In the first question since we need t_n to be an integer, then some n(n+1)/2 will be an integer. Solving we have the quadratic n^2+n-2*t_n=0, by the quadratic formula n=-1+sqrt(1+8*t_n)/2, since 2n+1(integer)=sqrt(1+8*t_n), we just check if the latter is an integer and we can get if it is a triangular number. https://codeforces.com/contest/47/submission/112063497
 » 14 months ago, # |   0 I guess for B we don't really have to use a graph to solve the given question. We can change them into 3 comparisons with the same direction(like all > or all <) then see if which is the smallest(in my case, you can work with largest if you wish). Hope this helps simplify things if you are stuck on B. https://codeforces.com/contest/47/submission/115702274
 » 12 months ago, # | ← Rev. 2 →   0 Could anyone please explain how this solution, https://codeforces.com/contest/47/submission/16023177, works? Im struggling to pick apart the logic, particularly with respect to isRight.