Hello Codeforces Community. I would like to invite you all for ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror. I am the Person In Charge of the event.
I want to thank:
Faculty of Computer Science, The University of Indonesia, for providing guidance and support for the official event.
Our committee: hocky, JulianFernando, faustaadp, dewa251202, Defy_AK12, faishol27.
MikeMirzayanov: for giving us the opportunity to host this online mirror. Also, for Codeforces and Polygon platform.
The online mirror will be held on , 3 hours after the official contest starts. Teams are allowed. The duration of the contest is 5 hours. For the official contestants, please refrain from joining this mirror contest.
Our problems are relatively easier than ICPC regional contests. However, we promise an interesting and diverse problem set. I'd say the overall difficulty is slightly more challenging than div two rounds. There might be an interactive problem. So make sure to familiarize yourself
About COMPFEST: COMPFEST is an annual event hosted by the University of Indonesia. It is the largest student-run IT event in Indonesia, and Competitive Programming Contest (CPC COMPFEST) is one of the competitions hosted.
Our contest on regional finder
Note: this contest is unrated.
UPD1: Editorial and contest review will be posted in a few hours, after we finish the official contest duty.
UPD2: Editorial is available here
Congratulations to the winners!
Bajetii (theodor.moroianu, freak93, bicsi)
2016wudi fan club (ChthollyNotaSeniorious, leukocyte, Cirno_9baka)
Teams Are For The Weak (IceKnight1093)
can I participate without team?
Yes, you can!
How many members in a team are allowed?
Maximum of three members is allowed (ICPC rules)
rip im 20 years too late
whoops! sorry about that. It's fixed now.
(effects of writing at 2 AM)
Isn't it a bit unfair to post the announcement and then delay the round by 20 years?
Isn't it a bit unfair that without contributing much to the community, you are 2nd top contributor.
What do you mean? This is a quality post right here
white is sus
here link is wrong.
Will there be any editorial for this contest?
Thanks
Yes!
I am eager to participate !!
How do you participate as a team?? could anyone walk me through the process it's my first time participating as a team.
go to ur profile , in tag "team" create ur team, invite ur teamates, when register choose "as a team member" instead of "as individual participant"
Will we be able to see the live standings?
yes, assume it's like a normal ICPC contest
th level?
As a whole it is slightly harder than div 2. However there are some hard problems :O
oh wait, i'm getting the vibes you're asking something else ._.
Tesla level 8. My guess TH10?
Yup, that's correct
Have a feeling that this contest would be pretty interesting!
Also great to see "There might be an interactive problem. So make sure to familiarize yourself" such notification before the contest. I was clueless when I first saw an interactive problem a couple of contests back.
Will problems be sorted depending on the difficulty like normal CF rounds?
No, the problems are not sorted by difficulty
How many question will be set on the dashboard?
Will this year's INC be running a mirror on CF as well?
Nvm it'll be great :)
:)
CAN I USE C++ THIS CONTEST??
Yes, all languages is allowed
Are contestants allowed to copy-paste code from their library or search things on the Internet during the contest?
Sure! it's unrated, anyway. glhf
will there be any rewards for the toppers of this contest?
bragging rights :(
will tutorial be available after contest??
Неответственно обвинять других в своих ошибках, так что, пожалуйста, верните мне мой рейтинг.
why chinese write on russian under english blog about indonesian contest?
Nice problemset! Enjoyed a lot!
How to solve E :|
Consider 3 cases
for all i ans=max(ans,range_sum_a(i,n)-d[i]);
Connect the minium di with the first atom . and connect (i-1) with (i+1); ans= (sum of all a )- min(d);
you have to trickiliy do some random operation to turn k>2 in k==2
Now the graph can be a Cycle + a bamboo tree or a tree .try by yourself
Any edge cases for test case 19 in D??
Its
You can get 7 by only exciting the last atom
I think the question is problem D, not E
Sorry i misread the question. In D there are no edge cases (that we intend to). Maybe check your formula
Okay. thanks for the reply..
I found the mistake the range of n was 2000 and coordinates was 1000 I took both array of size 1000 :(
sed_lif
We will release the editorial and contest review in a few hours. right now we are so tired from nonstop supervision of contests. Sorry about the unexpected difficulty jump :( we intended B to be a medium dynamic programming problem.
hiddentesla Can we participate in the contest virtually?
yeah. just try it
It says that I am not allowed to view the contest.
UPD: I can register for virtual now, thanks!
Now contest is over,but why can't I read the problems?
Sorry about that. We just updated the settings. We disallowed before just to prevent the official contestants from registering
In Problem B, I think it's not very nice to mention "every checkpoint except checkpoint 1 has exactly two routes connecting it" only in the input section , since it is quite important leading to the solution :(
BTW I've spent about an hour to write&debug my B but in vain :(
How to solve I?
Oh, I thought the editorial wouldn't be published. I'll read it :).
Arrange the nodes in dfs order so that subtrees correspond to subarrays, and then simply answer each query in O(n). Runs in 3.2s without pragmas or fast i/o, and 900ms with them: Code
Using the ternary operator is apparently important because I TLE'd when I used an if condition instead, probably some stuff going on with branch prediction which I really don't know about.
I'm sure this wasn't intended, but I don't know if it can be made to TLE within the limits of the problem.
The intended solution uses segment tree beats. We tried our best O(NQ) solution before and our fastest only got 13s. Pretty suprised we are still far away from constant optimization. Please wait for the editorial for the detailed explanation
With $$$N = 50000$$$ and 7 seconds, it's hard to imagine quadratic solutions to not pass, with some minor tricks (our solution also runs in under 1s with pragmas). Was the official complexity $$$O(Q \sqrt{Q} \cdot Beats(N))$$$?
$$$ Q \sqrt{Q} log (N)$$$ was the intended complexity. Yeah we are quite suprised. One solution NQ solution even manage to pass in less than 1 second sobs
Is it in time!? I was trying to make a solution better than O(NQ).
Thank you!
yeah our intended solution runs at 4.000 s. However some NQ solutions run less than 1 s.
oof
Weak tests for problem G XD
My program outputs
lolosfor case :Behind the scenes: generating test cases for problem G was so hellish, that its easier to generate testcases by hand rather than using a generator program. First 25 test cases was hand made.
Bad move, now they removed the problem from your standings.
When or where will the editorial be published for this contest?
In a few hours, along with the contest review. Currently we are still doing stuff for the official contest (closing ceremony and all)
Sure thanks a lot hiddentesla
problem C
detected an integer overflow error at the 154th line of the problem setter's submission:
Kcan be up to $$${10}^9$$$ so3*Kwill cause overflowYeah, all of our testers used the same formula. So sorry for this. All of the submissions for C is rejudged. Only 1 participant in contest is affected.
Thank you!
how to solve D?
Is there any solution?
Yes
Where can I find the editorial ?
Sorry for the delay. Editorial is up (see announcement)
Ok I get it. Appreciating your help !
Can someone help me find bug in my solution for Question D? During contest, I got wrong answer on test case 9. I tried upsolving later but couldn't find the bug.
Link to the submission : https://codeforces.net/contest/1425/submission/93937461
General Idea : So the idea is to count the total number of strategies in which a & b both occur together. Let's assume they occur in X number of different strategies. Then we can add X * (2ab) to our answer (calculating a^2 is trivial and can be handled separately). Now in order to calculate X, we can consider the bounding box for a & b and then count the number of snakes in their intersection, union, and rest and can use combinatorics to calculate the answer. Please refer the code.
Can someone please explain the bug in my code?
Hi, you might want to check your logic on getIntersection. Here is a small testcase that might help:
Answer should be 1400.