Hello Codeforces,
I would like to invite you all to participate in the 2019 JUST Programming Contest of Jordan University of Science and Technology. The contest was originally held on $$$23^{rd}$$$ of March, and it will launch in Codeforces Gym on Friday, 29 March 2019, 13:00 UTC.
The problems were prepared by justHusam (Husam Musleh), Aristos (Hamzeh Sahyoun), Lvitsa (Alaa Abu Hantash), H2A_TLE (Asem Al-Radaideh), and Thunder_r (Bara' Al-jawarnEh).
Thanks to Mockingjay (Sarah Abu Elayyan) for testing the problem set.
The duration of the contest is $$$4$$$ hours, and the registration will be open $$$6$$$ hours before the start of the contest.
Good luck to everyone, and I wish you all accepted solutions!
Update: Registration is now open.
Update: The contest has ended. Congratulations to all participants!
You can check the scoreboard of the onsite contest on the following link.
JUST already did it. You should be Jordanian to understand how XD.
How to solve A and L?
For L , the problem is very similar to IOI 2010 Quality of living , you can see here my solution to it and with explanation , don't forget to use scanf and printf because normal input and output will make TLE.
A: you may have already noticed this is a graph problem, with the cards being edges, and the nodes containing a character.
For every non-bridge edges in the graph, change their weight to 0 (since we can just wand them instead). Build a minimum spanning tree over these edges. Root this tree anywhere you like. Now for each A/H character in the tree you'd want to "lift" them up, moving them closer to the root, until they meet their counterpart character.
Can anyone tell why we need dp in D? Where greedy solution fails? I am not able to find case where it fails? Code
Check this test case:
Your code output is "1111111100", while the correct answer is "1111111111".
Can you share the approach to solve D?? I tried solving Greedily but getting WA.
Try every permutation of the first two strings, then you can greedily match the 3rd
My intitial solution was the same as you mentioned. But after a rough calculation I thought it will not fit in time limit. As it's time complexity will be roughly O(T * 252 * 252 * 10); As maximum permutation of a string will be max 252 (i.e. five zero's and five one's).
Example :
T = 250
for every T all the three strings be same
1111100000.
Not very surprising :)
The 1e8/1s bound is a simple approximation. As long as you don't do anything too costly, it should pass smoothly. I used that approach and passed in 233ms. In one problem I did O(M*2^N) for N = 19, M = 5000 and it passed in 2.3s
I suppose it comes down to optimization skill and confidence for one particular problem.
Mine too got an AC in 265ms. But if we consider the test case i mentioned above i don't think that our solution will work on it within given TL.
You have a point.
My code runs on 1500ms for your case :) looks like I found an unintended solution.
can you check this code please for problem D
Actually you only need to try all permutations of the second string, first one can be fixed (or vice versa) and then greedily match from the third. The complexity is now around $$$O(T * 252 * 10)$$$ and my accepted code runs in 15ms.
Hi there, can anyone help me find a counter case for problem D code I tried a lot of cases but it seems to work, I cannot find a counter case
Check this test case:
Your code output is "1111111100", while the correct answer is "1111111111".
How to solve C — Large GCD?
this is a trick question , can be solved in O(1)
Actually we had to print some output by bruteforce solution, then we would observe that output is always 2 or 12.
Spoiler
Any editorial for this contest?
How to solve K?
Lets fix the left barrier of the subarray. A key insight in this case is to note that we can't get more than log_a different results as we keep expanding to the right. Why? The OR result is always non-decreasing. Either it stays the same, or one or more bits get turned on. So, every different result turns on at least one new bit, but we only have log_a bits, so the possibilities are limited to this number.
Having this insight, for every left barrier i ( from 1 to N ) we can do the following. Start with a range [i,i]. Insert the OR of the range to a set. Then, as long as we can keep expanding our right barrier, binary search the closest right barrier that increases the OR of the range. When we find it, insert the OR of the new range and repeat. Stop when we can't find a new OR.
We will try N different left barriers, and in each one we will make at most log_a binary searches. To calculate the OR of a range quickly we can use a sparse table. This would give us a complexity of N*lgN*lgA that fits perfectly in time.
Any tips for problem k?
https://ide.geeksforgeeks.org/qorNuMmBI1 link to code for k
Wow! Can you explain why this works?
Any tips for H and I?