MikeMirzayanov's blog

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

Welcome to 2013-2014 CT S01E04: 2013 Kashan Contest + Some Problems of 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.

The most problems were given by mohammadrdeh. Thanks! It is the great help. Take example!

Good luck!

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

Comments Comments (41)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I think, that solutions in the Gym section should be opened for everyone. In my humble opinion Codeforces is the best community of programmers, mostly because you can learn from others.

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

    ^Very True.I also think that the solution should be opened for all to see and learn new techniques.Please see if this can be done.

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

    I agree with you! It will be very useful for many programmers, if the solutions of all participants will be available after you've finished the contest.

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

      I don't agree, some people just spoil the rank list by virtual participating and submitting solutions in less than 1 minute. Moreover there are thousand of problems in Codeforces all with category and solution and editorial, I think that's enough for practicing.

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

        I mean that solutions will be available after you have written a contest "online" or "virtual", that is, when Resolving. How you know "Resolving" does not affect to the rating.

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

        But the solutions can be found easily online anyways. It's not a rated contest, so why does it matter?

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

    I think soooo

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

nice problem setter

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

Hello everyone,

It's my first time participating in a training competition of codeforces and I would like to ask if the results afect the contestants rating.

Thank you very much for reading my question and I would like to wish everyone good luck to the upcoming event!!!

Have a nice competition, Adamos2468

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

I hope you all enjoyed our problems. Also I want to thank my teammates, Alisafe and leviathan. Without their help I could not be able to prepare this problemset.

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

    Thanks a lot for you and your teammates! It was really good contest — well-prepared and interesting. Also I'm sure it is right policy to share contests with community.

    Hope, it could be a good tradition to use local contests for public trainings.

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

How to solve problem G and K and also L ?

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

    K

    Since P = product of primes, it can have at most 2^7 divisors (when P = 2*3*5*7*...). Thus you can do dynamic programming with state (how many number used, divisor of P).

    G

    It is data structure problem. You need to maintain which person is standing and how many pairs using some data structure. It's quite hard to explain in words. You can see code of ntu_tst_004

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

      what about L ?

      In Gym, you cannot see others code, without solving them . :( can you send me your code to my inbox. :)

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

      -

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

      hello! can you explain the problem K please!!

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

    L: let's generate graph of alphabet by edges from input. It's obvious that this graph is some numbers of cycles. Let's look on first character of our text, call this character s0. We must change it to lexicography best character. Let we change it to some other symbol — obvious that this symbol must be the best lexicography symbol in cycle which contain s0. Let this symbol is placed d0 symbols after s0. Than X = l0*k0 + d0, where l0 — the length of cycle which contain s0, k0 — some number.

    Let's look on i-th possition. Tryed to place different d[i], we must choose such that system of equations l[i]*k[i] + d[i] solvable and this d[i] best lexicography. How to check if solvable? Prefix of system of equations [1..i-1] solvable, we must check that last i perhaps for first [1..i-1]. Check it: solve this system l[j]*k[j] + d[j] = l[i]*k[i] + d[i], it's diophantine equations.

    I hope that you understand our solution:)

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

hello everyone

one asked where I find the problems of this gym for submit again?? please!

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

How to solve problems D,E? Is E solvable in doubles?

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

    the problem E require more precision geometry

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

      the problem D is MST can you use kruskal o prim !!

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

        http://codeforces.com/gym/100236/submission/4642949 — why this idea is wrong?

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

          I dont see these code

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

            can you explain your idea I dont understand your code

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

              First, let's sort edges in decreasing weight order. IF edge connects vertices in different connected components. Then we take all edges with weight <=c and look if it connects vertices in same connected component. if they vertices are in same component, we take two components with the least(or biggest) rank in DSU and unite them. And in the final part we unite all componentsnot connected with the first vertex and pay c for this.

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

                good first make sort in decreasing weight order. then run kruskal

                now know how many road missing now check the road no used in kruskal y with weigth <= c and add is all

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

                  in order increasiing the last part

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

I very humbly request codeforces to open solutions of gym for public. If they do not want to open the submissions for all, then please give us a good logical difference between gym contests and regular codeforces contest policy of submissions.

It would be really helpful if we would be able to see the solutions.

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

    If they open solutions, standings will be spoiled by solutions with less than 1 minute. I know that some people aren't bothered with that stuff, but some ARE.

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

      This logic applies for the codeforces Div1, Div2 rounds too, Does the static standing matters. How can you stop somebody from submitting the solutions if they are available for learning, they might as well use direct solutions or might tweak them, I can not think of a reason to do so.

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

      Your logic makes no sense. I could very easily obtain all the solutions and then create a new account and do the thing you said.

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

      You would like to hamper the learning progress of people in order to keep your ego intact, surely a good logical approach.

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

Any Hints for ProblemC — Combiantion Locks?? I tried an approach using bitmasking, but was unable to decide among many states which to keep and which to reject??

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

    Try to enumerate answers for little sizes. Then you will seen some interesting things with sum of elements)

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

      Thanks for your hint.Do you konw how to prove the result?

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

Since there don't seem to be any official test data / judges' solutions available for this one, I guess I'll write an editorial. Just hold on!

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

wow ,i'm stuck in nostalgia ,i have 20GB pic and movies form this contest in Kashan. thank u mohammadrdeh for ur nice problems.

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

Is there an analysis for the problemset?

→ Reply