Perplexed — Codefest'19

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Hi, Codeforces Community!

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

Perplexed is one of the most innovative events of CodeFest, whose target is not only gauge a contestant's coding abilities but also how one tackles different situations and constraints. The problemset will include all mind-boggling coding problems, ranging from code obfuscation to language constraints, character limits etc

The contest will take place at HackerRank. This contest will be an individual event with a duration of 2 hours 30 minutes, from Aug/23/2019 20:00 IST. 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 contest has been prepared by Enigma27, _hiccup, _shanky, hitman623 and me (drastogi21).

UPD1: The contest will start in about an hour.

UPD2: The contest will start in about 15 minutes.

UPD3: The contest has ended.

UPD4: The editorial has been published. You can find the solutions to the problem at HackerRank itself. Feel free to discuss the problems in the comments.

Prizes -

1st Prize-Rs.20000

2nd Prize-Rs.12000

3rd Prize-Rs.8000

1st in India-Rs.6000

1st in IIT(BHU)-Rs.3000

1st in 1/2 year in IIT(BHU)-Rs.1000

UPD: The issue in the checker has been resolved. Following are the winners of the contest. Congrats!

1. .I.

2. Jeffrey

3. dvshah

First place in India: IceKnight1093

500 94 29 66189 158 47716 216 63318 373 62649 1257 35751 1580 45992 1619 76160 1919 48707 2362 34896 2599 84791 2760 87062 3175 17907 3642 94017 3870 40946 3904 73828 4156 56219 4350 97364 4371 57166 5090 99079 5352 28757 5412 67512 6143 50019 7094 13802 7661 31490 7933 17153 8150 1427 8169 36690 8311 53269 8329 9399 8418 35946 8527 53380 8776 85381 9363 95365 9533 36818 10776 30301 11105 86949 11316 50410 11672 43020 11757 95088 12497 97110 12532 15440 12741 42193 13172 85733 13309 68837 13368 9940 13614 16294 13870 73995 14120 86240 14217 34658 15089 60450 15464 66189 16110 13793 16646 35838 16836 49512 16931 33242 17065 20930 17259 77820 17390 14025 17466 43222 17958 41608 18519 58624 18945 56242 19107 23016 19673 56927 19729 58112 20215 87758 20269 68776 20277 40164 20446 64825 20516 43105 20591 47277 20592 47274 20592 47275 20592 47277 20592 47279 20592 47280 20593 47273 20593 47274 20593 47275 20593 47276 20593 47277 20593 47278 20593 47279 20593 47280 20593 47281 20594 47274 20594 47276 20594 47277 20594 47278 20594 47279 20594 47280 20595 47273 20595 47274 20595 47275 20595 47276 20595 47277 20595 47278 20595 47279 20595 47281 20596 47273 20596 47274 20596 47279 20596 47280 20596 47281 20596 47282 20597 47274 20597 47275 20597 47276 20597 47277 20597 47278 20597 47280 20597 47281 20598 47273 20598 47274 20598 47276 20598 47277 20598 47279 20598 47280 20598 47281 20599 47274 20599 47275 20599 47276 20599 47278 20599 47279 20599 47280 20599 47281 20600 47276 20600 47277 20600 47278 20600 47279 20600 47280 20601 47277 20705 55197 20847 3909 22532 3506 22787 29190 22932 69099 23520 50784 23813 90730 23869 70924 24565 28797 25022 41929 25688 10840 25868 36666 25981 70849 26440 29479 26537 4707 26934 48044 27097 69627 27278 36287 27289 65335 27431 9151 27787 98805 28056 39693 28063 35397 28243 60103 28376 36672 28377 36670 28377 36671 28377 36672 28377 36673 28377 36674 28378 36670 28378 36671 28378 36674 28379 36669 28379 36670 28379 36671 28379 36672 28379 36674 28380 36670 28380 36673 28380 36674 28381 36670 28381 36671 28381 36672 28381 36674 28382 36672 29136 30502 29982 68421 30416 37204 30444 20801 31627 17187 31973 64484 32276 77849 32372 12939 32924 58209 33042 95690 33563 91401 33601 62007 33910 70730 33933 15275 34271 63897 34275 29262 34485 33212 36709 83203 37149 83502 37454 39745 37758 65534 37955 61403 38268 80771 38453 31420 39050 55373 39188 91989 39596 45585 39897 90471 40071 44913 40422 47795 41234 43234 41628 79755 42127 93262 42922 81375 43250 41375 43992 71192 44394 73990 45063 15337 45441 28703 45731 26730 46090 63087 46350 73545 46579 48561 47963 79564 49531 30431 49900 42505 49961 56425 50282 29477 50483 86535 50534 27651 50714 13131 51112 67321 51246 60232 51390 57063 51710 96678 51819 50428 52008 45810 52057 26055 53845 30687 54216 54215 54766 58046 54915 59176 55311 32536 55485 92304 55840 68419 56052 91615 56200 65142 56252 41950 56343 23348 56879 96431 57117 21001 57473 56254 57548 79035 57645 68041 57699 35285 57734 22033 57997 21037 58525 44403 58526 44401 58526 44402 58526 44403 58526 44404 58526 44405 58527 44401 58527 44402 58527 44404 58527 44405 58528 44400 58528 44401 58528 44403 58528 44404 58528 44405 58529 44401 58529 44404 58529 44405 58530 44402 58530 44403 58530 44405 58531 44403 58592 72720 58915 82523 59076 65731 60077 2150 61173 26848 61340 74070 61373 34963 62161 68322 62325 48536 62924 55651 62951 28360 63336 15585 63725 26321 63726 68121 63873 70748 64265 72982 64473 14964 64512 13188 64529 78771 64969 56259 65095 96563 65227 16434 65726 48588 65889 85577 66087 71482 66307 33798 66308 33796 66308 33797 66308 33798 66308 33799 66308 33800 66309 33795 66309 33796 66309 33797 66309 33798 66309 33799 66309 33800 66309 33801 66310 33795 66310 33796 66310 33797 66310 33798 66310 33801 66311 33795 66311 33796 66311 33797 66311 33798 66311 33799 66311 33802 66311 72162 66312 33795 66312 33796 66312 33797 66312 33799 66312 33800 66312 33801 66313 33795 66313 33796 66313 33797 66313 33799 66313 33800 66313 33801 66314 33796 66314 33797 66314 33798 66314 33799 66488 86053 66943 48983 66952 49690 66989 57036 67720 3631 67767 44301 67805 37556 67882 41313 68364 14219 68440 27990 68507 15834 68779 77947 68870 76491 69313 23050 70015 14394 70083 77580 70680 50061 70984 6966 71475 72312 71727 84595 72371 4108 72454 21627 72540 32595 72613 41606 72667 41221 72829 18152 72861 42155 72906 51055 73064 70025 73826 90572 74465 37180 74488 71061 75196 46959 75314 73771 75546 4077 76611 87033 77569 23712 77653 87869 77728 94624 77934 32358 78241 35643 78369 33350 79046 83925 79111 24754 79247 79039 79703 67278 80925 30248 81054 86478 81175 30524 82780 30294 83031 60940 83172 64695 83444 71222 83816 24504 83922 94831 84268 99084 84385 5883 84642 71012 86238 35118 86904 35211 87942 37607 88534 84268 88569 59824 88703 60936 89116 2185 89163 53381 89246 45910 89334 880 89607 79084 89630 76641 89973 14066 90219 7365 90390 92708 90442 23193 90443 23190 90443 23191 90443 23192 90443 23193 90443 23194 90443 23196 90444 23189 90444 23190 90444 23191 90444 23192 90444 23193 90444 23195 90444 23197 90445 23189 90445 23190 90445 23193 90445 23195 90446 23189 90446 23191 90446 23192 90446 23194 90446 23195 90446 23197 90447 23188 90447 23190 90447 23193 90447 23194 90447 23195 90447 23196 90447 23197 90448 23190 90448 23191 90448 23192 90448 23194 90448 23195 90448 23197 90449 23189 90449 23190 90449 23191 90449 23192 90449 23193 90449 23194 90449 23195 90449 23196 90449 23197 90450 23189 90450 23190 90450 23191 90450 23193 90450 23194 90450 23195 90450 23196 90450 23197 90451 23190 90451 23191 90451 23192 90451 23193 90451 23194 90451 23195 90451 23196 90452 23193 91967 1750 92453 65295 92755 10697 92949 28161 93093 23965 93808 97888 95059 35468 95074 88824 95749 1636 96003 54719 96344 57572 96466 4766 96975 17317 97991 87144 98450 33655 98817 27822 99010 44655 99081 5866 99084 3814 99198 51802 99644 6751 99907 77090

//vpll p; //ll f(ll i, ll j){ // return (p[i].X-p[j].X)*(p[i].X-p[j].X)+(p[i].Y-p[j].Y)*(p[i].Y-p[j].Y); //} //vvl ans; //void solve(vpll p){ // ll min_x = MOD, max_x = -MOD; // ll min_y = MOD, max_y = -MOD; // for(auto _ : p){ // min_x = min(min_x,_.X); // min_y = min(min_y,_.Y); // max_x = max(max_x,_.X); // max_y = max(max_y,_.Y); // } // ll cx = (max_x + min_x)/2; // ll cy = (max_y + min_y)/2; // ll bound = 0; // for(auto _ : p){ // ll tp = (_.X-cx)*(_.X-cx)+(_.Y-cy)*(_.Y-cy); // bound = max(bound,tp); // } // ll lo = 0, hi = 1000000, mid; // while(lo < hi){ // mid = (lo+hi)/2; // if(mid*mid >= bound) // hi = mid; // else // lo = mid+1; // } // assert(lo*lo >= bound); // ans.pb({cx,cy,2*lo+1}); //} //void _(){ // int n,k; // cin >> n >> k; // p.resize(n); // cin >> p; // vvl edges; // rep(i,0,n-1) // rep(j,i+1,n-1) // edges.pb({f(i,j),i,j}); // sort(all(edges)); // DSU dsu(n); // int more = n-k; // for(auto _ : edges){ // if(dsu.unite(_[1],_[2])){ // --more; // if(more == 0) // break; // } // } // map<int,vpll> pts; // rep(i,0,n-1) // pts[dsu.getpar(i)].pb(p[i]); // for(auto _ : pts) // solve(_.Y); // print(sz(ans)); // print(ans,"\n"); //} // #include <map> #include <numeric> #include <iomanip> #include <algorithm> #include <cassert> #include <vector> #include <utility> #include <iostream> #include <string> #define pb push_back #define REP_INT(i,l,r) for(int i = l; i <= r; ++i) #define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME #define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT)(__VA_ARGS__) #define all(v) (v).begin(), (v).end() #define sz(v) ll(v.size()) #define X first #define Y second #define T1 template<typename T> static using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef vector<int> vi; const ll MOD = 1e9 + 7; T1 ostream& operator<<(ostream& stream, const vector<T>& t); template <typename F, typename S> static istream& operator>>(istream& stream, pair<F, S>& t){ return stream >> t.first >> t.second; } T1 istream& read(T, T, istream& = cin); T1 istream& operator>>(istream& stream, vector<T>& t){ return read(all(t), stream); } T1 istream& read(T b, T e, istream& stream){ for(T it = b; it != e; ++it) stream >> *it; return stream; } struct DSU{ vi par; int n; DSU(int _n):n(_n){ par.resize(n + 1); iota(all(par), 0); } int getpar(int u){ if(par[par[u]] == par[u]) return par[u]; return par[u] = getpar(par[u]); } bool unite(int u, int v){ u = getpar(u); v = getpar(v); if(u == v) return false; par[u] = v; return true; } }; T1 void print(T x, string end = "\n"){ cout << x << end; } T1 ostream& print(T b, T e, string sep = " ", ostream& stream = cout){ for(T it = b; it != e; ++it){ stream << *it; if(it + 1 != e) stream << sep; } return stream; } T1 ostream& operator<<(ostream& stream, const vector<T>& t){ for(int i = 0; i < sz(t); ++i){ stream << t[i]; if(i+1 < sz(t)) stream << ' '; } return stream; } T1 void print(vector<T> arr, string sep = " "){ if(arr.empty()){ return; } print(arr.begin(), arr.end(), sep); cout << '\n'; } vpll p; ll f(ll i, ll j){ return (p[i].X-p[j].X)*(p[i].X-p[j].X)+(p[i].Y-p[j].Y)*(p[i].Y-p[j].Y); } vvl ans; void solve(vpll p){ ll min_x = MOD, max_x = -MOD; ll min_y = MOD, max_y = -MOD; for(auto _ : p){ min_x = min(min_x,_.X); min_y = min(min_y,_.Y); max_x = max(max_x,_.X); max_y = max(max_y,_.Y); } ll cx = (max_x + min_x)/2; ll cy = (max_y + min_y)/2; ll bound = 0; for(auto _ : p){ ll tp = (_.X-cx)*(_.X-cx)+(_.Y-cy)*(_.Y-cy); bound = max(bound,tp); } ll lo = 0, hi = 1000000, mid; while(lo < hi){ mid = (lo+hi)/2; if(mid*mid >= bound) hi = mid; else lo = mid+1; } assert(lo*lo >= bound); ans.pb({cx,cy,2*lo+1}); } void _(){ int n,k; cin >> n >> k; p.resize(n); cin >> p; vvl edges; rep(i,0,n-1) rep(j,i+1,n-1) edges.pb({f(i,j),i,j}); sort(all(edges)); DSU dsu(n); int more = n-k; for(auto _ : edges){ if(dsu.unite(_[1],_[2])){ --more; if(more == 0) break; } } map<int,vpll> pts; rep(i,0,n-1) pts[dsu.getpar(i)].pb(p[i]); for(auto _ : pts) solve(_.Y); print(sz(ans)); print(ans,"\n"); } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); _(); }

Comments (28)

Show archived | Write comment?

demoralizer

5 years ago, # |

-16

Really excited about the contest... Haven't done much constrained programming before, so will be a great experience for me.

→ Reply

sspm

Excited for the contest!!

neeraj_alavelli1729

+14

Can't wait for the contest!!

ILoveCodingNinja

Is this contest an April Fool type Contest?

drastogi21

5 years ago, # ^ |

+28

Not exactly, there are algorithmic and other types of problems too: surprise language, codegolf, hack the code etc.

+13

Thanks for Clarification

Ra16bit

+19

Why this contest is not listed at https://www.hackerrank.com/contests ?

bertrandovide

← Rev. 2 →

That is true I was also suprised. But the given link works. Maybe they have thier reasons about that.

ashishkr23438

+49

Since it's a college contest (by IIT (BHU) Varanasi), so it is listed at https://www.hackerrank.com/contests/college. Also, you'll find two other contests — Mathmania and CTF in that link, which are also conducted as a part of Codefest'19 by the Department of Computer Science and Engineering, IIT(BHU), Varanasi.

solvemproblr

+11

Is it rated?

No, it is an unrated contest.

spam_123

Can you post previous contest links ?

Perplexed '18

Perplexed '17

siddhi

how to solve Odd-One-Out ? I tried 1-2-3-1-3-2-1-2-3-2-1-3 pattern of increments in with seed value of 1 but was able to get only 20 for it

datte

Check pattern on OEIS

Thanks

+18

I got top 3 rank in contest....when will prizes be distributed?

How to solve B (the balls one) ?

Think about output of the following... 2 4 4

How did you reach at this test case ?

I was considering min priority case

Sorry, but isn't the answer 4 only ?

+23

It was a fun contest....had fun solving problems...very good job by Rastogi ji

bhatnagar.mradul

I really hope there are more contests with similar theme

.I.

Help: why is my answer wrong in Minimal Cover? First test case for example:

Test case #0:

My output:

94
201 64419 3559
1809 35323 1399
2679 85926 2279
3870 40946 1
2761 74994 3267
4263 56692 975
4366 96548 5267
5412 67512 1
8150 1427 1
5752 13653 9949
8064 32787 9717
5737 49686 11835
10930 96099 3731
12206 42606 1353
13870 73995 1
11448 86165 5571
14386 67513 3417
15574 34540 3757
17259 77820 1
14961 13117 7111
18086 21973 2921
17897 57823 7693
22014 89244 4669
24139 7173 9273
27787 98805 1
28243 60103 1
25961 29649 6577
23626 43090 18693
32276 77849 1
33302 93545 4323
29112 64566 19591
32188 16870 8603
37454 39745 1
36364 31237 5751
39050 55373 1
40657 91866 4057
39815 81628 6967
41423 44585 7389
45063 15337 1
46090 63087 1
45171 72591 3661
46579 48561 1
47963 79564 1
50483 86535 1
50714 13131 1
51112 67321 1
51710 96678 1
53686 51368 19277
56182 94023 5015
57170 22174 2875
57391 43177 3351
58231 80779 3749
60077 2150 1
53407 30670 18101
62449 27340 3267
65095 96563 1
61075 69606 13223
66188 85815 767
64956 56343 4297
68440 27990 1
67306 77631 6005
71727 84595 1
72540 32595 1
68082 18119 12177
73394 71898 5367
71633 5298 8509
77728 94624 1
79247 79039 1
77440 87248 9823
72552 40651 29115
81437 64109 7227
80692 24233 6335
84095 96957 4271
84385 5883 1
84043 71117 1219
87090 36362 3019
88534 84268 1
88636 60380 1123
89163 53381 1
89246 45910 1
89618 77862 2447
90390 92708 1
92453 65295 1
91364 10715 7259
91767 25674 5633
93808 97888 1
96975 17317 1
96532 87984 3369
96754 34561 3847
98817 27822 1
99010 44655 1
94380 3815 12057
97600 54687 6599
99907 77090 1

My code (last submission during contest time):

And a tester I wrote (that doesn't find the mistake):

Tester

points, circles = [], []
with open('mysol.in') as f:
    n,k = [int(x) for x in f.readline().split()]
    for i in range(n):
        points.append([int(x) for x in f.readline().split()])
with open('mysol.out') as f:
    nr_circles = int(f.readline())
    for i in range(nr_circles):
        circles.append([int(x) for x in f.readline().split()])
    assert(nr_circles <= k)
for point in points:
    solved = False
    for circle in circles:
        assert(abs(circle[0]) <= 10**5)
        assert(abs(circle[1]) <= 10**5)
        assert(1 <= circle[2] and circle[2] <= 1000000)
        if (point[0]-circle[0])**2+(point[1]-circle[1])**2 <= circle[2]**2:
            solved = True
    assert(solved)
print('All points covered?! What am I missing, then?')

gaand_faad_coder_

Their tester had a bug, this is a result of noobs setting problems

But does it still have a bug?

When I submit the code again I still reach the same results:

1) WA on HR, because "All points are not inside circles."

2) But when I run my code on those inputs and check, all points do seem to be inside circles.

Also found another much less severe bug: the constraint 1 <= r_i <= 1e6 doesn't seem to be enforced at all — my wrong solution that prints both 0 radius and huge radius circles passes all cases...

drastogi21's blog