|
|
|
Advices
- Make a heterogenous team - people that know Java (has Bigint and JFC), and C; you should be able to cover to a very great degree, the possible problems
- Start with easiest implementable problem
- Precompute data
- Use the multi-tasking of the machine - run another problem in the background while coding a problem
- coNP intersected NP is mostly P
- Robust design is important in the sense that all cases have to be thought of
- Good OO design doesn't matter. Don't try to implement complicated design patterns
- Remember that time is very precious
- Imperative programming should suffice
Reguli de aur pentru mine:
- de verificat sample input-urile cu output-urile
- atentie la introducerea input-urilor!!!!
- sa acopar toate raspunsurile cu cazuri de test
- avut grija la limite i8,i16,u8,u16
- sa citesc corect enuntul
- ma gandesc la limite timp --> ce complexitate ar trebui sa aiba programul (nu merita acceptat mai mult de 5 sec pe test)
- ma gandesc la limite spatiu
- sa am f.f.f clar in minte cum anume sa rezolv problema, preferabil sa am o schita serioasa a ei pe hartie
- in timp ce gandesc algoritmul scot cazuri speciale de test care pot sa-mi buseasca programul
- de testat algoritmul pe cateva seturi de date, pe hartie
- teste mai multe decat cele scrise pe hartie - sa aleg vreo 2 teste medii si vreo 2 critice!!!!!!!
- nu cumva am facut niste modificari de debug si submitez problema cu modificarile respective? Mare atentie inainte de a submita problema
- nu sta prea mult sa cauti greseala la o problema. E posibil sa fie o problema usoara nefacuta.
Algos
* Exact, normally polynomial solutions
* Sorting, recursion, Greedy, dynamic programming
* Min-max search, A*-search
Types of problems
* Graph algorithms
o Minimum Spanning Tree (MST)
o Dijkstra's shortest path
o Max flow, bipartite matching
* combinatorial
o Longest increasing subsequence
o Binpacking
o 2SAT
* Use mathematical properties
o Linear algebra
o Viete's relations for polinomials
o Big numbers - more than 32 bit ints
o Inversions in a permutation (merge-sort like)
o kth order statistic
* Computational Geometry
o Convex hull
o Line intersection
o Closest points in 2D. Also Voronoi diagram
o Polygon intersection
o Pyramid reaches equilibrium - mass center computation, 3D rotations
* Parsing mathematical expression and evaluating them
* Data structures - Hashing, Binary heaps, trees
* Non-standard
o Optimize an iteration inside a function
About contest:
* Input data might be non-trivial in some cases
* Solutions are tested extensively by the jury
* Errors:
o Wrong output
o Presentation error
o Time limit exceeded à efficient algorithms |
|
|
This wiki