MikeMirzayanov's blog

2013-2014 CT S01E05: Codeforces Trainings Season 1 Episode 5
By MikeMirzayanov, 11 years ago, translation, In English

Welcome to 2013-2014 CT S01E05: 2007 Nordic Collegiate Programming Contest (NCPC 2007) + Selected Problems from 2009 Google Code Jam World Finals (GCJ WF 2009). The training duration is 5 hours. It is opened for teams as well as for individual participants. After the end you may use the practice mode to complete problem solving. Also it will be availible as a virtual contest for whose of you who can't take part today. Please, do not cheat. Only fair play!

It is possible that the problems will be too easy for some participants, it is possible that we will add some problems.

The registration will be available on the Gym page and will be opened until the end of the training. Be careful registering team: please, choose only whose members who will take part in the contest.

Good luck!

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

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

Note that for the NCPC part of this contest, there's a problemset analysis and all you might want to see (like judges' solutions) available at http://ncpc.idi.ntnu.no/ncpc2007/. That means there's no need for an editorial :D

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

How to solve K?

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

For Problem G (Nested Dolls) How it can be solved ?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

After solved problem B by disjoint-set principle, I read other codes and found this problem can be solved by a number different techniques : max-flow ; bfs-dfs ; and even brute force (!). Can anyone explains the solution by max-flow, please ?

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

    follow this steps :

    1. add two special nodes to graph ( Source and Sink ) .
    2. add some edges from Source to every left side nodes with one capacity .
    3. add some edges from every right side nodes to Sink with one capacity .
    4. find max-flow of this new graph .

    if max-flow of this new graph equals to number of words( left side nodes ) , then there is exist a Cuckoo hashing .

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

Since these competitions are mainly for practicing so why we are not allowed to view other codes ? really viewing other codes helps alot.

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

    Probably because self help is the best help :)

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

      Well , at first you should try to do it by yourself and keep thinking till some point you may give up and want to know the answer , probably the answer to the problem has a proved theorem that you don't know or it is really hard for your current skills to get , in that case you should search for solutions better than wasting your time in a single problem and since I'm going to search in google or somewhere else then viewing solutions would be easier and better.

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

        this time they have supplied the tutorial :)

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

          Yeah Xellos did , and he doesn't have to do it everytime + tutorial improve our thinking skills with getting the idea but looking at some coders' solutions will improve our coding skills especially if the code belongs to a good coder. It's not an argument It is just my opinion. :)

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

            Actually, writing a tutorial helps me a lot more than it helps everyone else. That's because I need to prove stuff properly and code hard problems that I would've left hanging otherwise. I don't complain about the contribution going up, though :D

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

http://ideone.com/YKHlC8

This is my code for Problem L ELection. I am having trouble coding. Would really be glad if someone can help me out on this. I am implementing a trie and doing updates.

Any help will be really appreciated.

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

    input :
    2
    A B C
    GroupA
    A BC
    GroupB
    3
    A B C
    A BC
    ABC

    Correct Answer :
    tie
    Your answer :
    GroupA

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

How to solve I?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

EDIT: Turns out that I must have added some inefficiency with the way I purchased fuel. I reimplemented right now, worked fine.

Original: Looks like the time limit is too strict for Java on F. While not 100% certain my algorithm is optimal, based off of the problem set analysis posted by Xelios, I have the intended algorithm...

→ Reply