ashish1610's blog

Invitation to Procon 2015
By ashish1610, history, 9 years ago, In English

Hello Codeforces Community!

IIITD invites you to Procon 2015, the annual programming contest conducted as a part of our technical fest. We, the problem setters have tried our best to make problems of varying difficulty levels so that there is something interesting for every participant.

Time: The contest will be held on 8th August, 18:00 IST. See the time in your timezone here: link

Contest Details: The contest will be held on the codechef platform here: link

Problem Setting and Testing Team: Ashish Khatkar (ashish1610), Mohit Wadhwa (lifecodemohit), Ambar Pal (AmbarPal), Priyanshu Singh (tgamerz), Anmol Singh (kzanmos), Gaurav Rathee (garyclay08).
Special thanks to Kshitij Jain (kshitij_jain) and Rohan Garg (rohangarg) for their guidance and reviewing the problems.

Prizes: Only for Indian students
Cash prizes: INR 15000
Total Prizes: INR 25000

Hope to see a lot of participation!

UPD: Reminder, contest starts in less than 1.5 hrs.
UPD: Contest has already started less than 2 hrs to go.
UPD: Contest is over. Editorials will be published soon.
UPD: Editorials for all problems except Graph Sum is published. You can find them here
UPD: Editorial for Graph Sum is added.

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

Comments Comments (30)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Colorful problem setters!

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

Why prizes only for Indian students?

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

    Maybe because the contest is being organized by the programming club of the university which is completely run by students and thus it would be hard and expensive for the students to send the prizes to international competitors.

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

    The intention of the contest is to promote programming among Indian Students :)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
Duration: 3 hours
Start time: 8th August 2015, 1800 hrs IST
Ends time: 8th August 2015, 2030 hrs IST

... so how long is it?

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

    We are getting the discrepancy corrected. Contest duration is 2.5 hours.

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

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

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

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

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

Nice problemset, I enjoyed it :)

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

The problems didn't all load at the same time for me and I've never used codechef before so I got confused and just clicked the first problem I saw... so I ended up solving Code Land before I realised there were 4 easier problems. I regret everything.

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

    We are sorry for the goofup. The problems were getting synced thats why there were only 4 problems initially.
    I hope you liked the problem set.

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

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

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

Doesnt this question " https://www.codechef.com/COOK35/problems/TYTACTIC " look a lot similar ?

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

    I can assure you that we did not see this problem earlier. We'll look into this.

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

      I had no solution in mind , so I tried to google for some hints. "update vertex sum of subtree" is the query that landed me this question and it's tagged editorial ( but I didn't copy and avoided this question :P )

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

        There are a lot of problems with update element sum subtree or update subtree sum subtree:) What was really the important idea was the exponentiation and to reduce it to matrix of 2x2. I got tle first because I didn't see that m=2*sutm_of_1_and_2

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

    But of course there are similar problems. It is almost impossible to come up with an original query problem. I have given a problem with updating tree vertex values and calculating subtree sums myself before, just as there are tons of different problems about sums/minimums/maximums/different numbers queries.

    In my opinion the interesting and original part of the problem was to generate the last 5 digits of the N-th fibonacci number quickly :)

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

How to solve Code Land Problem?

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

    Editorials are up.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    1. Find bridge tree of the given graph. (new graph consisting only of bridge edges of given graph).
    2. For every pair of vertices on the bridge tree , find the minimum cost to disconnect them and the best cost of joining them. answer is max of all these differences.

    Code (AC) : http://ideone.com/Mfu9PK

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

In my opinion Code Land was significantly easier than Range Queries. Perhaps I'm missing some easy solution of Range Queries?

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

    I solved it using Mo's algorithm, however did not come up with solution for Code Land problem. What was your approach for it?

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

      Thought of sqrt decomp for range queries but no ideea... Waiting for editorial to see new ideas with mo's algorithm :)

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

        Hello, BAM! Good to see you ;) In Romania, "Mo's algorithm" is the RangeMode "smen". You just solve the queryes offline sorting by some points which are marked from sqrt to sqrt(the most left one). In case of the same point, you sort by the right limit. In this way it is very easy to process the queryes using a Fenwick Tree. Read the solution to that problem, maybe it will shed some light, bro.

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

      I used the same algorithm for Range Queries. For Code Land my approach was as follows:

      We'll be aiming for O(N2) complexity per test so it's fine to generate the costs of each edge using the function provided. Then it is clear that we'll be removing some critical edge, so let's build the DFS-Tree. We can in O(N) find all critical edges and mark them as critical (though finding them in O(N2) is fine too).

      Now let's take some edge A - B and say that this will be the edge we'll add after removing some other. Imagine the DFS-Tree and vertices A and B in the tree. The edge we'll have to remove is some critical edge along the path from A to B in the tree. Out of all critical edges along that path, it makes sense to remove the one with the minimum cost.

      There are O(N2) paths in the DFS-Tree so we can precompute the cheapest critical edge along each path. Afterwards we can simply try all O(N2) edges as the "add" edge and in O(1) find which edge we'll have to remove.

      All the steps are very easy to implement in O(N2), so I was surprised to see so few people that managed to solve the problem :)

      Note : By DFS-Tree I mean the tree formed by the edges chosen by DFS traversal. Of course this is just a random spanning tree of the graph.

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

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

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

Can "range queries" be solved in anything faster than n*logn*sqrt(n)? (n*logn or n*sqrt(n))

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

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

→ Reply