Good day codeforces.

I am currently preparing a problem where a variable must match one of the ten possible values. Once I finished the validator, I noticed that it validates unusually long, about 18 seconds. Meanwhile, my solution only runs in about 2 seconds on my local machine.

After debugging, I found out that the problem is with readToken. I created a simple validator to reproduce the bug:

Validator 1: https://ideone.com/1CZiQW

Validator 2: https://ideone.com/d91Aan

test-case used: https://files.catbox.moe/qb00ce.in (size: 5.2 MB)

What both of them do is read an input file where the first variable (cmd) can be one of ten values (QUERY1 — QUERY10). Their running time differ vastly.

Validator1:

time ./a.out < testcase.in

real    0m16,480s
user    0m16,465s
sys     0m0,009s

Validator2:

time ./a.out < testcase.in

real    0m1,667s
user    0m1,662s
sys     0m0,005s

As we can see, Validator2 is almost ten times faster than validator1. Is there a caveat on readToken() which makes it slow to validate multiple patterns? i tried readToken([A-Z0-9]*) and it gives compatible results to validator2.

Thank you for your time, and have a nice day :)

Edit: im also wondering. 1.6 s just to read input is a bit slow for C++, no? Is there anything else that can be improved here?

Hi everyone, sorry for the considerable delay. It turns out, we were exhausted yesterday from supervising two contests back-to-back. We are surprised by the number of participants in the online mirror. And I hope you enjoy the problems :)

Our big surprise was problem B. We were setting it to be a medium problem. Turns out, maybe the observation is not that obvious.

fun fact: Initially, we don't plan to have any particular naming theme other than the obligatory first letter matches the problem order. However, when naming 6 out of 9 problems, one of my committee member noticed that 5 problems have A of B theme. So, we decided to continue using this theme.

Here are the authors and first solvers for all problems:

A — Arena of Greed

Author: JulianFernando

Expected difficulty: Medium

Tag: greedy

First solver: kotamanegi

B — Blue and Red of Our Faculty!

Author: dewa251202, hiddentesla

Expected difficulty: Medium-hard

Tag: dynamic programming

First solver: team NeedHelpPls: MiricaMatei, AlexLuchianov, loan

C — Captain of Knights

Author: AMnu

Expected difficulty: Very hard

Tag: math

First solver: team Extra Registration: LJC00118, xay5421, Sulfox

D — Danger of Mad Snakes

Author: hiddentesla

Expected difficulty: medium

Tag: Inclusion-exclusion, DP prefix sum.

First solver: team hsy-DD: Yukikaze_, Fuyuki, xzx34

E — Excitation of Atoms

Author: hiddentesla

Expected difficulty: easy-medium

tag: Adhoc, casework.

First solver: jiangly

F — Flamingoes of Mystery

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: Team LCA on Cactus: tem_shett, Dart-Xeyter, sevlll777

H — Huge Boxes of Animal Toys

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: idea guy, snake wrangler, and deep learner: oof_ouch_owie, tenth, WolfBlue.

I — Impressive Harvest of The Orchad

Author: hocky, hiddentesla

Expected Difficulty: Hard

Tags: SQRT algorithms, Segment tree beats.

First solver: IIT Patna: ravik1, Sixpathsguy, darklight13

Code: 94148836

$$$O(N^2 \sqrt{N})$$$ code: 94149019

$$$O(N^2)$$$ code: 94149066

code: 94149150

code: 94149327

code: 93947185

code: 94151055

code: 94151563

Code (without lazy propagation): 94152055

Code (with lazy propagation): 94152123

Honorable mention: the fastest $$$O(NQ)$$$ solution during the contest: 93941953

About problem G

Problem G was really saddening. We had a cool solution using convex hulls. The solution idea is for we find all connected components of "#". For each CC, we push to a set all non-"#" squares connected in the top, right, left, and down of each '#' and then build a \textbf{convex hull} from the set. The convex hull is then marked the safe zone. If the thief can reach one of these safe zones, the answer is "lolos".

However, after the contest, one participant found the counter case on solutions like this:

5 5
M....
.....
..#..
...C.
.....

The distance from the thief to each safe zone is not less than Mr. Chanek. However, the thief can move to bottom-right, which can then react to Mr. Chanek's next move. (output is "lolos", jury will print "tertangkap").

We are sad and are currently finding the correct answer. We have also taken down the problem (for now). We manually verify every test case during the test generation of this problem, so they are correct. During the contest (official and mirror), nobody managed to pass the test cases (except jiangly), so it does not affect the standings. However, broken is still broken. We hope it does not reduce the enjoyment of the other problems that much :(.

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.

• Our testers: AMnu, stevenwjy, Yehezkiel

• 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!

1. Extra Registration (LJC00118, xay5421, Sulfox)

2. jiangly

3. Bajetii (theodor.moroianu, freak93, bicsi)

4. 未来ガジェット研究所 (wasa855, frame233, memset0c)

5. QAQAutoMaton

6. wlzhouzhuan

7. 2016wudi fan club (ChthollyNotaSeniorious, leukocyte, Cirno_9baka)

8. wucstdio

9. Sugar_fan

10. Teams Are For The Weak (IceKnight1093)

Hello, currently i struggle with output only task. I usually can only come up with the most brute force solution. Is there any tips to deal with these kinds of problem?

here is a (shortened) question from one of my old national olympiad

given N and K and an array of N integers 1 and 10^6 inclusive.

partition the array into exactly K subarrays and calculate their sum. find the minimum possible difference of the maximum sum and the minimum sum.

(1<k<=n<=40)

for example for N=6 and K=3 and array={5 1 1 1 3 2}

the optimal way is to split it into [5][1 1 1][3 2] so the maximum sum is 5, minimum sum is 3 so the answer is 5-3=2.

i think the right step is to use prefix sum so pref[i] -> sum of element from 1..i

i thought about DP[pos][k][lmin][rmin][lmax][rmax] where it means the answer for subarray 1..pos where we already made k subarray and the subarray with minimum sum is in lmin..rmin and the subarray with maximum sum is in lmax..rmax. transition is O(n) so the complexity is O(n^7)

i also have an idea of fixing Lmin,Rmin,Lmax,Rmax (O(n^4)) and find if we can get K-2 subarrays from the remaining elements with the sum between (pref[Rmin]-pref[Lmin-1]) and (pref[Rmax] — pref[Lmax-1]). but i need an O(n) way to do that but it seems i cant find one (think about a greedy strategy which moves from left to right and increase cnt whent the current sum is >=min and reset sum to 0. but it does not work the cnt>k because its not certain that we can split something and keep the sum>=mn

so can i have some hints for this problem?

problem:

given at most 400 values of C. for each C,find an integer X (X<=10^18) such that 2^x mod (10^9 + 7) = c

i know that a value x must exist (X<10^9 + 7).but finding X is a problem for me. is there an efficient way to find x?

i have ben thinking about this problem for a few weeks now, here is the problem:

given a grid of size n x n and T ammount of starting and ending positions in the grid, for each position determine if its possible to start from the starting position, visit all vertex in the grid exactly once, and finish in the finishing position

for example: n=4, t=3 start=(1,1), end=(4,4)

start=(1,1), end=(3,2)

start=(1,2) end=(2,1)

answer shound be yes,yes,no

(N<=10), (T<=20)

how to solve this problem? i could only think of pruned recursive backtracking (if the current vertex is pos, next vertex we visit is x, check if the degree of adjacent unvisited vertex (other then x), and reduce them by 1, if any of them is less then 2 (less then 1 for target vertex), then we cannot visit x next).

after about 6 months sway USACO, i decided to continue my USACO training page, and i have ben stuck in the problem "camelot" for a full day now!, here is the problem description : https://www.scribd.com/document/124295413/USACO-Training-Pages-Camelot my idea is calculating the minimum moves needed to gather at all the squares, but for the king that is hard, because we dont know when will the king get picked up.

can i have a small hint for this problem?

so im learning Euler circuit now, and i found this algorithm

'tour' is a stack

find_tour(u):
	for each edge e=(u,v) in E:
		remove e from E
		find_tour(v)
	prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

source: http://www.algorithmist.com/index.php/Euler_tour

i coded it, and got AC in an euler circuit problem (the problem guarantees that there is an euler circuit) however, i noticed that in the bottom of the algorithm, it says [WARNING! There is some error in this pseudo-code. The algorithm is not correct!]

does this mean that the algo has a high chance to print euler circuit? or something else?

http://www.spoj.com/problems/NPC2015E/ it looks like a normal egg dropping problem, but the constraints of the last subtask is really huge. here are some observations i made:

1. if (k=2) answer is the smallest x where x*(x+1) >= 2*n

2. if (k=1) answer is n

3. if(k>= log2(n)) answer is floor(log2(n)) (because we can do binary search)

however, using these three observations, its still not enough to beat the last subtask, because if the input is 10e18 and 5, it would be TLE

is there a faster solution? i tried googling and found a math solution for 2 eggs only

hello!, about a while back, i came across a problem called "building fences", link: https://open.kattis.com/problems/fence2, back then i cant solve it, and yesterday i remembered about that problem and attemp to solve it again, but still, i could not solve it. im thinking about binary searching the length of the log, to find the the highest log length (ill denote it L) that we can make, but then i noticed that if the log length is divisible by L, the number of cuts to get the logs to size L is log_length/L -1, and if its not divisible by L, the number is log_length/L. so while that binary search may return the largest L, it may not be the minimum cut, right?

so can anyone give me some hints on this problem? could this just be a simple problem and i have ben looking at it the wrong way?

the problem: http://jollybeeoj.com/problem/view/255

i tried all i can, but i can only think of preprocessing and save it in a string, then output the questions in O(1), but sadly, i cant because its memory limit exceeded, is there a math based approach?

problem link: https://open.kattis.com/problems/suma

so its ben 3 days since im stuck in solving this problem, i solved a similar problem called islands : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=360&page=show_problem&problem=2628

where my idea is do union find from backwards, (i.e start when all the land is flooded, then move time backwards, if for some time a land becomes unfloded, add it as a new single group, then if its neighbours are not flooded, do union() operation with its neighbour)

but in suma that does not apply, because if i work backwards, some trees would not stay "connected" permanently, because at some time, they will be different heights again, and im having troubles coming up with somthing. so can anybody give me some hints to solve this?

so yesterday i just learned the union-find data structure, and i found this problem: https://open.kattis.com/problems/almostunionfind

my approach is as following: implement basic union-find, but also add array sum[] for the sum of the group and freq[], the number for elements in the group

i also "made" the group using a vector of vector, so if there is a group {1,3,5} and 1 is the leader, the representing vector is

{1,3,5} or {1,5,3} (leader is always in the front, other element is random depending on the union, the function of this is for the "2" function, where how i handle it is i first find the "leader" of the group (lets call it indeks i), then the element must be in v[i], so i erase the element from the vector, make the next first element in the vector the leader and adjust the rest of the vector, if the leader of the new vector (lets call it indeks j) is not i, swap it the vector i with vector j clear vector i;

my code: https://ideone.com/vZVvCn

however, im getting WA :( and i tried to debug it but no luck, can someone point out a counter case?

also, if there is a more optimal approach then my approach, please give me hints

problem:

given a block with with bottom corner at (1,1,1) and uppper corner at (P,L,T) (2<=P,L,T<=400), a starting coordinate (x1,y1,z1) and target coordinate (x2,y2,z2)

find the shortest distance needed to get from (x1,y1,z1) to (x2,y2,z2) by only moving in the sides of the block

it is guaranteed that the starting and ending coordinates are located in the sides of the block (meaning atleast one of x,y,z is either 1 or P,L,T)

i know there is a math solution (with lots of if's), but given the constraints, and me wanting to learn something new, i wanted to solve this problem with BFS

so max test is where P=L=T=400, and we needed to get from (1,1,1) to (400,400,400) there should be only 6*400*400 = 960000 states. so my bfs algo is as follows:

//make struct node to save the x,y,z coordinate

queue q; while(!q.empty()) node t=q.front(); q.pop(); if(t is the target coordinate) print how many steps else if(t is not visited yet) visit all neighbours of t

the problem is the part if(t is not visited yet)

im having troubles finding a data structure/method that can save visited coordinates efficiently

i made comparing struct to compare based on x, then y, then z

i tried std::set but it got TLE'd

i also tried std::map<node,bool> but it also got TLE

so im asking, is there a method/data structure that can save visited 3D coordinates?

problem link: http://www.spoj.com/problems/INGRED/ my code: https://ideone.com/H30OGG

so im having troubles with this problem, my approach using dp: first i represent S as a mask, where if the I'th element of mask is on, it means that we have not visited store at city s[i]

firstly run Floyd-Warshall to get all distances between two cities

dp[x][y][mask] = minimum distance needed to get all S ingridients, with person A at city x, person b at city y, and the mask

if person A lives in city A, person B lives in city B, and there are SS ingridients, the answer is dp[A][B][(2^SS) — 1];

so i made recursive function solve(x,y,mask,dist)

x= position of person A, y= position of person B, dist = distance so far

then i just check for each bit that is on in the mask, assign person A or person B to get it..

but i got WA... cant seem to find where i did wrong. any help?

short problem statement:

given N and K (2 <= N,K <= 8) and an array consisting of N distinct elements; in one move you can pick a block of K elements in the array and reverse the order, for example: if N = 5 and K = 3 and the array is [4 5 1 2 3], in one move you can make the array [1 5 4 2 3] or [4 2 1 5 3] or [4 5 3 2 1]. how many minimum number of moves is required to make the array sorted in ascending order?, if impossible, print -1.

i cant give a link to the problem, because its in my native languange's, so i thought of a greedy algorithm:

for each i, find the i'th smallest element and perform BFS until that element is in the i'th position

my implementation: https://ideone.com/3x2vwP

however, it seems that this greedy algorithm do not always work, but im having troubles finding a counter case, can someone provide me one?

note: since the constraints are very low, i did a full frontal BFS and got AC: https://ideone.com/SYJklC . but im still curious...