All the questions of the test I think it was an easiest problem in the set, wasn't it?

Myth wrote: I think it was an easiest problem in the set, wasn't it? Most likely problem 1 will be the one solved by the most contestants. This problem proved to be rather difficult, since most solutions are based on case argumentations and thus spread over many pages. But maybe you have a short solution?

Consider the smallest cycle in our oriented graph (it is more convinient to consider it as a planar graph), i.e. the cycle, inside of which has the minimal number of facets. Then, if the inside of this cycle however has at least two facets, we go to this inside, and, by procceding the path, we form a smaller cycle.

I think my idea is the same as that of Fedor Petrov, but I think that when he says "a minimal cycle" he means a cycle that doesn't contain any other cycles inside of it (inside - geometrically speaking). Now, if it would not be a facet, it would be easy to take a vertex, say X, and then go forward from it and somewhere hit the cycle, at point say A. Also, by going back from X, we could hit the cycle at another point say B. It is easy now to obtain another cycle inside our cycle, so a minimal cycle is a facet.... I hope it was as clear as possible, and maybe even correct, although I suspect it is the same idea as that of Feodor Petrov! A note : X could be a vertex of the cycle!!!! Even simpler I think would be to take X to be a vertex of a cycle, that has an edge, because if all the verices of the cycle wouldn't have any edges, it would be a facet!!!! Now it became even easier I think!

You wrote it before me. (I received the notification only after 50 minutes Fedor wrote it) That's is what I meant. A very easy problem.

Yes, DusT, it is exactly what I meant, but could not say in English.

i tried to find out what "facet" means on the net, but i didn't really get it can anyone explain?

Fedor means "face" instead of "facet" (in Romanian "faţă").

DusT wrote: It is easy now to obtain another cycle inside our cycle, so a minimal cycle is a facet.... i don't see the way to construct a smaller cycle in our cycle

Well, let our cycle $\gamma$ be $A_1A_2\dots A_k$, and let $A_1B_1$ be an edge such that $B_1$ lies inside $\gamma$. Wlog, it is oriented as $A_1-B_1$. Next, we find edges $B_1-B_2$, then $B_2-B_3$ and so on, until some $B_k$ equals some $A_i$. So, we get a cycle: either $A_1B_1B_2\dots B_{k-1}A_iA_{i+1}A_{i+2}\dots A_nA_1$, or $A_1B_1B_2\dots B_{k-1}A_iA_{i-1}A_{i-2}\dots A_2A_1$. Is it clear now?

now i understand how to build the new cycle and what "inside" means

Let $F$ be the set o faces.Denote by $V$ the set of vertices and by $E$ the set of directed edges.By Euler relation we know that $|V|+|F|-2=|E|$.Now,suppose that there are no cycles in $F$.Then,for each face there must exist a vertice $v$ such that $\deg^+(v)\ge 2$.Denote by $M$ the set of this vertices,such that $|M| \le |F|$(if there are at least 2 vertices,we will choose only one to be element of $M$).Then,it is pretty simple that $\sum _{v \in M}\deg^+(v)\ge 2|F|$.But $\sum _{v \in V}\deg^+(v)= \sum _{v \in M}\deg^+(v)+ \sum _{v \in V - M}\deg^+(v)=|E|=|V|+|F|-2\Rightarrow \sum _{v \in V - M}\deg^+(v) \le |V|-|F|-2$.But we know that$ \sum _{v \in V - M}\deg^+(v) \ge |V|-|M| \ge |V|-|F|\Rightarrow |V|-|F|-2 \ge |V|-|F|$ which is false.

Please check my solution

Suppose that every face is not a directed cycle. Then for every face $f$, there exist vertex $v$ such that two directed edges of $f$ incident to $v$ is pointing $v$. Call this vertex good, and let's count all the pair $(v, f)$ such that $v$ is good vertice of $f$. Since every face has good vertex, number is at least $|F|$. Now for each vertex $v$, if face $f$ containig $v$ has $v$ as good vertex, pick edge $e$ which is side of $f$ and pointing $v$, and clockwisely left to side $f$. Let's assign $f$ to $e$. It's easy to show that different faces each edges pointing $v$ can be assigned by at most $1$ face, and there exist edge pointing $v$ such that not assigned by any face. Think about two consecutive edges $e_1$, $e_2$ such that each of them pointing/going out from $v$, and $e_1$ is clockwisely next to $e_2$. Then $e_1$ is not assigned by any face. This means that number of pairs $(v, f)$ for each $v$ is at most $\deg^+(v)-1$. So total number of pair is at most $|E|-|V|$, since $\sum _{v \in V}\deg^+(v)=|E|$. But this gives contradiction, because by euler formula $|E|-|V|=|F|-2<|F|$. Remark 1. It's easy to see that number of directed faces are actually at least $2$, because number of pair $(v, f)$ is at most $|F|-2$. Remark 2. Another solution: First, triangulate our polyhedron. That is, think about minimal counterexample and pick one good vertex for each face, and draw new directed edges between other vertice of face and good vertex to direction pointing good vertex. It's easy to see that this is also a counterexample, with every face is triangle. Now pick a vertex $v_0$ such that $\deg(v_0) \leq 5$(This vertex exist because $|E|=3|V|-6$). By deleting $v_0$ and add directed edges appropriately, we can make smaller counterexample with every face is triangle. This is contradiction to minimality.