Today at 11:00 AM EST takes place SRM #608.
By the coincidence it overlaps with the opening ceremony of Winter Olympic Games in Sochi.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Find user
→ Recent actions
Round starts in 10 minutes.
Seems like everybody related to the event already knows, but anyway I'll remind.
Facebook Hacker Cup Round 3 is happening today at 1:00 PM PT. Top-25 coolhackers will continue to Final Round.
Hello!
Does anyone have test data for BOI 2012? Links on official site are broken :-(
Also I didn't find any contacts there. Maybe somebody has e-mail, or any contact of jury of that olympiad?
UPD: there can be some type of misunderstanding. I mean Baltic Olympiad in Informatics, not Balkan.
Hi everyone! I wan't to share some interesting fact about how we're going to challenge almost every solution, that uses polynomial hashes modulo 2^64. We'll hack any solution, regardless of it's base (!), the only thing we need, that it's using int64 with overflows — like many coders write hashing.
Keywords: Only today, only for you, ladies and gentlemen: we're gonna challenge Petr's solution in problem 7D - Palindrome Degree from Codeforces Beta Round #7!
Is it interesting? Welcome reading after the cut.
Tomorrow in Hungary starts CEOI 2012 — Central-European Olympiad in Informatics. It's very interesting contest, problems are quite hard in comparsion to other school olympiads. There will be internet-contest on same problemset: first tour at 9th July, second at 11th July; both tours will start at 08:00 UTC.
Rules — like on old IOI with test groups (group scores only if all tests in that group passed)
Registration closed tomorrow (08 July) at 18:00 UTC!
UPD: (possibly) rules changed this year.
UPD2: you should have recieved e-mail wih password and instructions. Rules indeed were updated.
UPD3: Contest server is veeeery slow so here is the mirror for the tasks (thx to popoffka):
UPD4: Here is mirror for second day statements (thx to yeputons):
Hello everybody. Here's my simple userscript, that highlights viewed submits in tables.
PavelKunyavskiy suggested to make it public.
Because it's not good to send additional AJAX queries to the server, functionality is quite little. Submit becomes marked after opening it's table cell. Unique-hash of submit is (user, problem, time), so submits, made in same minute, seems identical. I don't think it's a big problem :-)
Everybody who doesn't like default style can adjust it in function color.
It works in Firefox in Greasemonkey, in Chrome by default. Don't know about Opera, though.
I can improve something. Use it :-)
UPD1: Now by ctrl-click as good as by double-click
UPD2: Now works under Opera.
Summer finally has come! So I want to tell about cool summer Internet Problem Solving Contest or IPSC. It's very interesting internet-contest. You can participate as a part of the team, or individually; there is also secondary school division on same problemset, but with separate results.
Usual problem are algorithmic output-only, but there are also some tricky challenging. As example, in previous contest there was problem where you had to take care about your dog — right answers decreased your penalty on 20 minutes, incorrect answer would cause death of your animal :-)
Today, June 1 at 08:00 UTC starts practice tour. It's recommended to everyone to participate in it, there are also interesting tricky (previous year) problems.
Contest starts at 10:00 UTC 2 June. GL & HF!
Our teams:
SPbSU4 (Dmitry_Egorov, PavelKunyavskiy, yeputons)
Endeavour to Jump Together (tatyanakov, Goshish, Malinovsky239)
Ide (yarrr, caustique, ant.ermilov)
unusual (eduardische, nvilcins, gen)
Ponyville Coders (ivan.popelyshev, halyavin, iroro)
Red-headed Leage (tunyash, Skird, fdoer), homo_sapiens(Edvard)
Individual: Scorpy (Scorpy), Gerald (Gerald), homo_sapiens(Edvard)
Yesterday at 14:00 GMT starts first internet-round of COCI - Croatian Open Competition in Informatics. As usual, it will contain 6 problems for 3 hours. Testing system - like in old IOI (without feedback, each test is rated separately).
There isn't nothing really hard in registering - just registering in testing system and logging in COCI Contest #1.
From myself: I like that contests. Great, tasty problems with right rating system :-)
Thanks to yeputons for undistinguished idea of publishing about COCI on CF.
For those who don't know yet. Yesterday morning Steve Jobs died.
It's hard to estimate what he done for IT for his life. It's very sad that so great people die.
Sometimes I think about such a question. We are solving one-thread contests: we solve all problems without parallel programming.
But is there any contest with problems for parallel algorithms? I think it would be quite interesting. Does anybody know?
Problem DIV1-A, Div2-C. Trains.
This problem can be approached from two sides - from a programmer's perspective and a mathematician's one. We consider both approaches.
First, let's write some general propositions. Let's put on a straight line all the moments of time when the trains arrive. We will refer the interval between two successive points to the girl, to who the train that matches the right end of the segment is going. Also note that the entire picture is periodic with the period equal to lcm(a, b). Vasya will obviously more often visit the girl, whose total length of the segments is larger.
The programming approach is about modeling the process. If we need to compare the lengths of two sets of intervals, then let's count them. We can do it using two pointers. Let's see what train comes next, add time before the arrival of the train to one of the answers, move the pointer and the current time. We should stop either when two last trains arrive simultaneously or when arrive a+b trains. The solution has asymptotic O(a + b), that fits the time limit. Don't forget that lcm(a,b) ~ 10^12, i.e., we need the 64-bit data type.
The mathematical approach provides us with a more elegant and shorter solution, however, it takes more thinking. It seems obvious that Vasya will more often go to the girl, to who trains go more often. This fact is almost true. Let's try to prove it. Let's divide a and b by their gcd - from this, obviously, nothing will change. To make it clearer, let a ≤ b. Let's calculate the total length of segments corresponding to the second girl. For this, we need to take a few facts into consideration.
1) All of them do not exceed a
2) All a segments are different (due to coprimeness of a and b).
3) They all are at least 1.
But such a set of intervals is unique - it’s set of numbers {1, 2, … , a} and its length equals
. Besides, the equality is fulfilled when the following condition is met: b - a = 1.
Hence the following is true. The answer is Equal, when |a - b| = 1, otherwise Vasya goes more often to the girl to which the trains go more often. The key is not to forget to divide a and b by their gcd.
Problem Div1-B, Div2-D. Vasya and Types.
In this task, it was necessary to do exactly what is written in the problem's statement, for practically any complexity.
You are suggested to do the following. For each data type we shall store two values - its name and the number of asterisks when it is brought to void. Then the typeof request is processed by consecutively looking at each element of an array of definitions, in which we find the desired name of the type and the number of asterisks in it.
The type errtype is convenient to store as void, to which we added - inf asterisks.
Thus, fulfilling a typedef request, we find the number of asterisks in the type A, add to it a number of asterisks and subtract the number of ampersands. Do not forget to replace any negative number of asterisks by - inf, and create a new definition of type B, removing the old one.
Problem Div1-C, Div2-E. Interesting Game.
In this task you should analyze the game. However, due to the fact that with every move the game is divided into several independent ones, the analysis can be performed using the Grundy's function (you can read about it here, or here). Now all we have to do is to construct edges for each position. We can build the edges separately for each vertex by solving
simple linear equations for each number of piles after splitting. We can construct all the divisions in advance, simply taking one by one the smallest pile and the number or piles and terminating when the sum exceeds n. The second way is better because it works for the O(m + n), where m stands for the number of edges, and the first one works for 
, which is larger.
We should evaluate m in the maximal test. The edges are no more than
. However, in practice they are much less - about 520 thousand. Which is why there's enough time to build the edges within the time limit of O(nk).
You can try to find a Grundy's function by the definition if we xor all the required values for each position. But this may not work: it has too many long partitions (solutions with lazy countings or other ideas was working, though).
Let's learn how to quickly count a Grundy's xor function for a long partition. Let's use a standard method for counting functions on the interval - xor[l, r] = xor[0, r]\^xor[0, l - 1]. In the course of the algorithm we will keep a xor on a prefix of xor[i] up to i. Then the xor on the interval can also be calculated as O(1). The solution was strictly successful due to the number of edges, which is not very large.
Problem Div1-D. Beautiful Road.
In this task we should count for each edge the number of ways on which it is maximal. Since for one edge alone it does not seem possible to find the answer faster than in the linear time, the solution will compute answer for all the edges at once.
We shall solve the problem first for the two extreme cases, then, combining these two we will obtain a complete solution.
The first case is when the weights of all edges are identical. In this case we can solve the problem via DFS. For each edge, we just need to count the number of paths that this edge lies on it. This number is the product of the number of vertexes on different sides of the edge. If we count the number of vertexes on one side from it, while knowing the total number of vertexes in the tree, it is easy to find the number of vertexes on the other side of it, and hence the required number of ways on which it lies.
The second case - when the weights of all edges are distinct. Sort the edges in the order of the weight's increasing. Initially we take a graph with no edges. We add an edge in the order of increasing of weight. For each edge we join the connected components it connects. Then the answer for each new added edge is the product of the size of components that it has connected.
Now we must combine these two cases. We will add the edges in the ascending order, but not one by one, but in the groups of the equal weight. We should understand what the answer is for each of the added edges. After adding our edges some number of connected components was formed - for each edge, we calculate the same product of the number of vertexes on different sides inside his newly formed connected component.
To find this number of edges on the different sides, we should realize that it is only enough to know the sizes of the old connected components and connections between them - how they were arranged is not important to us. We use a DSU: adding an edge to our forest, we combine the old connected components by these edges. Note that prior to the merging of the components we must calculate an answer for our edges - and it is possible to make via a DFS on our compressed forest as in the first case, only instead of the number of vertexes on different sides of the edge we take the sum of the sizes of the connected components on different sides of the edge.
How to do it neatly:
This problem can be approached from two sides - from a programmer's perspective and a mathematician's one. We consider both approaches.
First, let's write some general propositions. Let's put on a straight line all the moments of time when the trains arrive. We will refer the interval between two successive points to the girl, to who the train that matches the right end of the segment is going. Also note that the entire picture is periodic with the period equal to lcm(a, b). Vasya will obviously more often visit the girl, whose total length of the segments is larger.
The programming approach is about modeling the process. If we need to compare the lengths of two sets of intervals, then let's count them. We can do it using two pointers. Let's see what train comes next, add time before the arrival of the train to one of the answers, move the pointer and the current time. We should stop either when two last trains arrive simultaneously or when arrive a+b trains. The solution has asymptotic O(a + b), that fits the time limit. Don't forget that lcm(a,b) ~ 10^12, i.e., we need the 64-bit data type.
The mathematical approach provides us with a more elegant and shorter solution, however, it takes more thinking. It seems obvious that Vasya will more often go to the girl, to who trains go more often. This fact is almost true. Let's try to prove it. Let's divide a and b by their gcd - from this, obviously, nothing will change. To make it clearer, let a ≤ b. Let's calculate the total length of segments corresponding to the second girl. For this, we need to take a few facts into consideration.
1) All of them do not exceed a
2) All a segments are different (due to coprimeness of a and b).
3) They all are at least 1.
But such a set of intervals is unique - it’s set of numbers {1, 2, … , a} and its length equals
. Besides, the equality is fulfilled when the following condition is met: b - a = 1. Hence the following is true. The answer is Equal, when |a - b| = 1, otherwise Vasya goes more often to the girl to which the trains go more often. The key is not to forget to divide a and b by their gcd.
Problem Div1-B, Div2-D. Vasya and Types.
In this task, it was necessary to do exactly what is written in the problem's statement, for practically any complexity.
You are suggested to do the following. For each data type we shall store two values - its name and the number of asterisks when it is brought to void. Then the typeof request is processed by consecutively looking at each element of an array of definitions, in which we find the desired name of the type and the number of asterisks in it.
The type errtype is convenient to store as void, to which we added - inf asterisks.
Thus, fulfilling a typedef request, we find the number of asterisks in the type A, add to it a number of asterisks and subtract the number of ampersands. Do not forget to replace any negative number of asterisks by - inf, and create a new definition of type B, removing the old one.
Problem Div1-C, Div2-E. Interesting Game.
In this task you should analyze the game. However, due to the fact that with every move the game is divided into several independent ones, the analysis can be performed using the Grundy's function (you can read about it here, or here). Now all we have to do is to construct edges for each position. We can build the edges separately for each vertex by solving
simple linear equations for each number of piles after splitting. We can construct all the divisions in advance, simply taking one by one the smallest pile and the number or piles and terminating when the sum exceeds n. The second way is better because it works for the O(m + n), where m stands for the number of edges, and the first one works for , which is larger.We should evaluate m in the maximal test. The edges are no more than
. However, in practice they are much less - about 520 thousand. Which is why there's enough time to build the edges within the time limit of O(nk).You can try to find a Grundy's function by the definition if we xor all the required values for each position. But this may not work: it has too many long partitions (solutions with lazy countings or other ideas was working, though).
Let's learn how to quickly count a Grundy's xor function for a long partition. Let's use a standard method for counting functions on the interval - xor[l, r] = xor[0, r]\^xor[0, l - 1]. In the course of the algorithm we will keep a xor on a prefix of xor[i] up to i. Then the xor on the interval can also be calculated as O(1). The solution was strictly successful due to the number of edges, which is not very large.
Problem Div1-D. Beautiful Road.
In this task we should count for each edge the number of ways on which it is maximal. Since for one edge alone it does not seem possible to find the answer faster than in the linear time, the solution will compute answer for all the edges at once.
We shall solve the problem first for the two extreme cases, then, combining these two we will obtain a complete solution.
The first case is when the weights of all edges are identical. In this case we can solve the problem via DFS. For each edge, we just need to count the number of paths that this edge lies on it. This number is the product of the number of vertexes on different sides of the edge. If we count the number of vertexes on one side from it, while knowing the total number of vertexes in the tree, it is easy to find the number of vertexes on the other side of it, and hence the required number of ways on which it lies.
The second case - when the weights of all edges are distinct. Sort the edges in the order of the weight's increasing. Initially we take a graph with no edges. We add an edge in the order of increasing of weight. For each edge we join the connected components it connects. Then the answer for each new added edge is the product of the size of components that it has connected.
Now we must combine these two cases. We will add the edges in the ascending order, but not one by one, but in the groups of the equal weight. We should understand what the answer is for each of the added edges. After adding our edges some number of connected components was formed - for each edge, we calculate the same product of the number of vertexes on different sides inside his newly formed connected component.
To find this number of edges on the different sides, we should realize that it is only enough to know the sizes of the old connected components and connections between them - how they were arranged is not important to us. We use a DSU: adding an edge to our forest, we combine the old connected components by these edges. Note that prior to the merging of the components we must calculate an answer for our edges - and it is possible to make via a DFS on our compressed forest as in the first case, only instead of the number of vertexes on different sides of the edge we take the sum of the sizes of the connected components on different sides of the edge.
How to do it neatly:
- It’s good idea to dynamically create compressed graph at each step: it will have O(E’) vertexes and edges, where E' - the number of added edges of the source tree.
- Do not create unnecessary vertexes in the new created compressed column: after all, the DFS works for O(V + E), rather than O(E), so the unused connected components we do not include in the circuit.
- We should use the 64-bit data type. To store the response of the order of (105)2 it will fit more than the 32-bit one.
- We should not merge the adjacency lists explicitly when connecting components. It is too long.
- You can do everything instead of arrays on vectors / maps / heap, so the total time of nulling of the marks for an array of DFS occupied O(V). Or, instead of nulling of the array overlays we keep instead of a Boolean flag the iteration number. In general, it is better not to null extra arrays. After all, algorithm can make V iterations.
- Be careful, solutions with map works at TL's maximum, so it should be written very carefully; you should better use the vectors + list of involved nodes. The author's solution with the map fits in the TL with only half a second to spare. While using a vector has a four-time stock of time to spare.
Problem Div1-E. Mogohu Ree Idol.
In this task we had to verify that the point is the centroid of the triangle formed by points of the given three polygons. Lets reformulate the problem. We should verify the existence of three points A, B, C, such that A belongs to the first polygon, B - to the second one, C - to the third one, and 
. Logically, you should understand what set of points determines this 
, you should understand how to build it and test a point on whether it belongs to the set or not. This set is called Minkowski sum. We will need only one of its properties: the sum of two convex polygons is a convex polygon whose sides coincide as vectors, with the sides of the original polygons. We will prove this later.
How do we use it now? The first thing that this property gives us is an algorithm to test for belonging. Once the sum is built you can test whether or not a point belongs to the sum using a standard algorithm of testing a point being inside of a convex polygon in logarithmic time. Also the constructing algorithm is immediately obtained. We just need to add the coordinates of the lowest (the leftmost of them) points of all three polygons. As a result, we get a point, which is the lower left for the sum polygon. The sides are now represented as a sorted by the polar angles list of parties of the original polygons (instead of sorting we may merge sorted arrays).
Proof.
We shall prove the correctness of the algorithm for two polygons, for three polygons the proof is just the same. Let the first polygon be represented by A and the second one - by B. Denote the sum as M.
We will prove that M is a convex set.
Choose some 
. By definition, 
Q, 
(here and below the point is identified with its radius vector).
Let’s take some point 
. We shall prove that 
.
As G lies on the [AB], 
.
Note that the first bracket is obviously some point lying on the segment [PE]. That means the point lying inside the polygon A, since A is convex. Similarly, the second bracket is inside B. Hence, their sum, i.e., G, lies in the Minkowski sum. This means that the Minkowski sum is a convex set.
Let us consider some side XY of the first polygon. Let's rotate the plane so that the side XY was horizontal and that the polygon lied above the XY line.
Consider the lowest horizontal line intersecting B. Let it cross B along the segment of PR, where point P does not lie further to the right of the R (it is clear that PR can turn out to be a degenerate segment from one vertex or the segment between two consquent verteces). Let's call PR the lowest segment of the polygon. Then we construct in the similar way the lowest segment UV of polygon M.
Let's prove that
- if not, let 
. It is clear that x and p are the lowest points of the polygons A and B - otherwise one of them can be moved to a small vector d, which lies in the lower half-plane, so that the point remained within its polygon. In this case U will move the same way to d, which contradicts the fact that U is one of the lowest points of the polygon.
Thus, x and p are the lowest points of their polygons. Similarly, x and p are the leftmost points on the lowest segments of their polygons - otherwise we shift x or p to vector d that is directed to the left. It is also a contradiction - the U point stops to be the leftmost lower point.
Hence, U = X + P. Similarly, V = Y + Q. Hence, 
.
Thus, the sequence of sides M as vectors in the, for instance, counterclockwise order, is nothing other than the union of sides of A and B as vectors in the counterclockwise order, that immediately proves the correctness of the algorithm.
Tutorial of Codeforces Beta Round 73 (Div. 1 Only)
Tutorial of Codeforces Beta Round 73 (Div. 2 Only)
Please note due to Daylight Savings, TopCoder time has changed to Eastern Daylight Time or UTC -4.
TopCoder(R) Single Round Match 500 is scheduled for Saturday, March 19, 2011 at 12:00 UTC -4 hours. In recognition of this milestone, TopCoder will be awarding 5,000 in cash prizes plus more! So get ready for the most prestigious TopCoder SRM in years and give yourself a chance at becoming part of history!
SRM 500 will begin at 12:00 UTC-4 with registration opening 3 hours prior to match time. Registration will be limited to 2,100 slots on a first come first serve basis so be sure to register early!
Please be sure to check here for the start time in your time zone:
http://www.timeanddate.com/worldclock/fixedtime.html?&day=19&month=03&year=2011&hour=12&min=00&sec=0&p1=179
* Registration will begin at 9:00 and will end at 11:55 UTC -4 hours
* Allowable programming languages are Java, C++, Microsoft(R) Visual
C#(R) .NET, and Microsoft Visual Basic(R) .NET
* TopCoder Administrators will be available in the Admin Lobby Room to answer questions
* For more details click here:
http://www.topcoder.com/tc?module=MatchDetails&rd=14429
Prizes:
One SRM 500 t-shirt will be awarded per room.
Up to 75 commemorative badges will be given out.
Cash Prize Money Distribution
* Competitors with a rating of 1200 or higher at the start of the match will be placed into a division one room. All other competitors, including non-rated competitors, will be placed into a division two room.
* Room assignments within each division will performed randomly, with prizes distributed evenly among all rooms in each division.
* 70% of the total purse will be awarded to division one competitors, and 30% to division two competitors.
* Approximately 20 competitors will be assigned to each room.
* The first, second, and third place coders in each division one room will receive 50%, 30%, and 20% of the room award, respectively.
* The first and second place competitors in each division two room will receive 60% and 40% of the room award, respectively.
* In the event of a tie for any prize winning position, the sum of the awards of the tied competitors will be distributed evenly. (For example, if five coders tie for second place in a division one room, each will receive (30%+20%)/5 or 10% of the room award.)
* Prizes will only be awarded to competitors who finish with greater than zero scores.
In order to be eligible for prizes, a competitor must be a TopCoder member in good standing, at least 18 years of age, and must not be a resident of Cuba, Iran, Iraq, Libya, North Korea, Sudan, Syria, the Quebec province of Canada, or anywhere else where this contest is prohibited by applicable law.
For more contest details, click here: http://www.topcoder.com/tc?module=MatchDetails&rd=14429
Best of luck to you in the Arena!
- The TopCoder Competitions Team
Note that registration opened at about 20 minutes ago. And there is already 1100 people registered. Don't be late!
TopCoder(R) Single Round Match 500 is scheduled for Saturday, March 19, 2011 at 12:00 UTC -4 hours. In recognition of this milestone, TopCoder will be awarding 5,000 in cash prizes plus more! So get ready for the most prestigious TopCoder SRM in years and give yourself a chance at becoming part of history!
SRM 500 will begin at 12:00 UTC-4 with registration opening 3 hours prior to match time. Registration will be limited to 2,100 slots on a first come first serve basis so be sure to register early!
Please be sure to check here for the start time in your time zone:
http://www.timeanddate.com/worldclock/fixedtime.html?&day=19&month=03&year=2011&hour=12&min=00&sec=0&p1=179
* Registration will begin at 9:00 and will end at 11:55 UTC -4 hours
* Allowable programming languages are Java, C++, Microsoft(R) Visual
C#(R) .NET, and Microsoft Visual Basic(R) .NET
* TopCoder Administrators will be available in the Admin Lobby Room to answer questions
* For more details click here:
http://www.topcoder.com/tc?module=MatchDetails&rd=14429
Prizes:
One SRM 500 t-shirt will be awarded per room.
Up to 75 commemorative badges will be given out.
Cash Prize Money Distribution
* Competitors with a rating of 1200 or higher at the start of the match will be placed into a division one room. All other competitors, including non-rated competitors, will be placed into a division two room.
* Room assignments within each division will performed randomly, with prizes distributed evenly among all rooms in each division.
* 70% of the total purse will be awarded to division one competitors, and 30% to division two competitors.
* Approximately 20 competitors will be assigned to each room.
* The first, second, and third place coders in each division one room will receive 50%, 30%, and 20% of the room award, respectively.
* The first and second place competitors in each division two room will receive 60% and 40% of the room award, respectively.
* In the event of a tie for any prize winning position, the sum of the awards of the tied competitors will be distributed evenly. (For example, if five coders tie for second place in a division one room, each will receive (30%+20%)/5 or 10% of the room award.)
* Prizes will only be awarded to competitors who finish with greater than zero scores.
In order to be eligible for prizes, a competitor must be a TopCoder member in good standing, at least 18 years of age, and must not be a resident of Cuba, Iran, Iraq, Libya, North Korea, Sudan, Syria, the Quebec province of Canada, or anywhere else where this contest is prohibited by applicable law.
For more contest details, click here: http://www.topcoder.com/tc?module=MatchDetails&rd=14429
Best of luck to you in the Arena!
- The TopCoder Competitions Team
Note that registration opened at about 20 minutes ago. And there is already 1100 people registered. Don't be late!
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/05/2024 09:57:43 (l2).
Desktop version, switch to mobile version.
Supported by
