divyam's blog

Perplexed — Codefest'17
By divyam, history, 7 years ago, In English

Hi, Codeforces Community!

Codefest'17 — a diverse roster of high-quality programming competitions by Department of Computer Science and Engineering, IIT Varanasi is excited to present Perplexed — the constrained programming event.

The contest will take place at HackerRank (https://www.hackerrank.com/perplexed-codefest17 ). This contest will be an individual event with a duration of 5 hours, from Sep/22/2017 15:30 UTC. With the creativity that the problems will naturally encourage and INR 50,000 at stake, there is absolutely no reason for a programmer to not give this one a shot!


The questions here will bend your mind in different ways — this is not your normal coding contest! After all, tackling various kinds of situations and challenging constraints is what makes programming an art :)

Prizes -

1st (Overall) — INR 20,000
2nd (Overall) — INR 12,000
3rd (Overall) — INR 8,000
1st (India) — INR 7,000
1st (IIT Varanasi) — INR 3,000

To be eligible for the prizes you must be registered for the Perplexed event on http://codefest.tech/dashboard/events/. Innovate or stay perplexed!

UPD1 — Contest will start in 2 hours. It will have 12 problems to be solved in 5 hours.
UPD2 — Contest has started.
UPD3 — Contest has ended.

Overall Winners —

  1. tourist
  2. uwi
  3. Deemo

Indian Winner — sp_502
IIT(Varanasi) Winner — ab13123002

Thank you for participation and hope to see you in other Codefest'17 events.

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

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

Auto comment: topic has been updated by divyam (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 divyam (previous revision, new revision, compare).

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

How many tasks?

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

Why doesn't it appear on the contests page on HR?

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

    It will soon be available in the college contests section of Hackerrank.

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

      Holy shit! Been using HR for more than a year and did not know it had a 'college contest' section :P

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

You can have a look at last year's contest to know more about the type of problems.

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

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

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

What do you mean by constrained programming?

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

Auto comment: topic has been updated by divyam (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 divyam (previous revision, new revision, compare).

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

how to run the executables in linux?

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

    Linux users should use .out file.
    In command line —

    chmod u+x filename
    ./filename

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

Any idea why this TLEs?

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

    I suppose !! works in linear time (Haskell lists have no random access).

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

In lying detective problem, for this test case,
4
a b c
aacb
The answer I am getting is 3(aacb(0, 2, 3), acb(0, 2, 3), acb(1, 2, 3)). But the actual answer is 4. Can any one tell me the other subsequence?

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

    Substring aacb = 3(aacb(0, 2, 3), acb(0, 2, 3), acb(1, 2, 3))
    Substring acb = 1(acb(0,1,2)

    You have to find the answer for each substring and sum up the values.

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

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

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

How do you solve The Six Thatchers?

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

    Requires an approximate algorithm.
    Choose any two indices randomly and select all numbers from 1 to 10^5 which give the same remainder for these indices. Check whether any of these (p,m) pair form the answer. If you iterate the above process 10 times, the probability of not getting the correct answer is about 10^(-30).
    Thus, the solution works because k/n is less than equal to 0.02.

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

      If you iterate the above process 10 times, the probability of not getting the correct answer is about 10^(-30).Thus, the solution works because k/n is less than equal to 0.02.

      How do you derive this? The concept seems similar to 844D - Interactive LowerBound but a derivation would help me understand better.

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

        As k/n <= (1/50), The probability that you will select at least one number from the removed set in one iteration is approximately (1/25) . So in 10 iterations it becomes very less .

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

This code shows correct answer on local machine and doesn't look like having any undefined behavior. Can anyone check?

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

    Just in case anyone's still wondering, the code 

            if(i==2)tr(temp)
	if(temp){}

    changed to 

            if(i==2)
	if(temp){}

    on online judge and became a nested if statement, which became the reason for wrong answer.

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

      Can you please explain a little more? Why would the online judge discard the macro? I am not good in the C++

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

        Because of this: 

        #ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a)		cerr<<#a<<" : "<<a<<endl;
#else
#define tr(a)    
#endif

        On online judge, the #ifdef PRINTERS condition fails so tr(a) is substituted with a space.

        → Reply