Equinox's blog

Byterace 2K17 IIT Patna
By Equinox, history, 7 years ago, In English

Hello Codeforces!

I would like to invite you all to Byterace 2K17 to be held on codechef. It is scheduled on Wednesday 15th February 2017, 9:00PM IST.
The contest will be 3 hours long and will have 6 problems.
It has been prepared by me(Equinox), I_Love_Equinox and cc15. We have given a lot of effort in making the problems and hope that you would like them.

Prizes

  • 1st Prize 5,000 INR
  • 2nd Prize 3,000 INR
  • 3rd Prize 2,000 INR

)

Note

It is not necessary to be a college student to win prizes. Just fill "NA" in college field in the google doc given on the contest page.

Update

Problem authors and their respective problems-
I_Love_Equinox — FGAME, BATGRAPH, DIVIS
Equinox — ADWAR, MODNIM
cc15 — CHARR

Congratulations to the winners. The top 5 are as follows (all from different countries).
Deemo
rns4
nuip
YerzhanU
SameerGulati

Editorials

MODNIM

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).

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

Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

LOL! i_love_aishwarya_tandon ,, bro use a One time pad to keep it secret :D

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

Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).

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

Reminder:- The contest starts in 30 Minutes. See you at the leaderboard.

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

Prizes are only for indians, right?

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

    Its for everyone.

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

      When will I receive the prize?

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

        We will be contacting all the winners soon via email regarding the prizes.

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

Again the same CodeChef bug: I solved 5 problems, but it only displays 4. It is because I submitted ~30 seconds before the end of the contest.

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

    We will take that into consideration. But the first 3 have solved all problems.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Editorial or short descriptions ?

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

    Here are the problems that I solved in contest time:

    FGAME: We have c[0] white balls and c[1] + ... + c[n - 1] black balls. Try to put just one white ball in every box, and all the remaining white and black balls in the last box.

    BATGRAPH: The bridges of the graph generate a tree of biconnected components. The answer is ⌈ leafs / 2⌉ (why? look at the centroid of the tree)

    CHARR: We only have to calculate the longest path in the pseudoforest.

    DIVIS: Let's concatenate all the strings, then we can do dp: f[i][len][r] is the number of subsequences starting from i of length len and congruent with r modulo d

    ADWAR: Create a polinomial P(x) = f0·x0 + f1·x1 + ... + fn·xn, where fi is the number of soldiers with strength i. We can calculate the number of pairs that sum s by looking at the coefficient of xs in P(x)2

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

      Regarding BATGRAPH leafs/2 seems is not right. Counterexample:

      1

      6 7

      1 2

      1 3

      2 3

      3 4

      4 5

      4 6

      5 6

      Here we have bridge 3->4 which should be directed to one side and we need make another component reachable by adding one edge.

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

        After generating the tree, we get only 2 vertices and two leafs: [1 2 3]-[4 5 6]. We have to add just one edge

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

          There is no vertex 7 in my example.

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

            Yes I've updated the image, I thought 6 7 was an edge :)

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

              Oh I see what you mean. You mean leafs after compressing biconnected components. I thought you were talking about leafs at initial graph. Both solutions were passing tests so I was confused.

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

        Test data were too weak.The very first successful submission for BATGRAPH prints 0 for this input graph while the correct answer is 1500.

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

      In BATGRAPH can you explain what leafs are in that tree of biconnected components?And can u explain the leafs/2 part?

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

        Hi, I am the author of this problem. First you must understand that we will the create a new tree in which each node will represent a biconnected components and an edge between them will represent "cut-bridge" between the respective components. Now, you can see that it will optimal in this tree to connect the leaves in such a way that it minimizes the number of edges added. So, how to connect these leaves? After some observation you can find that connecting leaves is reducible to find the maximum matching in a complete k partite graphs, where k means here that the there are k subtrees on a particular root of the tree. There's a standard result that x1 + x2 + x3 + ... + xk - 1 ≥ xk where xi represents number of leaves in ith subtree, then matching will be (x1 + x2 + .. + xk) / 2

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

    For MODNIM — Trump will only lose when he gets all the heaps of size 1 and the number of heaps is divisible by 3. Obama will win only when he can convert the given heaps into this form. I will be posting the proof soon.

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

      that facepalm moment when I got the correct solution to MODNIM fast and then waited for 1 hour before realising that I missed out on an "else" part of code :(

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

      Can you tell the proof for MODNIM's solution ?

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

4th :'(

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

Auto comment: topic has been updated by Equinox (previous revision, new revision, compare).

→ Reply