polingy's blog

Invitation to ProCon'16
By polingy, history, 8 years ago, In English

Hi Codeforces,

We at IIIT-Delhi would like to invite you to ProCon 2016, the annual programming contest conducted as a part of our technical festival. We will have 6-7 problems of varying difficulty over 2.5-3 hours with ACM style scoring. Also, there are prizes worth 20k INR for top Indian students.

Event poster

Contest starts August 6, 2016, 21:00 IST
Check in your timezone here
Register at: http://esya.iiitd.edu.in/events/procon/register(for prizes)
Link to contest: https://www.codechef.com/PROC2016
RSVP: Facebook event

EDIT: contest starts in less than 24 hours.
EDIT: contest starts in 3 hours. We have 6 problems, and 2.5 hours for you to solve them. Good luck!
EDIT: contest ends in 1 hour, 2 problems remain unsolved.
EDIT: Winners will be listed here after a plag check, and contacted by email for prizes. There will be a replay on the next Saturday(August 13) in the CF Gym. An editorial will be published after the replay.
EDIT: Problems were set by the following.
rjalfa0 -> A
slender_hangman -> B, F
polingy -> C, D
lifecodemohit -> E
The problems were tested by the above, and AmbarPal and kzanmos.
UPDATE: Winners
1. rajat1603
2. sidhant
Winners will be contacted by email regarding prizes.

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

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

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

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

What is the expected cutoff for Procon Junior? I got 500 :)

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

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

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

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

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

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

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

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

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

Seems like the problem statement for Gangsters' wasn't clear. You are not required to pay for node t, but paying at s is mandatory. Interestingly, I had asked about this in the comments, and I was told that paying at both is mandatory, which is not the case. I guess the statement wasn't clear among the panel as well xD

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

    I didn't assumed anything as such to not pay at t. But it passed.

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

      How to solve it ?Using bitmask,right?

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

        Yes. Precompute nodes within distance k and set their mask to have bit i on. Try all masks of people to pay. Choose the one with minimum cost that allows you to reach t from s. Prune this a little bit to fit under TL.

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      6 5 1 1
6  
100 
1 2 
2 3 
3 4 
4 5
5 6 
1 5

      Expected answer for this was 0 instead of 100.

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

        Are you sure? Mine prints 100 but gets AC

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

          Idk. Mine prints 0. I added an if statement to ignore the cost of the end vertex and my code became TLE from WA. Then I changed dfs to bfs and it passed..

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

            Changed DFS to BFS

            What did you use DFS for in the 1st place? -_-

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

              I forgot that I needed your permission to use depth first search. Apologies.

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

              For each mask he would have used dfs to check if it is possible to reach from s to t with that..

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

    Hi, the panel was quite clear on the statement. If s or t are in a gangster's territory, you have to pay them.

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

How to solve this : https://www.codechef.com/PROC2016/problems/PRCS16B

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

    Fix the number x that A will take. Then make an array C -> C[i] = 1 for all positions i such that B[i] = x, else C[i] = 0. Number of cyclic shifts required is now the maximum distance between two adjacent 1s in the circular array C. Add N to the final answer to account for the assignment costs. Note that if C has just one 1 then number of shifts needed is N - 1.

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

Are they going to publish proper editorial or something like that ????

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

Solutions aren't visible. Please share approaches for E.

The time limit was huuuuge that points almost towards a bruteforce (12 secs), however it didn't passed.

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

    We will publish editorials after a replay. A brute force solution will not pass ^.^

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

    Minimize Tree :-

    Let (x, y) be the edge we are removing. The added edge (u, v) will have u in the subtree of y and v outside the subtree of y. I think that v should be the node with the least depth outside the subtree of y and u should be the centroid of the subtree rooted at y. This would be O(n). Was this the expected solution?

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

      Interesting, we implemented v the same way you talk, but for u, our algorithm was substantially different. What you are saying is probably correct though, we can discuss in more detail after the replay. EDIT: can you test your idea on the second sample, I think it doesn't work there

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

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

→ Reply