dario-dsa's blog

COCI Contest #7 (Croatian Olympiad in Informatics)
By dario-dsa, 11 years ago, In English

hi, a Croatian Olympiad in Informatics will be held at time.

  1. Where do I register for the contest? Everyone with an account on evaluator.hsin.hr can compete. There is no additional registration for the contest.

  2. Who is eligible for participating in COCI? Everyone (but not teams).

  3. Should I use %lld or %I64d for long long input/output in C++? %lld.

  4. How fast is the CPU of the evaluator? model name : Intel(R) Xeon(R) CPU E5520 @ 2.27GHz 4 cores

  5. What are the input / output file names? You don’t read the input from files, you don’t print the results to files. Use standard input and standard output (stdin/stdout).

  6. My code received "Non-zero exit code (#).". What does that mean? It means your program crashed on our machine. You may want to use the test interface to see more details about the error.

  7. What compiler and flags are used to compile my source? We are using the following compilers and flags: Language Compiler Flags C gcc 4.7.2 -std=c99 -O2 -static -s -lm C++ g++ 4.7.2 -O2 -static -s -lm C++11 g++ 4.8.2 -std=c++0x -O2 -static -s -lm Pascal fpc 2.6.2 -O1 -XS Java javac 1.6.0_27 Python python 2.7.3

  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you for the notification. Will you always notify COCI contests into Codeforces?

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This contest starts 2 hours before TCO14 Round 1A, but lasts 3 hours.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Actually, the duration of this contest is 5 hours.

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

In case anyone was curious, short solution ideas:

  • CSS: construct a tree where each vertex contains element name & set<> of classes (the root represents the body of the page); for every query, check which vertices match each classifier and do a DP (DP[i][j] denotes whether the first i classifiers can match some vertices on the path from the root to vertex j); for "ancestor" relations between consecutive classifiers i, i + 1, do a BFS (if some vertex had DP[i][j] = True, then all its children will have it True) before computing DP[i + 1][]; map the class names to ints, so the complexity is , where L is the max. number of class names in 1 query

  • HISTOGRAMI: sweepline DP — sort the points by the x-coordinate, compute B[i] — min. error if we ended a horizontal segment at point i (take just the nearest point to the left of the current one), and from that A[i] — min. error if we ended a vertical segment there (find the point with the same x-coordinate and smallest B[i]), also keep 1 more array that says from which point we'd need to make the last segment to get that answer and reconstruct the full answer from it; in order to know B[i], compute using another sweepline W[i] — the error we'd get if we had just 1 horizontal segment (0, 0) - (0, i); for type 1, it needs just 1 array where we mark how many heights in that segment would add 0 to the error, for type 2 we need a BIT where we store, for each height y,  + y in F[y] (so we can sum up the heights  ≤ t); complexity:

  • MOSTOVI: you never need to take 3 bridges, because you'd get a cycle in your path, and that leaves 3 cases; keep the whole segments connected by 1-way roads in a map<>, which allows you to check if you can take 0 bridges; for 2 bridges (A,B), bridge A must be after G1, bridge B before G2 and there must be a path from the other end of bridge A to that of bridge B, so we can take just the first possible A and last possible B (for that, keep the bridges in a map<>) and check if this path works; for 1 bridge, bin-search the last bridge (or its endpoint) that's after A, reachable from A and before B, and check if B is reachable from it; bin-search on map takes and the other 2 types of queries just (per query)

  • NIZOVI: always bin-search how many points in the right array are smaller than the leftmost one in the left array, reverse these points, reverse the left array and reverse them both together; the result is correctly sorted up to the smallest point of the left array, so ignore that (correctly sorted) part and run the same algorithm on the new array, which has the same form as before, just with new NA - 1 and some smaller NB; that means at most 20NA comparisons, 3NA reverses and reverse cost at most 2NB + NA(NA + 1) (which almost fits, just needs some optimization)

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How can i submit problems,I didn't find.

→ Reply